Time Complexity of Linked List Operations
Below, n is the list length (or current size). Auxiliary space means extra memory besides the structure itself (not counting the nodes or array slots already storing data). Unless stated otherwise, the linked list column assumes a singly linked list and a pointer to the head only—matching the usual C tutorial setup. Compare with a contiguous dynamic array (e.g. “vector” style: indexable block, amortized growth).
Related: Linked List vs Arrays · Introduction · Doubly linked list (changes some bounds).
Time & auxiliary space: linked list vs array
| Operation | Linked list — time | Linked list — aux space* | Array — time | Array — aux space* | Notes |
|---|---|---|---|---|---|
Access i-th element |
O(n) |
O(1) |
O(1) |
O(1) |
List: walk from head. Array: base address + index. |
| Traversal / print all | O(n) |
O(1) |
O(n) |
O(1) |
Visit every element once. |
| Search (unsorted) | O(n) |
O(1) |
O(n) |
O(1) |
Linear scan. |
| Search (sorted) | O(n) |
O(1) |
O(log n) |
O(1) |
Array allows binary search; singly list has no random access for bisection. |
| Insert at beginning | O(1) |
O(1) |
O(n) |
O(1) |
Array must shift all elements (unless extra front bookkeeping). |
| Insert at end | O(n) no tailO(1) with tail |
O(1) |
O(1) amortized |
O(1) |
List: walk to last node without tail pointer. Array push back with growth policy. |
| Insert at index / middle | O(n) |
O(1) |
O(n) |
O(1) |
List: O(n) to reach position, O(1) splice. Array: shift tail. |
| Delete from beginning | O(1) |
O(1) |
O(n) |
O(1) |
Array shifts remaining elements forward. |
| Delete from end | O(n) |
O(1) |
O(1) |
O(1) |
Singly list: need predecessor of last node. Array: pop back. |
| Delete at index / middle | O(n) |
O(1) |
O(n) |
O(1) |
List: find node then unlink. Array: shift. |
| Length / count | O(n) or O(1) if stored |
O(1) |
O(1) |
O(1) |
Often arrays track size; lists may count on demand. |
| Reverse (iterative) | O(n) |
O(1) |
O(n) |
O(1) |
In-place pointer rewiring vs two-index swap. |
| Reverse (recursive) | O(n) |
O(n) |
O(n) |
O(n) |
Call stack depth n (risk of overflow on huge n). |
| Find middle (slow/fast) | O(n) |
O(1) |
O(1) |
O(1) |
Array: middle index = n/2 without a walk. |
| Cycle detection (Floyd) | O(n) |
O(1) |
— | — | Classic arrays don’t have “next” cycles; relevant for list graphs. |
| Remove duplicates (sorted) | O(n) |
O(1) |
O(n) |
O(1)–O(n) |
Array in-place unique often shifts; extra array O(n). |
| Remove duplicates (unsorted) | O(n) hash |
O(n) |
O(n) hash / sort |
O(n) |
Hash set of seen values; sort-first changes time. |
| Merge two sorted | O(n + m) |
O(1) |
O(n + m) |
O(n + m) |
List: relink in place. Array merge usually needs output buffer. |
* Auxiliary space excludes the O(n) storage of the elements themselves (nodes + pointers vs contiguous cells). Per-operation allocation of one new node counts as O(1) extra.
Overall storage (the structure)
| Structure | Space for n elements |
Comment |
|---|---|---|
| Singly linked list | O(n) |
Each node: payload + one pointer (plus allocator metadata outside your struct). |
| Doubly linked list | O(n) |
Two pointers per node → more overhead than singly. |
| Dynamic array | O(n) often n to 2n capacity |
Contiguous; may reserve extra slots for amortized append. |
How to read the table
- Worst case is shown unless “amortized” is stated (array push).
- Linked list insert/delete after you already have a pointer to the right place is
O(1)for the pointer work; finding that place by index is stillO(n). - Doubly linked list with
tailcan delete the last node inO(1); singly cannot without extra tricks.