Linked List

Insertion, deletion and search on a singly linked list. Every operation has to walk from the head, so the cost is dominated by traversal — relinking itself is a single pointer write. Watching the cursor step node by node is the clearest argument for why arrays and lists trade off the way they do.

Best

O(1)

Average

O(n)

Worst

O(n)

Space

O(n)