A reference is a value that identifies or provides access to an object or memory location. In a linked list, each node stores a reference—often called a link or pointer—to another node. This reference lets the list connect elements even when the nodes are scattered across memory. section 6.3 section 6.4
References determine how linked-list nodes can be reached and changed:
- A singly linked node references only its successor, so traversal proceeds from the head one node at a time. section 6.4
- A doubly linked node keeps references to both its successor and predecessor, enabling traversal in either direction. section 6.17
- Changing references can insert a node without shifting later elements, provided a neighboring node is already known. section 6.17
- Deleting a node requires reconnecting references; a singly linked list must retain the preceding node while searching. section 6.9
- References consume extra memory compared with array elements, but they allow nodes to occupy noncontiguous locations. section 6.3
Deleting through references
To delete a matching node, keep references named current and previous. When current reaches the target, update the head if there is no previous node; otherwise, make previous reference current's successor. If the target is absent, raise an error. section 6.9
def delete(self, target):
current = self._head
previous = None
while current is not None:
if current.data() == target:
if previous is None:
self._head = current.next() #1
else:
previous.append(current.next()) #2
return
previous = current
current = current.next()
raise ValueError(f'No element with value {target} was found in the list.') #3
#1 Edge case: delete the head of the list.
#2 Average case: a node in the middle of the list (or the tail as well)
#3 If it gets here, target is not in the list.
Inspect the deletion implementation to see references maintained during traversal, including the head edge case and predecessor relinking. section 6.9
