AlgoScope

Singly Linked List

structurebeginnerTime O(n)Space O(1)

Boxes joined by arrows. Nothing ever shifts, because every change is just an arrow letting go of one box and grabbing another.

5142currhead

To delete 4, walk with prev and curr until curr holds it.

Check your understanding

The player pauses before each decision in this run and asks what happens next. Here are all 3, with their answers.

  1. curr is 5. Is this the node to delete?

    • This one
    • Keep walking

    Answer: Keep walking. 5 is not 4, so prev and curr both advance.

  2. curr is 1. Is this the node to delete?

    • This one
    • Keep walking

    Answer: Keep walking. 1 is not 4, so prev and curr both advance.

  3. curr is 4. Is this the node to delete?

    • This one
    • Keep walking

    Answer: This one. 4 equals 4.

How it runs, step by step

  1. To delete 4, walk with prev and curr until curr holds it.

    Linked list 5, 1, 4, 2. Deleting 4.

  2. 5 is not 4: keep walking.

    Node 5 does not match 4; moving on.

  3. Shuffle all three along. prev follows curr, curr follows next.

    prev is now 5; curr is now 1.

  4. 1 is not 4: keep walking.

    Node 1 does not match 4; moving on.

  5. Shuffle all three along. prev follows curr, curr follows next.

    prev is now 1; curr is now 4.

  6. 4 is the target. prev is 1.

    Node 4 matches the target.

  7. Route 1's next around it, straight to 2.

    1's next now bypasses 4.

  8. Nothing points at 4 any more, so it is gone.

    4 removed. The list is 5, 1, 2.

  9. Deleted after 3 comparisons: finding is O(n), unlinking is O(1).

    Result: 4 deleted. The list is 5, 1, 2.

Remember

  • There is no index, so reaching position k costs k hops.
  • Insert after a node you already hold is O(1); deleting that node is not, because you need its predecessor.
  • When relinking, grab the successor before letting go of it, or the rest of the list is lost.

Topics covered

Related

Where this is used

Standard librariesBucket chains in java.util.HashMap

When two keys hash into the same bucket, HashMap keeps them as a chain of Node objects joined by a next field, and adding to one bucket touches nothing else in the table. A singly linked chain is the right shape because the only access pattern is a forward walk from the bucket head, so the back pointers of a doubly linked list would be paid for on every entry and never read. Java 8 added a limit: a bucket that reaches eight entries is converted into a red-black tree, so long as the table itself already holds at least 64 buckets, and below that the map resizes instead. Either way a flood of colliding keys no longer degrades to a linear scan.

Programming languagesCons cells in Lisp, Clojure and Haskell

A list in these languages is a chain of two-field cells: one value and one pointer to the rest. Prepending is O(1) and, more to the point, copies nothing - the new cell simply points at the existing list, so the old list is still valid and the two share every cell behind the join. That structural sharing is what makes immutable lists affordable, where an immutable array would have to copy the whole thing on every change.

Operating systemsFree lists inside glibc malloc

When a small block is freed it goes on the tcache or fastbin list, and glibc does not write it into a side table; it stores the address of the previously freed block in the first bytes of the block being freed, threading the free blocks into a singly linked list. The bookkeeping is free because it lives in memory nobody is using, and allocating is a pop from the head, which is why a tcache hit costs only a handful of instructions. The list is deliberately LIFO: the block freed most recently is the one most likely to still be in cache. Larger free chunks move to bins that are doubly linked, because those have to be unlinked from the middle when neighbours are merged.

ConcurrencyLock-free queues such as ConcurrentLinkedQueue

Java's ConcurrentLinkedQueue follows the Michael and Scott algorithm, and the single pointer is the reason it works: a producer appends by compare-and-swapping one next field from null to its new node, and an ordinary compare-and-swap covers exactly one word. A doubly linked list would need two pointers in two different nodes changed in the same instant, which no single instruction gives you, so it takes a lock or a far more elaborate protocol. The price is that size() has to walk the whole chain, since no thread holds an authoritative count.

Why it works this way

Why can you insert after a node in O(1) but not delete it?

Unlinking a node means changing its predecessor's next pointer, and from the node itself there is no way back. So insert-after is genuinely O(1), while delete-this means walking from the head again just to find out who points at you. The usual trick is to copy the next node's value into this one and unlink the next node instead, which is O(1) but quietly fails on the tail, because there is no following node to steal from.

Why real implementations keep a dummy head node

Without one the first node is a special case in every operation: it has no predecessor, so inserting or deleting there has to update the caller's head variable rather than some node's next field. A sentinel node that is never removed gives every real node a predecessor, so the same code path handles position 0 and position 7. It costs one wasted node and removes the if (node == head) branch from every method, which is where most linked list bugs live.

How do you tell a ring from a very long list?

Walk two pointers from the head, one moving a single hop per step and one moving two. If the list ends, the fast pointer reaches null first. If it is a ring, both pointers end up inside it and the gap between them shrinks by exactly one each step, so they must eventually land on the same node. That is Floyd's cycle detection, and it uses O(1) memory instead of a set of every node already visited.

Why a linked list often loses to an array it should beat on paper

The O(1) insert assumes you are already holding the node, and walking to it reads an address the prefetcher had no way to guess, so a long walk is a run of cache misses. Shifting a few thousand array elements is one predictable streaming pass, which is exactly what the hardware is built for, and it frequently wins outright. Each node also carries a pointer and an allocator header, so the same data takes more memory and fits in cache worse.

Read more

Next up