You have a pointer to a node in the middle of a list and need to delete it. The operation is O(n) for a singly linked list but O(1) for a doubly linked list. What makes the difference?
ADoubly linked lists store sorted data, enabling binary search for the predecessor
BEach node's `prev` pointer gives immediate access to the predecessor, which is all you need to relink the list
CDoubly linked lists use arrays internally, making deletion index-based and faster
DDoubly linked lists avoid the need to update any pointers during deletion
To delete a node, you must update the predecessor's `next` pointer to skip the deleted node. In a singly linked list, finding the predecessor requires traversing from the head — O(n). In a doubly linked list, `node.prev` is the predecessor directly, so you access it in O(1). You then set `node.prev.next = node.next` and `node.next.prev = node.prev`. The `prev` pointer doesn't eliminate the pointer update — it eliminates the search for which node to update.
Question 2 Multiple Choice
How many pointer connections must be updated when inserting a new node into the middle of a doubly linked list?
A1 — only the new node's `next` pointer
B2 — the new node's `next` and the predecessor's `next`
C4 — the new node's `prev` and `next`, plus the predecessor's `next` and the successor's `prev`
D6 — the new node plus all three neighbors' pointers in both directions
Inserting node N between nodes A and B requires: (1) N.next = B, (2) N.prev = A, (3) A.next = N, (4) B.prev = N. That is 4 pointer updates. A singly linked list insertion requires only 2. The doubled update count is the direct cost of the extra flexibility. Missing any of the four — especially on boundary cases — is the primary source of bugs in doubly linked list implementations.
Question 3 True / False
Deleting a node in a doubly linked list, given only a pointer to that node, can be done in O(1) time.
TTrue
FFalse
Answer: True
This is the central advantage of doubly linked lists. With `node.prev` and `node.next` available in O(1), you can rewire the surrounding nodes directly: set `node.prev.next = node.next` and `node.next.prev = node.prev`. No traversal needed. This property makes doubly linked lists the natural choice for LRU caches, where you need to remove an arbitrary node immediately upon a cache hit — singly linked lists cannot do this in O(1).
Question 4 True / False
Doubly linked lists are strictly superior to singly linked lists because the back pointer enables faster operations across the board.
TTrue
FFalse
Answer: False
Doubly linked lists improve only specific operations — primarily arbitrary deletion and backward traversal. Many operations (searching for a value, accessing the k-th element) still cost O(n) because the structure is still a linked chain. Additionally, doubly linked lists consume more memory per node and require more pointer updates per insertion/deletion, increasing the chance of bugs. The right choice depends on the use case: if you need O(1) arbitrary deletion, use doubly linked; if memory is tight or you only traverse forward, singly linked may be better.
Question 5 Short Answer
Why are sentinel nodes useful in doubly linked list implementations, and what problem do they solve?
Think about your answer, then reveal below.
Model answer: Sentinel nodes are dummy head and tail nodes that are always present, even in an empty list. They eliminate special-case handling for insertions and deletions at the boundaries. Without sentinels, you must check whether the node being deleted is the head or tail before updating list pointers. With sentinels, every real node always has a valid `prev` and `next` (pointing to the sentinel at a boundary), so the same four-pointer update works for all positions uniformly. The empty list is simply the two sentinels pointing to each other.
Sentinel nodes exemplify a broader principle: adding a small amount of overhead (two extra nodes) to eliminate disproportionately complex special-case code. Fewer code paths means fewer bugs. Real-world implementations including Python's `collections.deque` and the Linux kernel's `list_head` use this pattern for exactly this reason.