Arrays are incredible. They're fast, intuitive, and the first data structure most of us reach for. You can grab any element by index in constant time, loop through them with a simple `for` loop, and they play nicely with every language on Earth. So why would we ever need anything else? Here's the thing: arrays have a secret weakness. They look simple on the surface, but under the hood, they're making promises that come at a cost. When you insert an element at the beginning of an array, every single element after it has to shift over by one position. Delete from the middle? Same story. That's an **O(n)** operation hiding behind a one-liner. And in low-level languages, arrays require **contiguous memory**, a single unbroken block of RAM. If your array grows, the system might need to allocate an entirely new block and copy everything over. > Imagine you're sitting in a packed movie theater and someone new needs to sit in the third seat. Everyone from seat three onward has to stand up and move one seat over. That's what arrays do on insert. **Linked lists** solve these problems with an entirely different approach. Instead of lining up data in one continuous block, they scatter nodes across memory and connect them with **pointers**, like a treasure hunt where each clue tells you where the next one is. No shifting. No contiguous memory requirement. Just nodes, pointers, and elegant simplicity. In this guide, we'll build linked lists from scratch in TypeScript, understand exactly when they shine (and when they don't), and master the patterns that come up again and again in coding interviews and real-world systems. Let's get started. --- ## What Is a Linked List? A **linked list** is a linear data structure made up of **nodes**. Each node contains two things: 1. **Data** — the value you want to store 2. **A pointer (or reference)** — a link to the next node in the sequence Unlike arrays, linked list nodes are **not stored in contiguous memory**. Each node can live anywhere in the heap. The only thing connecting them is the pointer from one node to the next. The first node in the list is called the **head**. If you have access to the head, you can traverse the entire list by following the chain of pointers. The last node's pointer is `null`, signaling the end of the list. ### Visualizing a Linked List Here's what a singly linked list holding `[10, 20, 30]` looks like conceptually: ``` head │ ▼ ┌──────────────┐ ┌──────────────┐ ┌──────────────┐ │ data: 10 │ │ data: 20 │ │ data: 30 │ │ next: ───────┼───►│ next: ───────┼───►│ next: null │ └──────────────┘ └──────────────┘ └──────────────┘ ``` Each box is a **node**. The `next` field is the **pointer** that tells you where the next node lives in memory. The last node points to `null`, the end of the road. ### The Treasure Hunt Analogy Think of a linked list like a **scavenger hunt**. You get the first clue (the head), and that clue tells you where the next one is hidden. Each clue has two parts: a prize (the data) and directions to the next clue (the pointer). You follow the chain until you reach a clue that says "The End" (`null`). You can't jump straight to clue #5, you have to follow the chain from the beginning. That's both the strength and the limitation of linked lists. > **Key Insight**: In an array, you know exactly where every element is (index × element size). In a linked list, you only know where the *first* element is. Everything else requires traversal. --- ## Arrays vs Linked Lists: A Detailed Comparison This is one of the most important comparisons in computer science, and understanding it will shape how you think about data structure choices for the rest of your career. ### Memory Layout **Arrays** store elements in a **contiguous block** of memory. Element 0 is at address `X`, element 1 is at `X + size`, element 2 is at `X + 2 * size`, and so on. This is why index-based access is O(1), the address is a simple calculation. **Linked lists** store nodes **scattered across memory**. Each node could be anywhere on the heap. The only way to find a node is to follow the pointer chain from the head. ``` Array in memory: ┌─────┬─────┬─────┬─────┬─────┐ │ 10 │ 20 │ 30 │ 40 │ 50 │ ← contiguous block └─────┴─────┴─────┴─────┴─────┘ 0x100 0x104 0x108 0x10C 0x110 Linked list in memory: 0x200: [10 | 0x508] 0x508: [20 | 0x304] 0x304: [30 | 0x700] 0x700: [40 | 0x412] 0x412: [50 | null ] ↑ scattered everywhere! ``` ### Access Patterns - **Array**: Random access in **O(1)**. Need element at index 3? Jump directly there. - **Linked List**: Sequential access in **O(n)**. Need the 3rd element? Start at head, follow `next` three times. ### Insertion and Deletion This is where linked lists flex. - **Array**: Inserting/deleting at the beginning or middle is **O(n)** because elements must be shifted. - **Linked List**: Inserting/deleting at the beginning is **O(1)**. If you already have a reference to the node, inserting/deleting next to it is also **O(1)**, just re-point a couple of pointers. ### Cache Performance This one is subtle but important in practice. Arrays win here. Because array elements sit next to each other in memory, CPUs can load chunks of an array into the **cache** all at once (this is called **spatial locality**). Traversing an array is extremely cache-friendly. Linked list nodes are scattered across memory, so traversing a linked list causes frequent **cache misses**. The CPU has to fetch each node from a potentially different memory location. > **Practical note**: For small to medium datasets, arrays are almost always faster in practice due to cache performance, even when the theoretical Big O says linked lists should win. ### The Big O Comparison Table | Operation | Array | Singly Linked List | Doubly Linked List | |---|---|---|---| | Access by index | **O(1)** | O(n) | O(n) | | Search by value | O(n) | O(n) | O(n) | | Insert at beginning | O(n) | **O(1)** | **O(1)** | | Insert at end | O(1)* | O(n)† | **O(1)** | | Insert at position | O(n) | O(n)‡ | O(n)‡ | | Delete at beginning | O(n) | **O(1)** | **O(1)** | | Delete at end | O(1)* | O(n) | **O(1)** | | Delete at position | O(n) | O(n)‡ | O(n)‡ | | Memory per element | Low | Medium | Higher | *\* Amortized O(1) for dynamic arrays.* *† O(1) if you maintain a tail pointer.* *‡ O(n) to find the position, O(1) for the actual insert/delete once there.* ### When to Choose What **Choose arrays when:** - You need fast random access by index - You're iterating through data sequentially (cache-friendly) - You know the size upfront or it doesn't change often - Memory efficiency matters (no pointer overhead) **Choose linked lists when:** - You have frequent insertions/deletions at the front or middle - You don't need random access - You're building a queue, stack, or LRU cache - The dataset size is highly dynamic and unpredictable --- ## Singly Linked List A **singly linked list** is the simplest form of a linked list. Each node has a `data` field and a `next` pointer. You can only traverse in one direction: from head to tail. Let's build one from scratch in TypeScript with full generic support. ### The Node Class Every linked list starts with a node. A node is a simple container that holds a value and a reference to the next node. ```typescript class ListNode { data: T; next: ListNode | null; constructor(data: T) { this.data = data; this.next = null; } } ``` The generic `` lets us create linked lists that hold any type: numbers, strings, objects, whatever we need. ### The SinglyLinkedList Class: Full Implementation Here's a complete, production-quality singly linked list implementation. We'll walk through each method after the full listing. ```typescript class ListNode { data: T; next: ListNode | null; constructor(data: T) { this.data = data; this.next = null; } } class SinglyLinkedList { private head: ListNode | null; private size: number; constructor() { this.head = null; this.size = 0; } /** Check if the list is empty */ isEmpty(): boolean { return this.head === null; } /** Get the number of nodes in the list */ getSize(): number { return this.size; } /** Add a node to the end of the list — O(n) */ append(data: T): void { const newNode = new ListNode(data); if (!this.head) { this.head = newNode; } else { let current = this.head; while (current.next) { current = current.next; } current.next = newNode; } this.size++; } /** Add a node to the beginning of the list — O(1) */ prepend(data: T): void { const newNode = new ListNode(data); newNode.next = this.head; this.head = newNode; this.size++; } /** Insert a node at a specific position — O(n) */ insertAt(data: T, position: number): void { if (position < 0 || position > this.size) { throw new RangeError(`Position ${position} is out of bounds (0..${this.size})`); } if (position === 0) { this.prepend(data); return; } const newNode = new ListNode(data); let current = this.head; let prev: ListNode | null = null; let index = 0; while (index < position) { prev = current; current = current!.next; index++; } prev!.next = newNode; newNode.next = current; this.size++; } /** Delete the first node with a matching value — O(n) */ deleteNode(data: T): boolean { if (!this.head) return false; if (this.head.data === data) { this.head = this.head.next; this.size--; return true; } let current = this.head; while (current.next) { if (current.next.data === data) { current.next = current.next.next; this.size--; return true; } current = current.next; } return false; } /** Delete the node at a specific position — O(n) */ deleteAt(position: number): T { if (position < 0 || position >= this.size) { throw new RangeError(`Position ${position} is out of bounds (0..${this.size - 1})`); } let removedData: T; if (position === 0) { removedData = this.head!.data; this.head = this.head!.next; this.size--; return removedData; } let current = this.head; let prev: ListNode | null = null; let index = 0; while (index < position) { prev = current; current = current!.next; index++; } removedData = current!.data; prev!.next = current!.next; this.size--; return removedData; } /** Find the first node with a matching value — O(n) */ find(data: T): ListNode | null { let current = this.head; while (current) { if (current.data === data) { return current; } current = current.next; } return null; } /** Check if a value exists in the list — O(n) */ contains(data: T): boolean { return this.find(data) !== null; } /** Get the value at a specific index — O(n) */ getAt(position: number): T { if (position < 0 || position >= this.size) { throw new RangeError(`Position ${position} is out of bounds (0..${this.size - 1})`); } let current = this.head; let index = 0; while (index < position) { current = current!.next; index++; } return current!.data; } /** Traverse the list and return all values as an array — O(n) */ toArray(): T[] { const result: T[] = []; let current = this.head; while (current) { result.push(current.data); current = current.next; } return result; } /** Print the list in a readable format — O(n) */ print(): void { const values = this.toArray(); console.log(values.join(' → ') + ' → null'); } /** Clear the entire list — O(1) */ clear(): void { this.head = null; this.size = 0; } } ``` ### Using the Singly Linked List ```typescript const list = new SinglyLinkedList(); list.append(10); list.append(20); list.append(30); list.print(); // 10 → 20 → 30 → null list.prepend(5); list.print(); // 5 → 10 → 20 → 30 → null list.insertAt(15, 2); list.print(); // 5 → 10 → 15 → 20 → 30 → null list.deleteNode(15); list.print(); // 5 → 10 → 20 → 30 → null const removed = list.deleteAt(0); console.log(`Removed: ${removed}`); // Removed: 5 list.print(); // 10 → 20 → 30 → null console.log(list.contains(20)); // true console.log(list.contains(99)); // false console.log(list.getAt(1)); // 20 console.log(list.getSize()); // 3 ``` --- ### Method Breakdown and Complexity Let's walk through the key operations to understand what's happening under the hood. #### `prepend(data)` — O(1) This is the linked list's superpower. Adding to the front is constant time because we just create a new node and point it at the current head: ```typescript prepend(data: T): void { const newNode = new ListNode(data); newNode.next = this.head; // point new node to old head this.head = newNode; // update head to new node this.size++; } ``` No shifting, no copying, no traversal. Just two pointer operations. #### `append(data)` — O(n) Adding to the end requires walking the entire list to find the last node: ```typescript append(data: T): void { const newNode = new ListNode(data); if (!this.head) { this.head = newNode; } else { let current = this.head; while (current.next) { // walk to the end current = current.next; } current.next = newNode; // link the last node to our new node } this.size++; } ``` > **Optimization tip**: You can make `append` O(1) by maintaining a `tail` pointer. We'll do exactly that in the doubly linked list section. #### `deleteNode(data)` — O(n) Deletion requires finding the node *before* the one we want to remove, then re-wiring the pointers: ```typescript deleteNode(data: T): boolean { if (!this.head) return false; // Special case: deleting the head if (this.head.data === data) { this.head = this.head.next; this.size--; return true; } let current = this.head; while (current.next) { if (current.next.data === data) { current.next = current.next.next; // skip over the node this.size--; return true; } current = current.next; } return false; // not found } ``` The key line is `current.next = current.next.next`. This "skips over" the node we want to delete, effectively removing it from the chain. --- ## Walking Through Operations Visually Understanding pointer manipulation is crucial. Let's visualize the most important operations step by step. ### Inserting at Position 2 Starting list: `10 → 20 → 30 → null`. We want to insert `25` at position 2. **Step 1: Create the new node** ``` newNode: [25 | null] head │ ▼ [10 | ─]──►[20 | ─]──►[30 | null] ``` **Step 2: Traverse to position 1 (the node before the insertion point)** ``` prev current │ │ ▼ ▼ [10 | ─]──►[20 | ─]──►[30 | null] ``` **Step 3: Point newNode.next to current** ``` prev current │ │ ▼ ▼ [10 | ─]──►[20 | ─]──►[30 | null] ▲ [25 | ─]──┘ ``` **Step 4: Point prev.next to newNode** ``` prev current │ │ ▼ ▼ [10 | ─]──►[20 | ─]──►[25 | ─]──►[30 | null] ``` Done! The node is inserted without moving any other data. > **Critical**: The order matters! You **must** set `newNode.next` before updating `prev.next`. If you update `prev.next` first, you lose the reference to the rest of the list. --- ### Deleting a Node (value: 20) Starting list: `10 → 20 → 30 → null`. We want to delete the node with value `20`. **Step 1: Traverse to find the node *before* the target** ``` current current.next │ │ ▼ ▼ [10 | ─]──►[20 | ─]──►[30 | null] ``` We found it! `current.next.data === 20`. **Step 2: Skip over the target node** ``` current.next = current.next.next [10 | ─]──────────────►[30 | null] [20 | ─]──┘ (orphaned, will be garbage collected) ``` **After deletion:** ``` head │ ▼ [10 | ─]──►[30 | null] ``` The node containing `20` is now unreachable. In JavaScript/TypeScript, the garbage collector will reclaim its memory automatically. --- ## Doubly Linked List A **doubly linked list** extends the singly linked list by adding a `prev` pointer to each node. Every node now knows both its successor *and* its predecessor. ### What's Different? ``` head tail │ │ ▼ ▼ null ◄── [10] ◄──► [20] ◄──► [30] ◄──► [40] ──► null ``` Each node has three fields: - `data` — the stored value - `next` — pointer to the next node - `prev` — pointer to the previous node We also maintain a **tail** pointer, giving us O(1) access to both ends. ### Trade-offs | | Singly Linked List | Doubly Linked List | |---|---|---| | Memory per node | data + 1 pointer | data + 2 pointers | | Traverse forward | ✅ | ✅ | | Traverse backward | ❌ | ✅ | | Delete with node ref | O(n)* | **O(1)** | | Insert at end (with tail) | O(1) | **O(1)** | | Complexity | Simpler | More pointers to manage | *\* In a singly linked list, deleting a node when you have a reference to it still requires finding the **previous** node, which is O(n). In a doubly linked list, you already have `node.prev`.* ### The DoublyLinkedList Node ```typescript class DoublyNode { data: T; next: DoublyNode | null; prev: DoublyNode | null; constructor(data: T) { this.data = data; this.next = null; this.prev = null; } } ``` ### Full Doubly Linked List Implementation ```typescript class DoublyNode { data: T; next: DoublyNode | null; prev: DoublyNode | null; constructor(data: T) { this.data = data; this.next = null; this.prev = null; } } class DoublyLinkedList { private head: DoublyNode | null; private tail: DoublyNode | null; private size: number; constructor() { this.head = null; this.tail = null; this.size = 0; } isEmpty(): boolean { return this.size === 0; } getSize(): number { return this.size; } /** Add to the end — O(1) thanks to the tail pointer */ append(data: T): void { const newNode = new DoublyNode(data); if (!this.tail) { this.head = newNode; this.tail = newNode; } else { newNode.prev = this.tail; this.tail.next = newNode; this.tail = newNode; } this.size++; } /** Add to the beginning — O(1) */ prepend(data: T): void { const newNode = new DoublyNode(data); if (!this.head) { this.head = newNode; this.tail = newNode; } else { newNode.next = this.head; this.head.prev = newNode; this.head = newNode; } this.size++; } /** Insert at a specific position — O(n) */ insertAt(data: T, position: number): void { if (position < 0 || position > this.size) { throw new RangeError(`Position ${position} is out of bounds (0..${this.size})`); } if (position === 0) { this.prepend(data); return; } if (position === this.size) { this.append(data); return; } const newNode = new DoublyNode(data); let current = this.head; let index = 0; while (index < position) { current = current!.next; index++; } const prevNode = current!.prev!; prevNode.next = newNode; newNode.prev = prevNode; newNode.next = current; current!.prev = newNode; this.size++; } /** Delete the first node with a matching value — O(n) */ delete(data: T): boolean { let current = this.head; while (current) { if (current.data === data) { this.removeNode(current); return true; } current = current.next; } return false; } /** Delete the node at a specific position — O(n) */ deleteAt(position: number): T { if (position < 0 || position >= this.size) { throw new RangeError(`Position ${position} is out of bounds (0..${this.size - 1})`); } let current = this.head; let index = 0; while (index < position) { current = current!.next; index++; } this.removeNode(current!); return current!.data; } /** Internal helper to remove a node by reference — O(1) */ private removeNode(node: DoublyNode): void { if (node.prev) { node.prev.next = node.next; } else { this.head = node.next; } if (node.next) { node.next.prev = node.prev; } else { this.tail = node.prev; } node.next = null; node.prev = null; this.size--; } /** Get the head value — O(1) */ peekFront(): T | undefined { return this.head?.data; } /** Get the tail value — O(1) */ peekBack(): T | undefined { return this.tail?.data; } /** Traverse and collect values front to back — O(n) */ traverseForward(): T[] { const result: T[] = []; let current = this.head; while (current) { result.push(current.data); current = current.next; } return result; } /** Traverse and collect values back to front — O(n) */ traverseBackward(): T[] { const result: T[] = []; let current = this.tail; while (current) { result.push(current.data); current = current.prev; } return result; } /** Print the list forward — O(n) */ printForward(): void { const values = this.traverseForward(); console.log('null ◄─ ' + values.join(' ◄──► ') + ' ──► null'); } /** Print the list backward — O(n) */ printBackward(): void { const values = this.traverseBackward(); console.log('null ◄── ' + values.join(' ──► ') + ' ──► null'); } /** Convert to array — O(n) */ toArray(): T[] { return this.traverseForward(); } /** Clear the list — O(1) */ clear(): void { this.head = null; this.tail = null; this.size = 0; } } ``` ### Using the Doubly Linked List ```typescript const dll = new DoublyLinkedList(); dll.append(10); dll.append(20); dll.append(30); dll.append(40); dll.printForward(); // null ◄─ 10 ◄──► 20 ◄──► 30 ◄──► 40 ──► null dll.prepend(5); dll.printForward(); // null ◄─ 5 ◄──► 10 ◄──► 20 ◄──► 30 ◄──► 40 ──► null dll.insertAt(25, 3); dll.printForward(); // null ◄─ 5 ◄──► 10 ◄──► 20 ◄──► 25 ◄──► 30 ◄──► 40 ──► null console.log('Forward:', dll.traverseForward()); // Forward: [5, 10, 20, 25, 30, 40] console.log('Backward:', dll.traverseBackward()); // Backward: [40, 30, 25, 20, 10, 5] console.log('Front:', dll.peekFront()); // 5 console.log('Back:', dll.peekBack()); // 40 ``` ### The `removeNode` Helper The private `removeNode` method is the heart of the doubly linked list. Because every node has a `prev` pointer, we can remove *any* node in **O(1)** if we already have a reference to it: ```typescript private removeNode(node: DoublyNode): void { // If node has a previous, link it to node's next if (node.prev) { node.prev.next = node.next; } else { // Node is the head — update head this.head = node.next; } // If node has a next, link it to node's prev if (node.next) { node.next.prev = node.prev; } else { // Node is the tail — update tail this.tail = node.prev; } // Clean up the removed node's pointers node.next = null; node.prev = null; this.size--; } ``` This is why doubly linked lists are used for **LRU caches**: you can remove and reinsert nodes in constant time. --- ## Circular Linked List A **circular linked list** is a variation where the last node's `next` pointer circles back to the head instead of pointing to `null`. There's no true "end" — the list forms a loop. ### Visualizing a Circular Linked List ``` head │ ▼ ┌──► [10] ──► [20] ──► [30] ──┐ │ │ └───────────────────────────────┘ ``` ### When Is It Useful? - **Round-robin scheduling**: Tasks cycle endlessly through a queue (CPU time slicing, multiplayer game turns) - **Music playlists**: Loop back to the first track after the last - **Circular buffers**: Streaming audio/video data - **Token-passing networks**: Network protocols where a "token" circles the ring ### TypeScript Implementation ```typescript class CircularNode { data: T; next: CircularNode | null; constructor(data: T) { this.data = data; this.next = null; } } class CircularLinkedList { private head: CircularNode | null; private tail: CircularNode | null; private size: number; constructor() { this.head = null; this.tail = null; this.size = 0; } isEmpty(): boolean { return this.size === 0; } getSize(): number { return this.size; } /** Add to the end — O(1) */ append(data: T): void { const newNode = new CircularNode(data); if (!this.head) { this.head = newNode; this.tail = newNode; newNode.next = newNode; // points to itself } else { newNode.next = this.head; this.tail!.next = newNode; this.tail = newNode; } this.size++; } /** Add to the beginning — O(1) */ prepend(data: T): void { const newNode = new CircularNode(data); if (!this.head) { this.head = newNode; this.tail = newNode; newNode.next = newNode; } else { newNode.next = this.head; this.tail!.next = newNode; this.head = newNode; } this.size++; } /** Delete the first occurrence of a value — O(n) */ delete(data: T): boolean { if (!this.head) return false; // Single node case if (this.size === 1 && this.head.data === data) { this.head = null; this.tail = null; this.size = 0; return true; } // Head deletion if (this.head.data === data) { this.head = this.head.next; this.tail!.next = this.head; this.size--; return true; } let current = this.head; while (current.next !== this.head) { if (current.next!.data === data) { if (current.next === this.tail) { this.tail = current; } current.next = current.next!.next; this.size--; return true; } current = current.next!; } return false; } /** Traverse the circular list — O(n) */ toArray(): T[] { if (!this.head) return []; const result: T[] = []; let current: CircularNode | null = this.head; do { result.push(current!.data); current = current!.next; } while (current !== this.head); return result; } /** Print the list showing the circular nature — O(n) */ print(): void { if (!this.head) { console.log('(empty)'); return; } const values = this.toArray(); console.log(values.join(' → ') + ' → (back to head)'); } } ``` ### Using the Circular Linked List ```typescript const playlist = new CircularLinkedList(); playlist.append('Song A'); playlist.append('Song B'); playlist.append('Song C'); playlist.print(); // Song A → Song B → Song C → (back to head) playlist.prepend('Intro'); playlist.print(); // Intro → Song A → Song B → Song C → (back to head) playlist.delete('Song B'); playlist.print(); // Intro → Song A → Song C → (back to head) ``` > **Watch out**: When traversing a circular linked list, you **must** use a `do...while` loop or track the starting node. A regular `while (current)` will loop forever because `current` is never `null`. --- ## Real-World Applications Linked lists aren't just academic exercises. They power critical systems across software engineering. ### 1. Browser History (Doubly Linked List) When you click "Back" and "Forward" in your browser, you're navigating a doubly linked list. Each page you visit becomes a node with pointers to the previous page and the next page. ```typescript interface BrowserPage { url: string; title: string; } class BrowserHistory { private current: DoublyNode | null = null; visit(url: string, title: string): void { const page = new DoublyNode({ url, title }); if (this.current) { this.current.next = page; page.prev = this.current; } this.current = page; } back(): BrowserPage | null { if (this.current?.prev) { this.current = this.current.prev; return this.current.data; } return null; } forward(): BrowserPage | null { if (this.current?.next) { this.current = this.current.next; return this.current.data; } return null; } currentPage(): BrowserPage | null { return this.current?.data ?? null; } } ``` ### 2. Music Playlist (Circular Linked List) Music apps use circular linked lists so that after the last song finishes, playback loops back to the first: ```typescript class MusicPlayer { private playlist: CircularLinkedList; private currentTrack: CircularNode | null = null; constructor() { this.playlist = new CircularLinkedList(); } addSong(song: string): void { this.playlist.append(song); } nowPlaying(): string | null { return this.currentTrack?.data ?? null; } next(): string | null { if (this.currentTrack?.next) { this.currentTrack = this.currentTrack.next; return this.currentTrack.data; } return null; } } ``` ### 3. LRU Cache (Doubly Linked List + HashMap) An **LRU (Least Recently Used) Cache** is one of the most common interview questions *and* a real production pattern. It uses a doubly linked list (to track access order) and a hash map (for O(1) lookups): ```typescript class LRUCache { private capacity: number; private cache: Map>; private list: DoublyLinkedList<{ key: K; value: V }>; constructor(capacity: number) { this.capacity = capacity; this.cache = new Map(); this.list = new DoublyLinkedList(); } get(key: K): V | undefined { const node = this.cache.get(key); if (!node) return undefined; // Move to front (most recently used) this.list.delete(node.data); this.list.prepend(node.data); return node.data.value; } put(key: K, value: V): void { if (this.cache.has(key)) { this.list.delete(this.cache.get(key)!.data); } this.list.prepend({ key, value }); // The new head node is what we store in the map if (this.list.getSize() > this.capacity) { // Evict the least recently used (tail) const evicted = this.list.traverseBackward()[0]; if (evicted) { this.list.delete(evicted); this.cache.delete(evicted.key); } } } } ``` > The doubly linked list gives us O(1) removal and O(1) insertion at the head. The hash map gives us O(1) lookups. Together, every operation on the LRU cache is O(1). ### 4. Undo/Redo Systems Text editors, design tools, and IDEs use a doubly linked list for undo/redo. Each action becomes a node. "Undo" moves the pointer backward; "Redo" moves it forward. ### 5. Memory Allocation (Free Lists) Operating systems maintain **free lists** — linked lists of available memory blocks. When a program requests memory, the OS walks the free list to find a suitable block. When memory is freed, it's added back to the list. ### 6. React Fiber Architecture React's reconciliation engine (Fiber) uses a linked list structure internally. Each fiber is a node representing a unit of work, linked to its sibling, child, and return (parent) fibers. This allows React to pause and resume rendering work — something that wouldn't be possible with a simple recursive tree traversal. ``` FiberNode { child → first child fiber sibling → next sibling fiber return → parent fiber } ``` --- ## Common Operations and Patterns These patterns appear constantly in coding interviews and real-world code. Master them. ### 1. Reversing a Linked List (Iterative) This is the single most common linked list interview question. The idea: walk through the list and flip every `next` pointer to point backward. ```typescript function reverseList(head: ListNode | null): ListNode | null { let prev: ListNode | null = null; let current = head; while (current) { const nextTemp = current.next; // save the next node current.next = prev; // reverse the pointer prev = current; // advance prev current = nextTemp; // advance current } return prev; // prev is the new head } ``` **Visual walkthrough:** Starting: `1 → 2 → 3 → null` ``` Step 0: prev=null, current=1 null 1 → 2 → 3 → null Step 1: prev=1, current=2 null ← 1 2 → 3 → null Step 2: prev=2, current=3 null ← 1 ← 2 3 → null Step 3: prev=3, current=null null ← 1 ← 2 ← 3 Result: 3 → 2 → 1 → null ``` Three variables. One loop. That's it. **Time**: O(n) — single pass **Space**: O(1) — only three pointers --- ### 2. Finding the Middle Node (Slow/Fast Pointer) The **tortoise and hare** technique: use two pointers, one moving one step at a time (slow) and one moving two steps (fast). When the fast pointer reaches the end, the slow pointer is at the middle. ```typescript function findMiddle(head: ListNode | null): ListNode | null { if (!head) return null; let slow: ListNode | null = head; let fast: ListNode | null = head; while (fast && fast.next) { slow = slow!.next; fast = fast.next.next; } return slow; } ``` **Visual:** ``` List: 1 → 2 → 3 → 4 → 5 Step 0: slow=1, fast=1 Step 1: slow=2, fast=3 Step 2: slow=3, fast=5 fast.next is null → stop Middle: 3 ✓ ``` For even-length lists, this returns the second of the two middle nodes: ``` List: 1 → 2 → 3 → 4 Step 0: slow=1, fast=1 Step 1: slow=2, fast=3 Step 2: slow=3, fast=null (fast.next was null) → stop, middle is 3 ``` **Time**: O(n) — single pass **Space**: O(1) --- ### 3. Detecting a Cycle (Floyd's Algorithm) If a linked list has a cycle (a node points back to an earlier node), a naive traversal will loop forever. Floyd's algorithm detects cycles using the same slow/fast pointer technique. ``` Normal list: 1 → 2 → 3 → 4 → null Cycle: 1 → 2 → 3 → 4 ▲ │ └───────┘ ``` **The insight**: If there's a cycle, the fast pointer will eventually "lap" the slow pointer, and they'll meet inside the cycle. If there's no cycle, the fast pointer will reach `null`. ```typescript function hasCycle(head: ListNode | null): boolean { if (!head) return false; let slow: ListNode | null = head; let fast: ListNode | null = head; while (fast && fast.next) { slow = slow!.next; fast = fast.next.next; if (slow === fast) { return true; // they met — cycle detected! } } return false; // fast reached the end — no cycle } ``` **Finding the start of the cycle:** Once you detect a cycle, you can find where it begins. After the slow and fast pointers meet, reset one pointer to the head. Then move both one step at a time — they'll meet at the cycle's entry point. ```typescript function detectCycleStart(head: ListNode | null): ListNode | null { if (!head) return null; let slow: ListNode | null = head; let fast: ListNode | null = head; // Phase 1: Detect cycle while (fast && fast.next) { slow = slow!.next; fast = fast.next.next; if (slow === fast) break; } // No cycle found if (!fast || !fast.next) return null; // Phase 2: Find the entry point slow = head; while (slow !== fast) { slow = slow!.next; fast = fast!.next; } return slow; } ``` > **Why does this work?** It's math. If the distance from head to cycle start is `a`, and the distance from cycle start to meeting point is `b`, then the remaining cycle length is `c - b` (where `c` is cycle length). It turns out that `a = c - b`, so starting from head and meeting point simultaneously will converge at the cycle entry. This is a classic proof worth studying. **Time**: O(n) **Space**: O(1) --- ### 4. Merging Two Sorted Lists Given two sorted linked lists, merge them into one sorted list. This is a classic divide-and-conquer building block (used in merge sort on linked lists). ```typescript function mergeSortedLists( l1: ListNode | null, l2: ListNode | null ): ListNode | null { const dummy = new ListNode(null as unknown as T); let current = dummy; while (l1 && l2) { if (l1.data <= l2.data) { current.next = l1; l1 = l1.next; } else { current.next = l2; l2 = l2.next; } current = current.next; } // Attach the remaining nodes current.next = l1 ?? l2; return dummy.next; } ``` **Visual:** ``` l1: 1 → 3 → 5 → null l2: 2 → 4 → 6 → null Step 1: compare 1 vs 2 → take 1 Step 2: compare 3 vs 2 → take 2 Step 3: compare 3 vs 4 → take 3 Step 4: compare 5 vs 4 → take 4 Step 5: compare 5 vs 6 → take 5 Step 6: l1 exhausted, attach rest of l2 → 6 Result: 1 → 2 → 3 → 4 → 5 → 6 → null ``` The **dummy node** pattern is a key technique: it simplifies the logic by avoiding special handling for the head of the result list. **Time**: O(n + m) where n and m are the lengths of the two lists **Space**: O(1) — we're re-linking existing nodes, not creating new ones --- ### 5. Removing the Nth Node From the End Use two pointers separated by a gap of `n`. When the lead pointer reaches the end, the trailing pointer is right before the target. ```typescript function removeNthFromEnd( head: ListNode | null, n: number ): ListNode | null { const dummy = new ListNode(null as unknown as T); dummy.next = head; let fast: ListNode | null = dummy; let slow: ListNode | null = dummy; // Advance fast by n + 1 steps for (let i = 0; i <= n; i++) { fast = fast!.next; } // Move both until fast reaches the end while (fast) { slow = slow!.next; fast = fast.next; } // Skip the target node slow!.next = slow!.next!.next; return dummy.next; } ``` **Time**: O(n) — single pass **Space**: O(1) --- ## Common Pitfalls Even experienced developers trip over these. Learn them now so you don't debug them later. ### 1. Losing Reference to the Head If you reassign `head` during traversal without saving it, you lose the entire list: ```typescript // ❌ BAD: overwrites head let head = firstNode; while (head) { head = head.next; // oops — we lost the start of the list! } // ✅ GOOD: use a separate traversal variable let current = head; while (current) { current = current.next; } // head is still intact ``` ### 2. Not Handling Edge Cases Always account for: - **Empty list** (`head === null`) - **Single node** (`head.next === null`) - **Target is the head** (deletion/insertion at position 0) - **Target is the tail** (deletion/insertion at the last position) ```typescript // ❌ BAD: crashes on empty list function getFirst(head: ListNode): T { return head.data; // what if head is null? } // ✅ GOOD: handles empty list function getFirst(head: ListNode | null): T | null { return head?.data ?? null; } ``` ### 3. Memory Leaks (Forgetting to Null Out References) In languages with garbage collection (like JavaScript/TypeScript), orphaned nodes *usually* get cleaned up. But if external code holds a reference to a deleted node, that node (and everything it points to) stays in memory: ```typescript // When removing a node from a doubly linked list: private removeNode(node: DoublyNode): void { // ... re-wire prev and next ... // ✅ Clean up the removed node's pointers node.next = null; node.prev = null; } ``` ### 4. Off-by-One Errors in Position-Based Operations Position math in linked lists is tricky. Common mistakes: ```typescript // ❌ BAD: off-by-one — stops one node too early let index = 0; while (index < position - 1) { // should this be position or position - 1? current = current.next; index++; } // ✅ GOOD: be explicit about what "current" represents at each step // If you need the node BEFORE position, traverse to position - 1 // If you need the node AT position, traverse to position ``` > **Tip**: When in doubt, trace through your code with a small example (3 nodes, target position 0, 1, and 2). Draw the pointers on paper. This catches off-by-one errors every time. ### 5. Updating Pointers in the Wrong Order This is the most dangerous mistake during insertion: ```typescript // ❌ BAD: lost the rest of the list! prev.next = newNode; // we just orphaned everything after prev newNode.next = ???; // the old prev.next is gone! // ✅ GOOD: save the reference first newNode.next = prev.next; // link new node to the rest of the list prev.next = newNode; // then insert the new node ``` --- ## Big O Quick Reference Here's your go-to reference card for linked list operation complexity. ### Singly Linked List | Operation | Time | Space | Notes | |---|---|---|---| | Access by index | O(n) | O(1) | Must traverse from head | | Search | O(n) | O(1) | Linear scan | | Prepend | O(1) | O(1) | Update head pointer | | Append (no tail) | O(n) | O(1) | Must traverse to end | | Append (with tail) | O(1) | O(1) | Direct tail access | | Insert at position | O(n) | O(1) | Traverse + re-link | | Delete head | O(1) | O(1) | Update head pointer | | Delete by value | O(n) | O(1) | Search + re-link | | Delete at position | O(n) | O(1) | Traverse + re-link | | Reverse | O(n) | O(1) | Single pass, 3 pointers | ### Doubly Linked List | Operation | Time | Space | Notes | |---|---|---|---| | Access by index | O(n) | O(1) | Can start from closer end | | Search | O(n) | O(1) | Can search from either end | | Prepend | O(1) | O(1) | Update head + pointers | | Append | O(1) | O(1) | Direct tail access | | Insert at position | O(n) | O(1) | Traverse + re-link | | Delete head | O(1) | O(1) | Update head + pointers | | Delete tail | O(1) | O(1) | Direct tail access | | Delete by node ref | O(1) | O(1) | Has prev pointer | | Delete by value | O(n) | O(1) | Search + O(1) removal | ### Comparison with Arrays | Operation | Array | Singly LL | Doubly LL | |---|---|---|---| | Read at index | **O(1)** | O(n) | O(n) | | Insert at start | O(n) | **O(1)** | **O(1)** | | Insert at end | O(1)* | O(n)† | **O(1)** | | Delete at start | O(n) | **O(1)** | **O(1)** | | Delete at end | O(1)* | O(n) | **O(1)** | | Search | O(n) | O(n) | O(n) | | Memory overhead | None | 1 ptr/node | 2 ptrs/node | | Cache performance | Excellent | Poor | Poor | *\* Amortized for dynamic arrays* *† O(1) with a tail pointer* --- ## Cheat Sheet Keep this handy as a quick reference for interviews and day-to-day work. ### Key Patterns to Remember **1. The Dummy Node Pattern** When building or modifying a list, create a dummy node as a placeholder head. It simplifies edge cases (empty list, single node) and means you don't need special logic for the head. ```typescript const dummy = new ListNode(0); // ... build your list with dummy.next ... return dummy.next; // the real head ``` **2. The Two-Pointer (Slow/Fast) Pattern** - **Find middle**: slow moves 1, fast moves 2 - **Detect cycle**: slow moves 1, fast moves 2, check if they meet - **Nth from end**: gap of n between two pointers - **Palindrome check**: find middle, reverse second half, compare **3. The Prev/Current Pattern** For deletion and insertion, maintain a `prev` pointer so you can re-wire: ```typescript let prev: ListNode | null = null; let current = head; while (current) { if (shouldDelete(current)) { if (prev) { prev.next = current.next; } else { head = current.next; } } else { prev = current; } current = current.next; } ``` **4. The Runner Technique** Use two pointers at different speeds or starting points to solve problems in a single pass. ### When Linked Lists Are the Answer Look for these signals in interview problems: - "Insert/delete at the beginning frequently" → Singly linked list - "Need to traverse in both directions" → Doubly linked list - "Implement a queue" → Linked list with head and tail - "LRU cache" → Doubly linked list + hash map - "Merge sorted sequences" → Merge sorted lists - "Detect cycles" → Floyd's slow/fast pointer - "Find the kth element from the end" → Two pointers with gap - "Reverse a sequence in-place" → Pointer reversal - "Round-robin / circular behavior" → Circular linked list ### Common Interview Signals If the problem says... | Think... ---|--- "Given a linked list..." | Know your traversal, two-pointer, and reversal patterns "Constant space" | Pointer manipulation, no extra data structures "In-place" | Reverse, re-link, or partition by re-wiring pointers "Middle of the list" | Slow/fast pointers "Merge" | Dummy node + comparison loop "Cycle" | Floyd's algorithm ### The Linked List Mental Model ``` ┌─────────────────────────────────────────────────────┐ │ LINKED LIST │ │ │ │ Strength: O(1) insert/delete at known positions │ │ Weakness: O(n) access (no random access) │ │ Memory: Extra pointer(s) per node │ │ Cache: Poor (non-contiguous memory) │ │ │ │ Best for: Frequent inserts/deletes, queues, │ │ caches, undo systems │ │ Avoid for: Random access, small datasets, │ │ cache-sensitive workloads │ └─────────────────────────────────────────────────────┘ ``` --- ## Wrapping Up Linked lists are one of the foundational data structures that every developer should understand deeply. They teach you to think about **pointers**, **memory**, and **trade-offs**, concepts that apply far beyond linked lists themselves. Here's what we covered: - **Singly linked lists**: Nodes connected in one direction. Great for stacks, simple queues, and situations where you insert/delete at the front. - **Doubly linked lists**: Bidirectional connections. Essential for LRU caches, browser history, and undo/redo systems. More memory, but O(1) deletion from anywhere with a node reference. - **Circular linked lists**: The tail connects back to the head. Perfect for round-robin scheduling and looping playlists. - **Core patterns**: Reversal, slow/fast pointers, cycle detection, merging, dummy nodes — these show up again and again. - **When to choose what**: Arrays for random access and cache performance. Linked lists for dynamic insertions/deletions and building other data structures. The key takeaway? Linked lists aren't about replacing arrays. They're about having the right tool for the right job. Understanding *when* to reach for a linked list is just as important as knowing *how* to implement one. > **Remember**: Every great data structure has trade-offs. The best engineers don't pick the "best" data structure — they pick the *right* one for the problem at hand. --- ## What's Next? Now that you've mastered the fundamentals, it's time to put them into practice. In the upcoming **"Linked Lists Made Simple"** article, we'll tackle the most common LeetCode linked list problems step by step, breaking down the patterns that turn these problems from intimidating to intuitive. We'll cover problems like: - Reverse Linked List (LeetCode 206) - Merge Two Sorted Lists (LeetCode 21) - Linked List Cycle (LeetCode 141) - Remove Nth Node From End (LeetCode 19) - Reorder List (LeetCode 143) - And more... Each problem will build on the patterns you learned here. You've got the foundation — now let's sharpen it. Happy coding!

Linked Lists 101: The Ultimate Beginner's Guide