Skip to main content

DSAPath8 mincore

Linked Lists

A linked list stores each element in a node that points to the next node. It gives cheap insertion and deletion when the position is already known, but slow indexing and poor cache locality.

Why This Matters

Linked lists are the first structure where location is not the same thing as index. Each node says where to go next. That makes insertion at a known node cheap and random access expensive.

Core Idea

A singly linked node stores (value, next). A doubly linked node stores (prev, value, next).

OperationSingly linked list cost
read first itemO(1)O(1)
read item at index iiO(i)O(i)
insert after known nodeO(1)O(1)
delete after known nodeO(1)O(1)
search by valueO(n)O(n)

Worked example: to find the 50th node, a linked list must follow 50 pointers. An array computes the address directly.

Common Mistakes

  • Saying insertion is always O(1)O(1). It is O(1)O(1) only after you already have the node or iterator.
  • Forgetting to update both links in a doubly linked list.
  • Ignoring cache misses. Pointer chasing can lose badly to array scans even when asymptotic costs look similar.

Exercises

  • Draw the pointer changes for deleting a node from a singly linked list.
  • Explain why linked-list binary search is not useful.
  • Implement cycle detection with two pointers.

Next Topics

References

  • Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms (4th ed., 2022). Ch. 10.
  • Skiena. The Algorithm Design Manual (3rd ed., 2020). Ch. 3.