Exercises — Doubly linked list — bidirectional traversal

Picture the chain: head → node(5) → node(8) → node(13) ← tail.

• head.prev = None (nothing sits before the first node — that is what "first" means).
• head.next.data = 8 (head is node 5; its next is node 8).
• tail.next = None (nothing sits after the last node).
• tail.prev.data = 8 (tail is node 13; its prev is node 8).

True. Set $x=$ head (node 5). The invariant says $x.next.prev=x$. Here head.next is node 8, and node 8's prev is node 5, which is exactly head. So head.next.prev == head holds. This is the invariant doing its job: stepping forward one door and then backward one door lands you exactly where you started.

Forward starts at head (node 2) and follows next until None: 2 → 4 → 6 → 8 → None (stop). Output: 2 4 6 8. Backward starts at tail (node 8) and follows prev until None: 8 → 6 → 4 → 2 → None (stop). Output: 8 6 4 2. Notice the backward output is the forward output reversed — because prev walks the exact same chain the other way.

The body runs once per node = 4 times (for nodes 2, 4, 6, 8). The condition is checked once before each body run plus one final time that fails: 5 evaluations. The 5th check is cur is not None when cur = None (after stepping off node 8), which is False and ends the loop. That extra final check is the "clean stop" — it is not an off-by-one bug, it is the design.

Apply insert_after(node, new) with node = 4, new = 5:

1. new.prev = node → 5.prev = 4.
2. new.next = node.next → 5.next = 6.
3. node.next is not None? Yes (4.next was 6), so:
4. node.next.prev = new → 6.prev = 5.
5. node.next = new → 4.next = 5.

Now the chain reads 2 ⇄ 4 ⇄ 5 ⇄ 6 ⇄ 8. Forward output: 2 4 5 6 8. Invariant check on the new node: 5.next.prev = 6.prev = 5 ✓ and 5.prev.next = 4.next = 5 ✓.

Look at the figure below. The moment we run node.next = new, the pointer from node 4 that used to reach node 6 is overwritten — it now points to node 5. But we never saved node 6's address anywhere, and node 5's next was never set to 6.

So when the code then runs node.next.prev = new, node.next is now node 5, not node 6. We set 5.prev = 5 (nonsense, a node pointing back to itself), and node 6 is now orphaned: nothing's next reaches it going forward. Forward traversal would produce 2 4 5 and then loop or stop early. Node 6 becomes unreachable from the head. This is exactly why the parent rule is "attach the new node before detaching the old links."

Forward uses only next pointers, and none of those were touched, so traverse_forward still prints 2 4 6 8 correctly. Backward from tail (node 8) follows prev: 8 → 6 → then 6.prev is None, so the loop stops. Output: 8 6 — it silently drops nodes 4 and 2. Lesson: a one-sided break is invisible to traversal in the other direction, which is why one-sided edits are so dangerous — the bug hides until someone walks the affected direction.

A prev pointer gives exactly one step back per follow, each in $O(1)$. To go back 3 nodes you must follow prev three times: cur = cur.prev; cur = cur.prev; cur = cur.prev. That is $3$ constant-time steps = $O(1)$ for a fixed constant 3, yes — but the claim quietly implies arbitrary jumps are free. Going back $k$ nodes costs $O(k)$; going back to the head from the tail costs $O(n)$. There is no random access (that is an array's power, see Linked List vs Array). The confusion mixes "one cheap step" with "cheap arbitrary jump."

The idea: reconnect the two neighbours around the node so the chain skips it. Handle the ends specially because a missing neighbour is None.

def delete_node(node, head, tail):
    # link the left neighbour forward past `node`
    if node.prev is not None:
        node.prev.next = node.next
    else:
        head = node.next          # node was the head
 
    # link the right neighbour backward past `node`
    if node.next is not None:
        node.next.prev = node.prev
    else:
        tail = node.prev          # node was the tail
 
    node.prev = node.next = None  # optional: fully detach
    return head, tail

Why two ifs? Each boundary has a neighbour that might be None. When node.prev is None, there is no left neighbour to fix — instead the head itself moves to node.next. Symmetrically for the tail. Both branches touch two links total across the gap so the invariant $x.next.prev=x$ holds for the reconnected pair.

• (a) Middle node 6 in 2 ⇄ 4 ⇄ 6 ⇄ 8: 4.next = 8, 8.prev = 4. Result 2 ⇄ 4 ⇄ 8.
• (b) Head 2: node.prev is None, so head = 4; then 4.prev = None. Result 4 ⇄ 6 ⇄ 8.
• (c) Tail 8: node.next is None, so tail = 6; then 6.next = None. Result 2 ⇄ 4 ⇄ 6.

Walk left forward and right backward simultaneously; compare data; stop when they meet or cross.

def is_palindrome(head, tail):
    left, right = head, tail
    while left is not right and left.prev is not right:
        if left.data != right.data:
            return False
        left = left.next          # step inward from the front
        right = right.prev        # step inward from the back
    return True

Why two stop conditions? left is right catches an odd length (pointers land on the same middle node — nothing left to compare). left.prev is right catches an even length (pointers cross without meeting; the last valid pair was already compared). Missing either lets the loop run past the middle and re-compare pairs (harmless for correctness but wasteful) or, worse for a sloppy version, run off the end.

• 1 ⇄ 2 ⇄ 1 → compares (1,1), then left=2 right=2 are equal, left is right → stop → True.
• 1 ⇄ 2 ⇄ 3 ⇄ 1 → compares (1,1) OK, then (2,3) → False.
• Cost: each node is visited at most once from one side ⇒ $O(n)$ time, $O(1)$ extra space (just two pointers). This $O(1)$ space is the DLL advantage over a singly list, which needs an $O(n)$ stack or a full reversal to compare from the back.

"Move to front" = delete the node from its current spot, then insert it at the head.

• Deletion needs to splice the node's two neighbours together: node.prev.next = node.next and node.next.prev = node.prev. In a DLL you already hold node.prev and node.next, so this splice is $O(1)$.
• In a singly list you have next but no prev. To rewire the predecessor's next, you must first find the predecessor by walking from the head — $O(n)$. So each move is $O(n)$ there.
• Insertion at head is $O(1)$ in both.

Verdict: move-to-front is $O(1)$ in a DLL, $O(n)$ in a singly list. The prev pointer is the predecessor you would otherwise have to search for — that is precisely why real LRU caches and Browser History use doubly linked lists. See Big-O Notation for why an $O(1)$-per-touch structure matters when touches happen millions of times.

The condition cur is not None is never satisfied to stop, because following next now loops 4 → 6 → 8 → 4 → 6 → 8 → … forever — no node's next is ever None. The loop is infinite; cost is unbounded (∞), not $O(n)$. This is the danger of a broken invariant: 8.next = 4 but 4.prev is still node 2, so 8.next.prev = 4.prev = 2 ≠ 8 — the invariant is violated and would have flagged the bug. A cycle-safe traversal would need a visited-set or Floyd's two-pointer method, but the real fix is to never break the invariant in the first place.

• Forward traversal: visits all $n$ nodes once ⇒ $O(n)$.
• Backward traversal: visits all $n$ nodes once ⇒ $O(n)$.
• $k$ single-step back operations: each is $O(1)$ (follow prev once) ⇒ $O(k)$ total.

Total: $O(n)+O(n)+O(k)=O(n+k)$. We do not write $O(n^2)$ or $O(nk)$: the traversals are linear (constant work per node), and the $k$ steps are constant each, so they simply add. If instead each "go back" had to restart from the head (a singly list), each would be $O(n)$ and the last term would balloon to $O(nk)$ — the whole point of prev.