Imagine keeping track of customer orders as they arrive and are fulfilled. A linked list can grow when an order arrives and shrink when one is removed: it creates nodes as needed instead of reserving space for the whole collection in advance. Each node needs extra space for a link, though, so flexibility is not free. section 6.5 section 6.3
A linked list is a sequence of nodes. Each node stores a value and a link to another node; the nodes need not sit together in memory. In the simplest version, a singly linked list, each link points to the next node. Keep a reference to the first node, called the head, to find your way into the list. The last node, or tail, has no next node. section 6.2 section 6.4
That layout changes how you reach an element. An array can read its third element directly by index. A linked list must start at the head and follow two links. Reaching a distant node—and searching for a value—takes time proportional to the number of nodes visited. Keeping the list sorted does not give it efficient binary search, because even reaching a middle node requires traversal. section 6.3 section 6.13
Where you change the list matters:
- Insert at the front: make a node whose next link points to the old head, then make it the new head. This takes constant time. section 6.7
- Delete from the front: move the head reference to the next node. This also takes constant time. section 6.10
- Insert at the back or into a sorted position: first traverse to the right place. Without a stored tail reference, back insertion takes linear time; sorted insertion does too. section 6.7 section 6.12
- Delete a matching value: traverse while remembering the previous node, then redirect its link around the target. Deleting the head needs a separate case. Finding the target makes this operation linear-time. section 6.9
class Node:
def __init__(self, data, next_node = None):
self._data = data
self._next = next_node
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
The Python Node class shows the two essential pieces: stored data and a reference to the next node. A list class can hold a head reference set to None when empty. section 6.6
Need to move backward as well? A doubly linked list adds a predecessor link to each node, allowing traversal in both directions at the cost of more memory. For repeated cycles through elements, a circular linked list links the tail back to the head. Neither choice makes a singly linked list’s slow indexed access disappear. section 6.24 section 6.3
Choosing a list for a container
A stack changes only one end, so a singly linked list can insert and remove at its head in constant time while growing as needed. A bag can likewise insert at the head when it does not require insertion order during traversal. If compact storage or a known fixed capacity matters more, an array may be a better fit. section 8.8 section 7.12 section 9.9
Table 7.2 A comparison of the running time of arrays and linked lists (view table figure)
| Insert front |
Insert back |
Insert middle |
Delete |
Search |
|
|---|---|---|---|---|---|
| Array |
O(n) |
O(1) |
O(n) |
O(1)* |
O(n) |
| Singly linked list |
O(1) |
O(n) |
O(n) |
O(n) |
O(n) |
| Doubly linked list |
O(1) |
O(1) |
O(n) |
O(1)** |
O(n) |
Compare operation costs for arrays, singly linked lists, and doubly linked lists. Check the table’s conditions on deletion: its cost depends on whether the node is already known or must first be found. section 7.3
