The tail identifies the last node in a linked list. In a singly linked list, its next pointer is empty; in a doubly linked list, it also links back to its predecessor. section 6.4 section 6.24
Keeping a direct reference to the tail changes what the list can do efficiently:
- Doubly linked lists can reach the tail in constant time and insert a new node after it without traversing the list. section 6.17
- Deleting the final node requires updating the tail to the previous node; deleting the only node clears both tail and head. section 6.19 section 6.9
- A doubly linked list can traverse backward from its tail, while a singly linked list can traverse only from head to tail. section 6.24
Appending at the back
An empty list assigns the new node to both _head and _tail. Otherwise, it saves the old tail, creates a new node, makes the new node the tail, and connects the old tail to it. section 6.17
def insert_to_back(self, data):
if self._tail is None:
self._tail = self._head = Node(data)
else:
old_tail = self._tail
self._tail = Node(data)
self._tail.prepend(old_tail)
Inspect the Python implementation that uses the tail reference to append directly at the back. section 6.17
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
Inspect how deletion updates the tail when removing the final node and clears it when the list becomes empty. section 6.19
