Build fluency in the vocabulary of a linked list whose nodes track both a previous and a next neighbor.
0 / 5 completed
1 / 5
At standup, a dev mentions a linked list where every node holds pointers to both its next and its previous neighbor, letting the list be traversed forward or backward and letting a node be removed in constant time given just a reference to it. What is this structure called?
Doubly linked list is exactly this: a doubly linked list is a linked list where every node holds a pointer to both its next and its previous neighbor, letting the sequence be traversed in either direction and letting any node be removed in constant time given just a reference to that node, since both its neighbors are immediately reachable. A hash collision is an unrelated hash-table concept about two keys sharing a bucket. This both-directions-plus-instant-removal capability is exactly why a doubly linked list is preferred whenever backward traversal or O(1) removal of an arbitrary known node matters.
2 / 5
During a design review, the team picks a doubly linked list for an LRU-cache-style structure that needs to remove an arbitrary known node instantly, specifically because having both a previous and a next pointer on every node lets any node be unlinked in constant time without walking the list to find its neighbors. Which capability does this provide?
Doubly linked list here provides Constant-time removal of any node given just a reference to it, since since every node already stores pointers to both its previous and next neighbor, removing a known node only requires relinking those two neighbors directly to each other, with no need to walk the list to find them first. A singly linked list has no previous pointer, so removing a known node still requires walking from the head to find the node just before it. This instant-removal-of-a-known-node capability is exactly why a doubly linked list underlies structures like an LRU cache that must evict an arbitrary tracked node quickly.
3 / 5
In a code review, a dev notices an LRU-cache-style feature needs to remove an arbitrary, already-known node instantly on every access, but stores its entries in a singly linked list, which must walk from the head to find the node just before the one being removed. What does this represent?
This is a missed doubly-linked-list opportunity, since using a doubly linked list, where every node already stores both a previous and a next pointer, would let that same known node be removed in constant time without walking the list at all. A cache eviction policy is an unrelated concept about discarded cache entries. This walk-to-find-the-predecessor pattern is exactly the kind of avoidable cost a reviewer flags once removal always targets an already-known, tracked node.
4 / 5
An incident report shows an LRU-cache-style feature's eviction step slowed down as the cache grew, because it stored entries in a singly linked list and had to walk from the head to find a known node's predecessor before removing it. What practice would prevent this?
Switching the entries to a doubly linked list eliminates the need to walk the list to find a predecessor. Continuing to walk a singly linked list from the head to find a known node's predecessor before removing it regardless of how large the cache grows is exactly what caused the issue described in this incident. This doubly-linked-list approach is the standard fix whenever a structure repeatedly needs to remove an already-known, tracked node in constant time.
5 / 5
During a PR review, a teammate asks why the team reaches for a doubly linked list instead of a singly linked list, given that a singly linked list uses less memory per node since it only stores one pointer. What is the reasoning?
A doubly linked list's extra previous pointer on every node enables constant-time removal of a known node and traversal in either direction, at the cost of extra memory and pointer-maintenance bookkeeping per node, while a singly linked list uses less memory per node but must walk from the head to find a node's predecessor before removing it. This is exactly why a doubly linked list is favored whenever known-node removal or backward traversal genuinely matters.