Quiz Entry - updated: 2026.09.29
What is a doubly-linked list, and what does it cost compared to a singly-linked one?
Each node stores a reference to its predecessor (prev) as well as its successor (next), so the list can be walked and edited in both directions; the price is one extra reference per node.
* Every link has a partner in the opposite direction, so any node can reach both neighbours. *
A singly-linked list forces you to start at the head and only ever move forwards. The doubly-linked list removes that limitation:
| Singly-linked | Doubly-linked | |
|---|---|---|
| Links per node | next |
next and prev |
| Walk direction | forwards only | both ways |
| Remove the last node | $O(n)$ — must find the predecessor | $O(1)$ — tail.prev is right there |
| Insert before a given node | $O(n)$ | $O(1)$ |
| Memory per node | element + 1 reference | element + 2 references |
The extra reference per node is the whole cost, and for most uses it is a good trade. Java's LinkedList is doubly-linked for exactly this reason.
Go deeper:
Doubly linked list — insertion and removal pseudo-code for both ends and the middle.