A linked list stores a sequence through references between nodes rather than through consecutive array positions. Its main local advantage is that an operation given the relevant node can change a small number of links without shifting the rest of the sequence. That statement needs qualifications: finding the node may be expensive, and correct links must preserve one coherent list rather than several disconnected cycles.
We will represent a doubly linked list by a circular ring with one sentinel. The sentinel is an actual node that marks the boundary but carries no sequence element. This makes insertion into an empty list and insertion at either end follow the same local rule. We will then move a node between lists, identify the aliasing cases that must be treated carefully, and explain what is and is not constant-time about a larger splice.
Separate a node's identity from its stored value
Each data node has a value, a prev reference and a next reference. Two nodes can store equal values and still be different objects. A handle is a reference to one particular node; operations using handles do not search by value first.
The sentinel is recognized by object identity, not by a special value. In the implementation it stores None, but an ordinary data node may also store None. Confusing the value test with an identity test would incorrectly treat that legitimate data node as the boundary.
Common mistake
(Detecting the sentinel by its value)
Suppose values() stopped when node.value is None instead of node is self.root. After a.append(None) and a.append(3) the list has two data nodes and size , but the traversal starts at the first data node, finds the value None, and stops at once: it returns the empty sequence. The identity test returns [None, 3]. A data value never decides whether a node is the boundary.
Definition 10.1.1
(A sentinel ring's representation invariant)
Let be the unique sentinel and the set of data nodes representing this list. Require all of the following:
- Starting at and repeatedly following
nextvisits every member of exactly once, then returns to , without visiting any other node. - For each node in , the two links are reciprocal:
- The stored
sizeis , excluding the sentinel. Distinct list objects have disjoint data-node sets and different sentinels.
For an empty list, is empty, size is zero and both sentinel links point back to itself.
The abstract sequence is the order of data values encountered after the sentinel. The invariant says more than “every node has two references”: it specifies reachability, order, boundary behavior and the count of elements.
Counterexample mode
Locally reciprocal links can still form the wrong global structure
Make one circular ring containing the sentinel and some nodes, and a second disjoint circular ring containing other nodes that were supposed to belong to the same list. Every node in both rings can satisfy the displayed reciprocal equations.
Those equations alone do not show that all intended members are reachable from the sentinel. A proof of a list update must preserve the single-cycle membership condition as well as the nearby link equations. Checking a node's two neighbors also does not establish that it belongs to the list supplied by the caller.
Insert before a known anchor
An anchor is a member of the destination ring, possibly its sentinel. Inserting before the sentinel appends at the end; inserting before the first data node prepends. If the list is empty, these positions coincide.
Suppose is the anchor and . For a new detached data node , replace the adjacent connection with
Set x.prev = left, x.next = anchor, left.next = x and anchor.prev = x, then increase the size by one. Save the neighbor before overwriting the links that identify it.
Proposition 10.1.2
(Insertion before an anchor)
Let a ring satisfy the representation invariant, let be a member of it (the sentinel or a data node), and let be a detached node. Save , then set x.prev = left, x.next = anchor, left.next = x, anchor.prev = x and increase the size by one. The ring again satisfies the invariant, and its sequence is the old sequence with inserted immediately before .
Proof
(Subdividing one connection)
The new node was not in any ring. Every old node keeps its relative order, except that the connection from to now passes through . Thus the forward traversal gains exactly one node and still returns to the same sentinel.
The four assignments establish reciprocity on both new connections, while all unaffected connections keep their old references. Increasing the size by one matches the enlarged data-node set. The argument also covers an empty list: then , and the result is the two-node ring containing and .
The sentinel removes special end cases from the rewiring rule; it does not remove the need to state that the anchor is valid and the inserted node is detached. The teaching implementation creates a fresh node for public insertion, so that detachedness is automatic for that operation.
Erase a known data node
For a data-node handle belonging to the source list, save and . Set left.next = right and right.prev = left, bypassing , and decrease the size by one. The helper then sets both links of to None to mark it detached.
Proposition 10.1.3
(Erasing a data node)
Let a ring satisfy the invariant and let be one of its data nodes. Save and , set left.next = right and right.prev = left, and decrease the size by one. The ring again satisfies the invariant, and its sequence is the old sequence without .
Proof
(Bypassing one node)
The old traversal encountered consecutively. The new traversal encounters , with every other member in the same order. The replacement connection is reciprocal, and the reachable data-node set loses exactly .
If was the only data node, both neighbors are the sentinel; the assignments restore its two self-links. The sentinel itself must never be erased, because it defines the ring boundary rather than representing an element.
Proof X-ray
Why a local update keeps a global invariant
Reciprocal links alone do not give a single cycle, as the counterexample above shows. The two proofs obtain the global condition from the shape of the change: insertion replaces the connection by the path , and erasure replaces a path of two connections by one. In both cases the forward traversal from the sentinel is the old traversal with exactly one node added or skipped, so single-cycle membership is inherited. Reciprocity has to be rechecked only on the changed connections, because no other node's links are written. The order of the assignments matters for the same reason: must be read before anchor.prev is overwritten, and before the links of are cleared.
A detached handle remains a reference to a live node object. Its value still exists, but it is no longer a member and cannot validly be passed to a member-only operation. Clearing its links is not a proof that an arbitrary other handle has the correct ownership.
Worked example 10.1.4
(The empty ring: insert, then erase)
Start with an empty list: root.prev = root.next = root and size . Calling insert_before(root, 5) saves , sets and , then left.next = x makes and anchor.prev = x makes . The size is and values() is . Now erase(x): the saved neighbors are both the sentinel, so left.next = right and right.prev = left restore the two self-links; the size is again and the links of are None. The same four-assignment rule and the same two-assignment rule worked on the empty ring as on a long one, with no end-case branch.
Move one node without copying its value
To move member from source list before anchor in target list , detach from its source ring and attach the same node before in the destination ring. When , decrement the source size and increment the target size. Within one list, the size stays unchanged.
For a move within one list, two requests already describe the existing order:
- Moving before itself is a no-op.
- Moving before its current next node is also a no-op, including when that next node is the sentinel.
Detect these cases before detaching. In all other cases, obtain the destination's preceding neighbor after detachment. A cached neighbor from the original ring can be the node being moved or a connection already changed by removal.
Counterexample mode
Caching the left neighbor before detaching
Suppose a move were coded as: read left = anchor.prev, detach , then attach between left and anchor. Take a list with sentinel and data nodes , and move before its current next node . Then , the node being moved. Detaching leaves . The attach step now sets and , then left.next = p makes , and . Afterwards but , and is a self-loop that cannot reach, so both the reciprocity and the single-cycle conditions fail. The implementation avoids this by returning early when the anchor is or its next node, and by reading anchor.prev only after the detach.
Worked example 10.1.5
(A handle follows its node between different sequences)
Let list have nodes storing in that order, and let have node storing 2.
| Operation | Values in A | Values in B | Sizes (A, B) |
|---|---|---|---|
| Initial state | |||
| Move q from A before B's sentinel | |||
| Move q from B before p in A | |||
| Move q before itself in A | |||
| Move q before its next node p | |||
| Erase p from A |
The handle always names the same node; its list membership changes, but no value copy creates a replacement node. After erasing , its value remains 4 and its two links are None. Passing to erase again would violate the operation's membership precondition.
A small implementation with explicit handle preconditions
For insert_before, the anchor must belong to that list, with its sentinel allowed. For erase and move_before, the source node must be a current data member of the source. A move's anchor must belong to the target, with its sentinel allowed. These ownership conditions are preconditions, not global checks performed by the code. The explicit sentinel guards do not validate an arbitrary handle's ownership.
class Node:
__slots__ = ("value", "prev", "next")
def __init__(self, value):
self.value = value
self.prev = self.next = None
class SentinelList:
def __init__(self):
self.root = Node(None)
self.root.prev = self.root.next = self.root
self.size = 0
@staticmethod
def _attach_before(anchor, node):
left = anchor.prev
node.prev = left
node.next = anchor
left.next = node
anchor.prev = node
@staticmethod
def _detach(node):
left, right = node.prev, node.next
left.next = right
right.prev = left
node.prev = node.next = None
def insert_before(self, anchor, value):
node = Node(value)
self._attach_before(anchor, node)
self.size += 1
return node
def append(self, value):
return self.insert_before(self.root, value)
def erase(self, node):
if node is self.root:
raise ValueError("the sentinel is not a data node")
self._detach(node)
self.size -= 1
return node.value
def move_before(self, node, target, anchor):
if node is self.root:
raise ValueError("the sentinel is not a movable data node")
if self is target and (anchor is node or anchor is node.next):
return
self._detach(node)
self._attach_before(anchor, node)
if self is not target:
self.size -= 1
target.size += 1
def values(self):
result = []
node = self.root.next
while node is not self.root:
result.append(node.value)
node = node.next
return result
For the example, create a = SentinelList() and b = SentinelList(), then use p = a.append(4), q = a.append(7), u = a.append(9) and t = b.append(2). The two transfers are a.move_before(q, b, b.root) and b.move_before(q, a, p). Afterwards a.values() is [7,4,9] and b.values() is [2].
For valid handles, each update performs a constant number of reference reads/writes. New-node insertion additionally allocates one node. The sequence enumeration values() takes time and output storage for a list of length ; it is not part of the constant-time update claim. The list itself uses node storage and one extra sentinel.
Do not hide the cost of finding a node
A handle-based insertion or erasure is pointer work. Inserting at the position of the th element is not automatically : the operation may first need to locate that element. For a zero-based valid index , walking from the nearer end takes
time, and locating a middle position is linear in the worst case. Searching for a particular value is also generally linear; equal values can correspond to several different node identities.
This explains when linked nodes help. If a separate structure already provides the relevant handles, a list can reorder them locally without shifting many entries. If the workload mostly asks for arbitrary indexed elements, an array's constant-time indexing may be more useful. An operation's full cost includes locating its arguments, not just the final link assignments.
A range splice exposes another hidden cost
Suppose a nonempty forward-contiguous range of data nodes runs from first through last, without passing through the source sentinel. The destination anchor is outside that range. The range's internal links already have the required order, so they need not change.
Cut the source boundary by connecting first.prev to last.next in both directions. Then obtain anchor.prev in the resulting ring and connect that node to first, and last to anchor, in both directions. These are six reference-field writes, independent of the number of moved nodes. If the anchor is the range's old next node in the same list, recomputing its previous neighbor after the cut correctly restores the original order.
However, moving the range between lists also changes their stored sizes by . Knowing the two endpoint handles does not by itself provide . Traversing to count the range costs ; scanning to verify contiguity or ownership also costs time. Constant-time boundary rewiring is therefore not a promise that a fully validated, size-maintaining arbitrary-range API takes constant time. Such a claim needs the length already available or additional supporting structure. The implementation above moves one node, whose contribution to size is known to be one.
Worked example 10.1.6
(Moving a two-node range between lists)
Let be with nodes and sentinel , and let be with node and sentinel . Move the range from to before . Cutting the source connects , so . The destination neighbor is ; connect and , so . That is six writes: n1.next, n4.prev, m.next, n2.prev, n3.next, r_B.prev. With the sizes change from to , and was found by walking from to , which costs .
For the edge case in one list, move the same range before its old next node . After the cut , and is recomputed, so connecting and restores .
Exercises and worked solutions
Quick check
(Insert into the empty ring without an end-case rule)
The sentinel's two links point to itself. Insert a new node x before it. Give the next and previous references of both nodes. Would a data value of None make x a sentinel?
Solution · Answer
Both sentinel links point to , and both links of point to the sentinel. The stored size becomes one. A None data value does not make the sentinel: the sentinel is the particular root object, recognized by identity.
Quick check
(Follow a handle through the worked transfers)
After moving q to B and then before p in A, what are both sequences and sizes? After erasing p, what does its still-held handle refer to, and may it be erased from A again under the contract?
Solution · Answer
The transfers leave , and sizes three and one. Erasing changes to and size two. The handle still names the detached node containing 4, with both links None; it is no longer a member, so another erasure from violates the precondition.
Quick check
(Recognize the two single-node no-op cases)
Why are moving x before itself and moving x before its current next node no-ops within one list? If the latter case were handled by detach/attach, why would caching anchor.prev before detachment be dangerous?
Solution · Answer
The requested position already matches the current order in both cases. If the anchor is itself, it would be detached and no longer a valid destination anchor. If it is the next node, its old previous reference is , which is being detached; reusing that cached reference can connect through the removed node rather than the remaining ring. Detect the no-ops first and recompute destination neighbors after removal for real moves.
Quick check
(Identify what reciprocal pointers fail to prove)
Two disjoint circular components each satisfy next.prev and prev.next reciprocity. Why is this insufficient to show that they form one list with a specified sentinel? Which representation condition supplies the missing fact?
Solution · Answer
The equations describe local inverse connections but do not show that the sentinel can reach all intended members. The single-cycle reachability condition requires traversal from the sentinel to visit every data member exactly once before returning, with the stored size matching that set. A disconnected second component violates this global condition.
Quick check
(Compare a known handle with an indexed position)
An erasure changes two neighboring links in constant time. Does that make erasing the middle element by its numerical index constant-time in a bare linked list? State the nearer-end search bound for a valid zero-based index k.
Solution · Answer
No. The node must first be found unless a handle is already supplied. For length and , nearer-end traversal costs , which is in the middle. Only the subsequent local erasure is constant pointer work.
Quick check
(Distinguish range rewiring from size maintenance)
A known contiguous range is moved between two lists with stored sizes. Its endpoint links can be rewired with six writes. What additional number is needed to update sizes, and what happens to the time bound if it must be found by traversal?
Solution · Answer
The exact range length is needed: subtract it from the source size and add it to the destination size. Counting the range by traversal takes , despite constant boundary rewiring. Endpoint handles alone do not make that count available in constant time.