DLL Time Complexity
Bounds below assume a classic non-circular doubly linked list with head and tail pointers, as in this tutorial’s code. n is the number of nodes. “Extra space” means auxiliary pointers beyond the list itself.
Time (worst case)
| Operation | Time | Notes |
|---|---|---|
| Insert at front / back | O(1) |
With head + tail. |
| Delete at front / back | O(1) |
tail->prev makes delete-at-end cheap (vs singly linked). |
| Insert / delete at index | O(n) worst |
Walk from head (or optimize if index known). |
| Search by value | O(n) |
Linear scan unless sorted + extra structure. |
Access by index i |
O(n) |
No random access like arrays. |
Auxiliary space
| Operation | Extra space |
|---|---|
| Typical iterative insert/delete | O(1) |
| Storing the list | O(n) nodes; DLL uses ~2× pointer fields vs SLL |
For general linked-list analysis (arrays vs lists, merge, etc.), see Time Complexity (Linked List). For SLL vs DLL trade-offs, see SLL vs DLL.
Key takeaway
The main asymptotic win for DLL over SLL—when both use head and tail—is often delete at the end in O(1) instead of O(n). Middle inserts/deletes still need you to reach the position first unless you already hold the right pointers.