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 walk straight to locker #47 because you know exactly where it sits. A linked list is a scavenger hunt: each clue tells you the next clue's location, but never all of them. To find the fifth clue you must have already found the first four; there is no locker number to jump to.
Each stop is a node: a value plus a pointer — the address of the next node, or NULL if the hunt ends. The list itself only remembers where the hunt starts: a pointer called head. Lose the head and the whole chain is unreachable, 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 old start (may be NULL — that's fine)
list.head = newNode // 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 — 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 // deleting the head moves 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 we overwrite curr.next
curr.next = prev // flip the arrow backward
prev = curr
curr = nextNode
list.head = prev // 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 // walks 1 step
fast = fast.next.next // walks 2 steps
if slow == fast:
return true // fast lapped slow — must be a loop
return false // fast hit NULL — the chain has an endThe pattern to memorize: anything that only touches the head is O(1). Anything that has to walk to find a spot is O(n). Nothing here ever needs more than a handful of pointers, so space is O(1) across the board.
| Operation | Time | Space | Why |
|---|---|---|---|
| Insert at head | O(1) | O(1) | Rewrite one pointer. Never touches the rest of the chain. |
| Insert at tail | O(n) | O(1) | Must walk to the last node first — unless the list keeps a separate tail pointer, which drops this to O(1) too. |
| Search / access by value | O(n) | O(1) | No index to jump to — you must follow pointers from head, one node at a time. |
| Delete by value | O(n) | O(1) | Finding the node is O(n); once found, unlinking it is O(1). |
| Reverse whole list | O(n) | O(1) | Visit each node exactly once, flip its arrow, move on. |
| Cycle detection | O(n) | O(1) | Two pointers at different speeds meet within one lap of the cycle — no extra memory needed to remember visited nodes. |
Empty
Every operation's first check: delete-from-empty, search-in-empty, reverse-an-empty-list must all return cleanly instead of dereferencing a node that doesn't exist.
Single node
Deleting the only node means the list must become empty again — head itself has to change, not just some node's pointer. Common bug: code that only ever edits prev.next and never handles "there is no prev."
Value not found
Search and delete must terminate on NULL, not just "when found." Forgetting the NULL check turns a missing value into a crash instead of a clean "not found."
Cycle
next never becomes NULL, so a plain while-loop search runs forever — exactly why Floyd's slow/fast pointer exists: two walkers at different speeds are guaranteed to meet if a loop exists, with no extra memory.
Sign in to mark problems done — progress syncs across devices.