A linked list is a dynamic, linear data structure where elements are stored as nodes in non-contiguous memory locations, with each node holding both data and a reference (pointer) to the next node. Unlike arrays, linked lists enable efficient insertions and deletions without shifting elements, making them particularly suitable for scenarios with frequent modifications or unknown sizes. The trade-off is slower random access (requiring sequential traversal) compared to arrays, but for stacks, queues, and many algorithmic problems, this flexibility is often worth it — especially when you understand that the choice between linked lists and arrays isn't about pure speed, but about cache behavior, access patterns, and dynamic sizing needs. In systems programming, variants like the Linux kernel's intrusive linked list (list_head) further reduce allocation overhead by embedding the link node inside the data structure itself.
What This Cheat Sheet Covers
This topic spans 14 focused tables and 105 indexed concepts. Below is a complete table-by-table outline of this topic, spanning foundational concepts through advanced details.
Table 1: Core List Types
| Type | Example | Description |
|---|---|---|
node1 → node2 → node3 → null | • Each node contains data and one next pointer • traversal is unidirectional (forward only). Most common and memory-efficient type. | |
null ← node1 ⇄ node2 ⇄ node3 → null | • Each node has prev and next pointers enabling bidirectional traversal • doubles memory overhead but simplifies deletions and reversals. | |
node1 → node2 → node3 → node1 | • The last node points back to the first instead of null • ideal for round-robin scheduling or applications requiring continuous looping. | |
node1 ⇄ node2 ⇄ node3 ⇄ node1 | • Combines doubly linked structure with circular connectivity • both head.prev and tail.next point to each other, enabling efficient queue/deque operations. |