The Doubly Linked List: The Second Link

Get access to whole semester resourcesSemester Pass

Chapter Twenty-Six

Syllabus topic Module 1, "Linked Structures: ADT of doubly linked list"

Pages 77 to 79 of 411

In one line

A doubly linked list gives every node a link backwards as well as forwards, which removes the predecessor problem and makes deletion of a known node O(1).

The problem it solves

Chapter 19 found the difficulty: deleting a node means changing the node before it, and a singly linked node holds no way to reach backwards. So deletion carried a second walking pointer, and deleting the last node stayed O(n) even with a tail pointer.

The doubly linked list fixes that directly. Each node holds three things:

Part	Holds
prev	the address of the previous node
data	the value
next	the address of the next node

Now a node knows both of its neighbours. Given any node, you can reach everything around it without walking from anywhere.

The picture

null .--[ | A | -]--.--[ | B | -]--.--[ | C | -]--. null

head --. first node last node .-- tail

Two ends need care and they are where student code fails:

The first node's prev is null. Not the head variable, not itself: null. The last node's next is null. As before.

A list with one node has both null in the same node, which is worth checking by hand when writing any operation.

The ADT

The operations are the singly linked list's, plus the ones the backward link makes possible.

Operation	Needs	Returns	Cost
`DoublyLinkedList()`	nothing	a list	O(1)
`is_empty()`	nothing	true or false	O(1)
`length()`	nothing	a number	O(1) with a counter
`prepend(v)`	a value	nothing	O(1)
`append(v)`	a value	nothing	O(1), with a tail
`insert_before(node, v)`	a node, a value	nothing	O(1)
`insert_after(node, v)`	a node, a value	nothing	O(1)
`delete(node)`	a node	nothing	O(1)
`traverse_forward()`	nothing	values, first to last	O(n)
`traverse_backward()`	nothing	values, last to first	O(n)

Two rows are new and both matter.

delete(node) takes a node, not a value, and is O(1). This is the whole point. On a singly linked list, deleting a node you are holding still costs O(n) because the predecessor must be found.

traverse_backward exists at all. A singly linked list cannot walk backwards, at any price, without reversing itself or using a stack.

Built, both ways

class DNode:
    """A node with links both ways."""

    def __init__(self, data):
        self.prev = None
        self.data = data
        self.next = None

    def __repr__(self):
        return "DNode(%r)" % (self.data,)


class DoublyLinkedList:
    def __init__(self, values=()):
        self.head = None
        self.tail = None
        self.n = 0
        for value in values:
            self.append(value)

    def is_empty(self):
        return self.head is None

    def length(self):
        return self.n

    def append(self, value):
        node = DNode(value)
        if self.tail is None:
            self.head = self.tail = node
        else:
            node.prev = self.tail
            self.tail.next = node
            self.tail = node
        self.n += 1
        return node

    def forward(self):
        out, walk = [], self.head
        while walk is not None:
            out.append(walk.data)
            walk = walk.next
        return out

    def backward(self):
        out, walk = [], self.tail
        while walk is not None:
            out.append(walk.data)
            walk = walk.prev
        return out

    def check(self):
        """Prove the two chains agree. A doubly linked list that disagrees with
        itself is the classic defect, so it is checked rather than assumed."""
        if self.head is not None and self.head.prev is not None:
            return "head.prev is not null"
        if self.tail is not None and self.tail.next is not None:
            return "tail.next is not null"
        walk, seen = self.head, 0
        while walk is not None:
            seen += 1
            if walk.next is not None and walk.next.prev is not walk:
                return "forward and backward disagree at %r" % (walk.data,)
            walk = walk.next
        if seen != self.n:
            return "counter says %d, chain has %d" % (self.n, seen)
        return "consistent"


lst = DoublyLinkedList(["A", "B", "C", "D"])
print("forward        :", lst.forward())
print("backward       :", lst.backward())
print("length         :", lst.length())
print("head.prev      :", lst.head.prev)
print("tail.next      :", lst.tail.next)
print("consistency    :", lst.check())

one = DoublyLinkedList(["only"])
print()
print("one node: head is tail:", one.head is one.tail,
      "| prev:", one.head.prev, "| next:", one.head.next)
print("consistency    :", one.check())

empty = DoublyLinkedList()
print("empty    :", empty.forward(), empty.backward(), empty.check())

The Doubly Linked List: The Second Link

forward        : ['A', 'B', 'C', 'D']
backward       : ['D', 'C', 'B', 'A']
length         : 4
head.prev      : None
tail.next      : None
consistency    : consistent

one node: head is tail: True | prev: None | next: None
consistency    : consistent
empty    : [] [] consistent

The backward traversal is the new capability, and it costs nothing extra: it is the same loop following prev from the tail.

The invariant, and why it is checked

A doubly linked list has an invariant that a singly linked one does not:

For every node x with a next, x.next.prev must be x.

The two chains must agree. Every operation has to maintain both, and an operation that updates one and forgets the other leaves a list that traverses correctly forwards and wrongly backwards, or vice versa. That defect is invisible until somebody walks the other way.

This is why the class above carries a check method and why the rest of this book calls it after every operation it demonstrates. It is the same discipline as chapter 18's tail pointer: anything remembered twice must be kept in step, and the way to be sure is to verify it rather than trust it.

Quick revision

A doubly linked node holds prev, data and next.
The first node's prev is null and the last node's next is null; a one node list has both in the same

node.

The backward link removes the predecessor problem, so deleting a known node is O(1).
Backward traversal becomes possible: the same loop from the tail following prev.
The ADT gains insert_before, delete(node) and traverse_backward.
The invariant is that x.next.prev is x for every node with a next; both chains must always agree.
An operation that updates one chain and forgets the other leaves a defect invisible in one direction.

The Doubly Linked List: The Second Link

Test yourself

1. What three fields does a doubly linked node hold? prev, the address of the previous node; data; and next, the address of the following node.

2. What is the first node's prev, and the last node's next? Both are null. In a one node list, that single node has both.

3. Which problem from the singly linked list does the second link remove, and what does it buy? The predecessor problem. Deleting a node you already hold becomes O(1), because its previous node can be reached directly instead of being found by walking.

4. State the invariant of a doubly linked list. For every node x that has a next, x.next.prev must be x. The forward and backward chains must agree.

5. What kind of defect does breaking that invariant produce, and why is it hard to find? One that traverses correctly in one direction and wrongly in the other. It is invisible until somebody walks the other way, and until then every test passes.

6. Why does the class in this chapter carry a check method? Because the invariant is maintained by hand in every operation, and the reliable way to know it holds is to verify it after each operation rather than trust that it was remembered.

The rest of this subject

These notes are cut from the University's printed syllabus. Open the syllabus itself, or the past papers, for the same subject.

Issue