Linked Lists Cheat Sheet

Updated 2026-04-29

Next Topic: Manual Testing and Test Case Design Cheat Sheet

🧠Study flashcards on this topic92 cards · spaced repetition→

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, 92 flashcards. Below is a complete table-by-table outline of this topic, spanning foundational concepts through advanced details.

Table 1: Core List TypesTable 2: Node Structure and ComponentsTable 3: Insertion OperationsTable 4: Deletion OperationsTable 5: Traversal OperationsTable 6: Search OperationsTable 7: Reversal OperationsTable 8: Advanced AlgorithmsTable 9: Time Complexity AnalysisTable 10: Memory CharacteristicsTable 11: Common Pitfalls and Edge CasesTable 12: Comparison with Other Data StructuresTable 13: Real-World ApplicationsTable 14: Implementation Patterns

Quick IndexSubscribe to unlock

A jump-to index of every table row in this cheat sheet.

Mind MapSubscribe to unlock

An interactive map of every table and concept in this topic.

Table 1: Core List Types

Not all linked lists are the same chain of nodes — the variant you pick determines what becomes cheap and what becomes possible. The progression here runs from the bare singly linked list up through doubly and circular forms, then into specialized variants like skip lists and intrusive lists that trade simplicity for faster search or tighter memory layout.

Type	Example	Description
Singly linked list	`node1 → node2 → node3 → null`	• Each node contains data and one next pointer • traversal is unidirectional (forward only). Most common and memory-efficient type.
Doubly linked list	`null ← node1 ⇄ node2 ⇄ node3 → null`	• Each node has prev and next pointers enabling bidirectional traversal • doubles memory overhead but simplifies deletions and reversals.
Circular linked list	`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.
Doubly circular linked list	`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.
Intrusive linked list	`struct task { int pid;` `struct list_head list; };`	• List node embedded directly in the data structure rather than wrapping it • used in the Linux kernel (`list_head`) • &bull • fewer allocations and better cache locality than non-intrusive variants.
Skip list	Bottom: `1→2→3→4→5` Top: `1→3→5`	• Multi-level linked list with probabilistically placed express lanes at upper levels • achieves $O(\log n)$ search in sorted data by skipping nodes.
Unrolled linked list	`[1,2,3] → [4,5,6] → [7,8]`	• Each node stores an array of elements instead of a single value • reduces pointer overhead and improves cache locality for better performance.
XOR linked list (legacy)	`node.link = prev ⊕ next`	• Memory-efficient doubly-linked list storing XOR of addresses instead of two separate pointers • rarely used today due to complex pointer arithmetic and lack of garbage collection support.

Table 2: Node Structure and Components

Everything a linked list can do comes down to the small set of fields inside each node and the pointers that anchor the list itself. Getting comfortable with the data field, the next and prev pointers, and helpers like the head, tail, and sentinel node is what makes the operations in later tables click into place.

Component	Example	Description
Node class/struct	`class Node:` `def __init__(self, data):` `self.data = data` `self.next = None`	• Basic building block containing data field and pointer(s) to adjacent nodes • forms the atomic unit of all linked list types.

The rest of this section is part of the full cheat sheet

Table 3: Insertion Operations

Adding a node is mostly a matter of rewiring two pointers in the right order — the cost lives in finding the spot, not the insertion itself. Inserting at the head is the cheapest at $O(1)$, while inserting at a position or into sorted order pays $O(n)$ to locate the target first.

Operation	Example	Description
Insert at head	`new.next = head` `head = new`	• Add node at the beginning • $O(1)$ complexity, most efficient insertion point.

The rest of this section is part of the full cheat sheet

Table 4: Deletion Operations

Deletion mirrors insertion — unlink the node and patch the surrounding pointers — but it has more edge cases that bite. Watch the tail (singly lists must walk to the second-to-last node), the head, and the trick of deleting a node when you only hold a reference to it, which quietly fails on the final node.

Operation	Example	Description
Delete at head	`head = head.next`	• Remove first node • $O(1)$ complexity, simplest deletion.

The rest of this section is part of the full cheat sheet

Table 1: Core List Types

Type	Example	Description
Singly linked list	`node1 → node2 → node3 → null`	• Each node contains data and one next pointer • traversal is unidirectional (forward only). Most common and memory-efficient type.
Doubly linked list	`null ← node1 ⇄ node2 ⇄ node3 → null`	• Each node has prev and next pointers enabling bidirectional traversal • doubles memory overhead but simplifies deletions and reversals.
Circular linked list	`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.
Doubly circular linked list	`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.
Intrusive linked list	`struct task { int pid;` `struct list_head list; };`	• List node embedded directly in the data structure rather than wrapping it • used in the Linux kernel (`list_head`) • &bull • fewer allocations and better cache locality than non-intrusive variants.
Skip list	Bottom: `1→2→3→4→5` Top: `1→3→5`	• Multi-level linked list with probabilistically placed express lanes at upper levels • achieves $O(\log n)$ search in sorted data by skipping nodes.
Unrolled linked list	`[1,2,3] → [4,5,6] → [7,8]`	• Each node stores an array of elements instead of a single value • reduces pointer overhead and improves cache locality for better performance.
XOR linked list (legacy)	`node.link = prev ⊕ next`	• Memory-efficient doubly-linked list storing XOR of addresses instead of two separate pointers • rarely used today due to complex pointer arithmetic and lack of garbage collection support.

Table 2: Node Structure and Components

Component	Example	Description
Node class/struct	`class Node:` `def __init__(self, data):` `self.data = data` `self.next = None`	• Basic building block containing data field and pointer(s) to adjacent nodes • forms the atomic unit of all linked list types.

Table 3: Insertion Operations

Operation	Example	Description
Insert at head	`new.next = head` `head = new`	• Add node at the beginning • $O(1)$ complexity, most efficient insertion point.

Table 4: Deletion Operations

Operation	Example	Description
Delete at head	`head = head.next`	• Remove first node • $O(1)$ complexity, simplest deletion.