When going back matters
Imagine a game in which a player moves through rooms in order. A singly linked list can point from each room to the next, but the player also needs to retrace their steps. A doubly linked list supplies the links needed to move in either direction. The same need arises when moving through document layers or undoing and redoing actions. section 6.16
A doubly linked list is made of nodes. Each node holds an element, a link to the next node, and a link to the previous node. Starting at the head, you can follow next links to the tail; starting at the tail, you can follow previous links back. A list wrapper can keep links to both ends. Unlike an array, though, a linked list cannot jump directly to an arbitrary index. section 6.15 section 6.14
class Node:
def __init__(self, data):
self._data = data
self._next = None
self._prev = None
def data(self):
return self._data
def next(self):
return self._next
def has_next(self):
return self._next is not None
def append(self, next_node):
self._next = next_node
if next_node is not None:
next_node._prev = self
def prev(self):
return self._prev
def has_prev(self):
return self._prev is not None
def prepend(self, prev_node):
self._prev = prev_node
if prev_node is not None:
prev_node._next = self
The Python node implementation shows the two links. Its append and prepend methods update the adjoining node’s link too, so the connection works in both directions. section 6.15
The extra link helps with some operations, but it does not make every operation faster:
- Insert at either end in constant time when the wrapper tracks the head and tail. Inserting between known neighboring nodes also takes constant time; finding an unknown position still requires traversal. section 6.17
- Search by value one node at a time. Following links backward is possible, but without a reason to start near the tail, it does not improve a general search. section 6.18
- Delete a found node by linking its neighbors around it, updating the head or tail when necessary. Deleting by value remains O(n) because finding the node can require a full search. section 6.19
- Join two nonempty lists by linking the first tail to the second head. This concatenation takes constant time, unlike merging arrays by allocating a larger array and moving their elements. section 6.20
def delete(self, target):
node = self._search(target)
if node is None:
raise ValueError(f'{target} not found in the list.')
if node.prev() is None: #1
self._head = node.next()
if self._head is None: #2
self._tail = None
else:
self._head.prepend(None)
elif node.next() is None: #3
self._tail = node.prev()
self._tail.append(None)
else: #4
node.prev().append(node.next())
del node
#1 Delete the node at the beginning of the list.
#2 In this case, the list’s head was the only element in the list.
#3 Delete the node at the end of the list.
#4 General case
The delete method separates head, tail and middle cases. Notice the one-node case: removing the head must leave both wrapper links empty. section 6.19
Choose a doubly linked list when moving backward is important or when you often work at both ends. The tradeoff is an extra link in every node and more links to maintain after changes. If you only need forward movement, a singly linked list is simpler; if you need direct indexed access, the extra link will not provide it. section 6.15 section 6.24
