What's Next?

Congratulations

You have implemented 12 linked list algorithms in C: node creation, traversal, length, push front/back, pop front, search, nth node, delete by value, nth from end, reverse, and merge sorted.

These are exactly the problems that come up in systems programming interviews and in real kernel/allocator code. You know them at the pointer level now — not just abstractly.

What to Explore Next

  • Doubly-Linked Lists — Add a prev pointer to each node. O(1) deletion anywhere (given the node pointer). The Linux kernel's list implementation uses this.
  • Circular Lists — The tail's next points back to the head. Useful for round-robin schedulers.
  • Skip Lists — Probabilistic multi-level linked lists that achieve O(log n) search. Used in Redis and LevelDB.
  • XOR Lists — Store prev XOR next in a single pointer field, halving memory use. A classic bit-manipulation trick.
  • Memory Allocators — Implement a free list allocator: malloc returns from the front of the free list; free inserts back in order.

Build Something

  • A stack — use push_front/pop_front to implement LIFO semantics with O(1) push and pop.
  • A queue — maintain head and tail pointers; O(1) enqueue at tail, O(1) dequeue at head.
  • A sorted insert — insert values in sorted order into a linked list (the basis of insertion sort).
  • Cycle detection — implement Floyd's tortoise-and-hare algorithm to detect if a list has a cycle.

References

  • The C Programming Language by Kernighan and Ritchie — Chapter 6 covers structs and the basics of pointer-linked data structures.
  • Introduction to Algorithms (CLRS) — Chapter 10 covers linked lists, stacks, and queues at depth.
  • Linux kernel list.h — the actual doubly-linked list implementation used throughout the Linux kernel. Read it after this course.
← Previous