Singly Linked List
Quick reference
| Insert at head | O(1) |
| Insert at tail | O(n) |
| Search / access by value | O(n) |
| Delete by value | O(n) |
| Reverse whole list | O(n) |
| Cycle detection | O(n) |
An array is a row of numbered lockers. You can go directly to locker #47, because you know exactly where it is. A linked list is a scavenger hunt. Each clue tells you the location of the next clue, but no clue tells you all the locations. To find the fifth clue, you must already have the first four clues. There is no locker number to jump to.
Each stop is a node: a value plus a pointer. The pointer is the address of the next node, or NULL if the hunt ends. The list itself remembers only where the hunt starts. This is a pointer called head. If you lose the head, you cannot reach the chain, even though every node still exists in memory.
Structures
structure Node:
value
next // -> another Node, or NULL
structure LinkedList:
head // -> first Node, or NULL if emptyinsertAtHead — O(1)
function insertAtHead(list, value):
newNode = Node(value)
newNode.next = list.head // point at the old start (it may be NULL, which is fine)
list.head = newNode // the new node becomes the startinsertAtTail — O(n) without a tail pointer
function insertAtTail(list, value):
newNode = Node(value)
if list.head is NULL: // empty list: the new node is the list
list.head = newNode
return
curr = list.head
while curr.next is not NULL: // walk until curr is the last node
curr = curr.next
curr.next = newNodedeleteValue — first match, O(n)
function deleteValue(list, target):
if list.head is NULL:
return // nothing to delete
if list.head.value == target:
list.head = list.head.next // to delete the head, move head forward
return
prev = list.head
while prev.next is not NULL:
if prev.next.value == target:
prev.next = prev.next.next // skip over the target node
return
prev = prev.nextreverse — O(n) time, O(1) space
function reverse(list):
prev = NULL
curr = list.head
while curr is not NULL:
nextNode = curr.next // save it before you overwrite curr.next
curr.next = prev // turn the arrow backward
prev = curr
curr = nextNode
list.head = prev // the old tail is the new headhasCycle — Floyd's slow/fast pointer, O(n) time, O(1) space
function hasCycle(list):
slow = list.head
fast = list.head
while fast is not NULL and fast.next is not NULL:
slow = slow.next // moves 1 step
fast = fast.next.next // moves 2 steps
if slow == fast:
return true // fast caught slow, so there is a loop
return false // fast reached NULL, so the chain has an endMemorize this pattern. Any operation that touches only the head is O(1). Any operation that must walk to find a position is O(n). Nothing here needs more than a few pointers, so space is O(1) for all operations.
| Operation | Time | Space | Why |
|---|---|---|---|
| Insert at head | O(1) | O(1) | You rewrite one pointer. You never touch the rest of the chain. |
| Insert at tail | O(n) | O(1) | You must walk to the last node first. But if the list keeps a separate tail pointer, this drops to O(1) too. |
| Search / access by value | O(n) | O(1) | There is no index to jump to. You must follow the pointers from the head, one node at a time. |
| Delete by value | O(n) | O(1) | To find the node is O(n). After you find it, to unlink it is O(1). |
| Reverse whole list | O(n) | O(1) | You visit each node exactly one time, turn its arrow, and continue. |
| Cycle detection | O(n) | O(1) | Two pointers at different speeds meet within one lap of the cycle. You need no extra memory to remember visited nodes. |
Empty
This is the first check of every operation. A delete from an empty list, a search in an empty list, and a reverse of an empty list must all return cleanly. They must not dereference a node that does not exist.
Single node
To delete the only node, the list must become empty again. The head itself must change, not only a pointer of some node. A common bug is code that only edits prev.next and never handles "there is no prev".
Value not found
A search and a delete must stop on NULL, not only "when found". If you forget the NULL check, a missing value becomes a crash instead of a clean "not found".
Cycle
next never becomes NULL, so a plain while-loop search runs forever. This is why the Floyd slow/fast pointer exists. Two walkers at different speeds always meet if a loop exists, with no extra memory.
Sign in to mark problems done — progress syncs across devices.