How it works
A doubly linked list adds a backward reference, which makes removal constant time given only a node reference, at the cost of memory and bookkeeping.
Choose doubly linked when removal by reference or backward traversal is needed.
Common error
Forgetting to update both directions on a modification, which corrupts the list silently.
Worked example
Example
Singly linked: value + next
Doubly linked: previous + value + next
Known doubly linked node: can update both neighbors
Find a value: still may require a scanA doubly linked list spends extra space and update work on backward links. It can remove a known node locally when the necessary references are available; searching for that node still costs time.
Exercises
3.3.1 · Explain
Which links must be updated when removing an interior doubly linked node x?
Show solution
Connect x.previous.next to x.next and x.next.previous to x.previous, with separate handling for boundaries and any sentinel conventions.
3.3.2 · Explain
Does adding previous references make searching an unsorted linked list logarithmic?
Show solution
No. Without an additional indexing structure, locating a value still requires a linear scan in the worst case.