What is the primary memory-related advantage of a doubly linked list over a singly linked list?

• A. They use less memory due to extra pointers.
• B. They allow faster random access.
• C. They can be inserted at the head in O(1) without extra pointers.
• D. They enable O(1) deletion of a given node and bidirectional traversal, at the cost of extra memory for the prev pointer per node.

Answer: (D)

The key idea here is that having a previous pointer in each node gives the doubly linked list both backward traversal and the ability to remove a known node in constant time. With a prev pointer, you can unlink a node by updating its neighbor’s links directly: you adjust the next pointer of the previous node and the prev pointer of the next node, all without scanning from the head. That makes deletion of a given node happen in O(1) time, provided you have a reference to the node itself. The ability to move in both directions—forward and backward—from any position also stems from having that extra link. Of course, this comes with a memory cost: every node stores an additional pointer, so the list uses more memory than a singly linked list.

Options that claim less memory or faster random access are not accurate: extra pointers in a doubly linked list increase memory, random access in linked lists remains O(n), and inserting at the head is O(1) in both kinds of lists, but the distinctive advantage here is the combination of O(1) deletion of a known node and bidirectional traversal enabled by the prev pointer.