Doubly and circular lists

A one-way list can only be walked forwards, and to delete a node you need the node before it. Give each node a second reference, to the node before it. Then you can walk both ways, and delete a node without the one before it.

A second reference: prev

In a doubly linked list (a two-way list), each node has next and also prev. The first node’s prev is None, and so is the last node’s next.

class Node:
    def __init__(self, value):
        self.value = value
        self.prev = None
        self.next = None

Now a node knows both its neighbours. If you hold a reference to a node, you can remove it in O(1) without any walk: tell its two neighbours to point past it. Step through it:

node.prev.next = node.next
node.next.prev = node.prev

Every change now touches two references for each link, one in each direction. Inserting a node between a and b sets four: the new node’s prev and next, then a.next and b.prev. The rule from lesson 2 still holds: set the new node’s own references first, while a and b still point to each other.

Sentinel nodes at both ends

The removal code above fails at the ends: if node is the first node, node.prev is None, and None.next raises an error. The fix is the dummy node from lesson 2, now at both ends. Two extra nodes, often called sentinels, sit before the first real node and after the last one, and they are never removed:

class Line:
    def __init__(self):
        self.front = Node(None)       # sentinel before the first real node
        self.back = Node(None)        # sentinel after the last real node
        self.front.next = self.back
        self.back.prev = self.front

    def _remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
        return node.value

Every real node now has a real node or a sentinel on each side, so _remove works for every real node with no checks. To add a value, insert a new node between two nodes as above, setting its own two references first. Adding at the front means inserting between front and front.next; adding at the back means inserting between back.prev and back. The list is empty exactly when front.next is back.

Circular lists

In a circular list, the last node’s next refers back to the first node instead of None. There is no end, so a walk must decide when to stop: usually when it comes back to the node it started from. The figure’s second version shows this.

Circular lists suit things that take turns over and over, such as players in a game or jobs that share a processor. If you keep a reference to the last node, you have both ends at once: the first node is last.next. The sentinel version above becomes circular in the same way if one sentinel is used as both the front and the back.

How Python’s deque is built

collections.deque (say “deck”, short for double-ended queue) adds and removes at both ends in O(1). Inside, it is a two-way linked list. But each node does not hold one item: it holds a block of 64 items. This keeps most of the speed of a list, because items sit close together, and keeps the O(1) ends of a linked list.

The cost is in the middle: d[k] must skip whole blocks to reach item k, so it is O(n) in the worst case, not O(1). Use a deque for work at the ends. STAQ-3 uses it as a queue.

Now try LINK-P2, A two-way line.