Noesis
3.2.3 · D5Linear Data Structures

Question bank — Doubly linked list — bidirectional traversal

1,779 words8 min read↑ Back to topic

Before we start, three words are used constantly below, so we pin them down first (never a symbol before its meaning):

True or false — justify

Each item: decide true/false, then why. The "why" is the whole point.

A DLL lets you jump to the middle node in like an array does.
False. A DLL has no index arithmetic — you still walk node-by-node from head or tail, so reaching the middle is . Only neighbour access (one step either way) is . See Linked List vs Array.
Having a prev pointer makes backward traversal of the whole list .
False. prev gives one step back in , but visiting all nodes backward still touches each node once ⇒ . Cheap per step is not cheap overall.
The prev of the head and the next of the tail are both null.
True. The head has nothing before it and the tail nothing after it; those nulls are the signals that let a while cur is not None loop stop cleanly at either end.
A DLL always uses more memory per node than a singly linked list.
True. Each node stores an extra pointer (prev), costing extra space overall — the price you pay for two-way movement.
If head is None, the list is empty and both traversals immediately do nothing.
True. The loops start with cur = head = None, so while cur is not None is false on the first check — zero iterations, no crash. This is the correct degenerate case.
You can reverse a DLL's logical order just by swapping the head and tail pointers and reading via prev.
True in effect for reading, but a real "reverse" must swap each node's next/prev. Reading tail→head via prev already gives reversed output for free; only if you want future forward traversals reversed do you rewrite the pointers.
The invariant must hold even when is the tail.
False (vacuously). The tail's next is None, so x.next.prev doesn't exist — the invariant only applies "when those neighbours exist." The tail is exempt on the next side.
Deleting a node in the middle of a DLL is if you already hold a pointer to that node.
True. You just relink its two neighbours to each other — constant work — because prev gives you the left neighbour without a search. Without the pointer, finding the node first is .
A Circular Doubly Linked List has a node whose next is null.
False. In a circular DLL the tail's next loops back to the head and the head's prev points to the tail — there is no null end, which changes every stop-condition.

Spot the error

Each snippet has one flaw. Name it and give the fix.

while cur.next is not None: visit(cur.data); cur = cur.next — asked to print all nodes.
Skips the last node. The loop exits before visiting the node whose next is None. Fix: use while cur is not None. (while cur.next is not None is only correct when you deliberately want to stop at the tail, e.g. to find it.)
insert_after: node.next = new; new.next = node.next (setting node.next first).
Loses the old successor. After node.next = new, the pointer to the old next node is gone, so new.next = node.next just points new back at itself. Fix: attach before you detach — wire new.prev and new.next from the old links first, rewrite node.next last.
On delete, code does node.prev.next = node.next but forgets node.next.prev = node.prev.
Breaks the invariant on one side. Forward traversal skips the node correctly, but backward traversal still walks into the deleted node via its old prev link. Every boundary needs both links updated.
Backward traversal written as cur = head; while cur is not None: visit(cur.data); cur = cur.prev.
Prints one node then stops. head.prev is None, so the loop ends after the first node. Backward traversal must start at tail (or walk to the end first if no tail is stored).
Inserting into an empty list, code sets new.prev = node where node is the (nonexistent) head.
Null dereference / wrong wiring. With an empty list there is no node to insert after; the empty case must be handled separately by setting head = tail = new and both its pointers to None.
node.next.prev = new executed without checking node.next is not None.
Crashes when node is the tail. If node.next is None, dereferencing .prev fails. Fix: guard with if node.next is not None and, in the else branch, update tail = new.

Why questions

Why does a DLL make an LRU Cache eviction while a singly list does not?
Eviction removes the least-recently-used node at the tail; with prev you unlink the tail and reach the new tail in . A singly list would need an walk from the head to find the node before the tail.
Why can Browser History "back" be with a DLL but awkward with a singly list?
"Back" means step to the previous page — exactly what the prev pointer gives in one hop. A singly (forward-only) list would have to re-traverse from the start to find the predecessor.
Why must every structural edit in a DLL touch two pointers per boundary?
Because each link is stored twice — once as the left node's next and once as the right node's prev. Updating only one side leaves the invariant broken, so one traversal direction lies.
Why is storing a tail pointer not required for backward traversal, only helpful?
The prev pointers do the real backward work; without tail you first walk forward to the end () then back (), still total. tail merely skips the forward walk — a constant-factor saving, not a complexity change.
Why does forward traversal use cur = cur.next but backward uses cur = cur.prev — can't we just "reverse" one loop?
They follow physically different pointers. The forward loop rides the next chain from head; the backward loop rides the prev chain from tail. You cannot reverse a loop's direction without switching which pointer it dereferences and where it starts.
Why is the check cur is not None (rather than checking the data value) the correct stopping rule?
Because a data value could legitimately be anything (including a repeat or a sentinel), but None is structurally guaranteed only at the ends. Stopping on None is the one condition that is always exactly "no more nodes."

Edge cases

For a single-node list (head == tail), what are that node's prev and next?
Both are None — it is simultaneously the head (nothing before) and the tail (nothing after). Both traversals visit it exactly once and stop.
Deleting the only node of a one-node list — what must be updated besides unlinking?
Set head = None and tail = None, because after deletion the list is empty and no stale pointers may remain, or later operations will dereference a freed node.
Inserting after the current tail — which extra bookkeeping is required?
You must also update the tail pointer to the new node, since the new node is now the last; skipping this leaves tail pointing at the old last node and corrupts future backward traversals.
Traversing an empty list backward from tail — what happens?
tail is None, so while cur is not None is false immediately: zero iterations, no output, no error. Empty is a valid, safe case both directions.
In a two-node list A ⇄ B, does deleting A require the node.next is not None guard?
Yes on A's successor side: A.next is B (exists), so A.next.prev is set to None, making B the new head. The guard matters precisely because whether a neighbour exists differs at the boundaries.
What is the difference between a DLL and a Circular Doubly Linked List at the traversal-stop boundary?
A plain DLL stops on None at each end; a circular DLL has no None end, so a naive while cur is not None loops forever — you must instead stop after returning to the starting node.
Compared to a Singly Linked List, what single structural fact removes the need to ever restart from the head to go back?
The prev pointer: every node records its predecessor, so "go back one" is a direct hop instead of an re-walk from the head.
Recall One-line summary of the traps

Constant-time is per neighbour step, never whole-list; every edit updates two links per boundary; stop on None (except circular lists); and always handle empty / single-node / tail-boundary cases explicitly.

Connections

  • Parent: Bidirectional traversal — the mechanics these traps probe.
  • Singly Linked List — the one-way baseline every "why prev" trap contrasts against.
  • Linked List vs Array — grounds the "no random access" traps.
  • Big-O Notation — the language of every complexity trap here.
  • LRU Cache · Browser History — real systems the "why " questions come from.
  • Circular Doubly Linked List — the boundary-condition contrast for stop rules.