Linked list

push-front O(1) · search O(n)

A (singly) linked list stores each value in a node that points to the next one, with a head pointer at the front. Adding or removing at the head is O(1) — just relink a pointer — but there's no random access: finding the k-th element or a value means walking the chain from the head, which is O(n). Linked lists underlie stacks, queues, adjacency lists, and more.

Linked list
Press ▶ to run
Edit the input and press Play

How it works

  1. pushFront makes a new node point to the old head, then moves the head to it (O(1)).
  2. pushBack walks to the tail and links the new node on.
  3. search walks from the head, comparing each node until it matches or hits null.
  4. remove walks to the matching node and relinks its predecessor past it.

Pseudocode

1pushFront(v):  node.next ← head; head ← node      # O(1)2pushBack(v):   walk to the tail, link the new node # O(n)34search(v):5  cur ← head6  while cur ≠ null:7    if cur.value = v: return cur8    cur ← cur.next                                  # O(n)910remove(v):  relink the predecessor past the match