Understanding Linked Lists.

September 6, 202510 min read
A linked list is a linear data structure where elements are stored in nodes, and each node contains data and a reference (pointer) to the next node in the sequence. Unlike arrays, elements are not stored in contiguous memory locations.

Memory Representation

Types of Linked Lists

Visual Representation

Singly Linked List

Doubly Linked List

Circular Linked List

Operations Complexity

Node Structure Implementation

// Singly Linked List Node
class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

// Doubly Linked List Node
class DNode {
    constructor(data) {
        this.data = data;
        this.next = null;
        this.prev = null;
    }
}

// Node with additional info
class AdvancedNode {
    constructor(data) {
        this.data = data;
        this.next = null;
        this.random = null;  // For special problems
        this.timestamp = Date.now();
    }
}

Basic Operations Visualization

1. Insertion Operations

2. Deletion Operations

Singly Linked List Implementation

class SinglyLinkedList {
    constructor() {
        this.head = null;
        this.size = 0;
    }
    
    // O(1) - Insert at beginning
    prepend(data) {
        const node = new Node(data);
        node.next = this.head;
        this.head = node;
        this.size++;
    }
    
    // O(n) - Insert at end
    append(data) {
        const node = new Node(data);
        if (!this.head) {
            this.head = node;
        } else {
            let current = this.head;
            while (current.next) {
                current = current.next;
            }
            current.next = node;
        }
        this.size++;
    }
    
    // O(n) - Insert at position
    insertAt(data, position) {
        if (position < 0 || position > this.size) return false;
        if (position === 0) return this.prepend(data);
        
        const node = new Node(data);
        let current = this.head;
        for (let i = 0; i < position - 1; i++) {
            current = current.next;
        }
        node.next = current.next;
        current.next = node;
        this.size++;
    }
    
    // O(n) - Delete by value
    delete(data) {
        if (!this.head) return null;
        
        if (this.head.data === data) {
            this.head = this.head.next;
            this.size--;
            return data;
        }
        
        let current = this.head;
        while (current.next && current.next.data !== data) {
            current = current.next;
        }
        
        if (current.next) {
            current.next = current.next.next;
            this.size--;
            return data;
        }
        return null;
    }
    
    // O(n) - Search
    search(data) {
        let current = this.head;
        let index = 0;
        
        while (current) {
            if (current.data === data) return index;
            current = current.next;
            index++;
        }
        return -1;
    }
    
    // O(n) - Reverse list
    reverse() {
        let prev = null;
        let current = this.head;
        
        while (current) {
            let next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        this.head = prev;
    }
}

Doubly Linked List Implementation

class DoublyLinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }
    
    // O(1) - Insert at beginning
    prepend(data) {
        const node = new DNode(data);
        if (!this.head) {
            this.head = this.tail = node;
        } else {
            node.next = this.head;
            this.head.prev = node;
            this.head = node;
        }
        this.size++;
    }
    
    // O(1) - Insert at end (with tail pointer)
    append(data) {
        const node = new DNode(data);
        if (!this.tail) {
            this.head = this.tail = node;
        } else {
            node.prev = this.tail;
            this.tail.next = node;
            this.tail = node;
        }
        this.size++;
    }
    
    // O(1) - Delete from beginning
    deleteFirst() {
        if (!this.head) return null;
        
        const data = this.head.data;
        if (this.head === this.tail) {
            this.head = this.tail = null;
        } else {
            this.head = this.head.next;
            this.head.prev = null;
        }
        this.size--;
        return data;
    }
    
    // O(1) - Delete from end
    deleteLast() {
        if (!this.tail) return null;
        
        const data = this.tail.data;
        if (this.head === this.tail) {
            this.head = this.tail = null;
        } else {
            this.tail = this.tail.prev;
            this.tail.next = null;
        }
        this.size--;
        return data;
    }
}

Common Linked List Algorithms

1. Floyd's Cycle Detection (Tortoise & Hare)

function hasCycle(head) {
    if (!head || !head.next) return false;
    
    let slow = head;
    let fast = head.next;
    
    while (fast && fast.next) {
        if (slow === fast) return true;
        slow = slow.next;
        fast = fast.next.next;
    }
    return false;
}

// Find start of cycle
function detectCycleStart(head) {
    let slow = head, fast = head;
    
    // Find meeting point
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow === fast) break;
    }
    
    if (!fast || !fast.next) return null;
    
    // Find start of cycle
    slow = head;
    while (slow !== fast) {
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
}

2. Find Middle Element

function findMiddle(head) {
    if (!head) return null;
    
    let slow = head;
    let fast = head;
    
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

3. Merge Two Sorted Lists

function mergeSortedLists(l1, l2) {
    const dummy = new Node(0);
    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;
    }
    
    current.next = l1 || l2;
    return dummy.next;
}

Advanced Patterns

1. Reverse in K-Groups

2. LRU Cache using Doubly Linked List

class LRUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.map = new Map();
        this.head = new DNode(0);  // Dummy head
        this.tail = new DNode(0);  // Dummy tail
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }
    
    get(key) {
        if (!this.map.has(key)) return -1;
        
        const node = this.map.get(key);
        this.moveToHead(node);
        return node.value;
    }
    
    put(key, value) {
        if (this.map.has(key)) {
            const node = this.map.get(key);
            node.value = value;
            this.moveToHead(node);
        } else {
            const node = new DNode(key, value);
            this.map.set(key, node);
            this.addToHead(node);
            
            if (this.map.size > this.capacity) {
                const removed = this.removeTail();
                this.map.delete(removed.key);
            }
        }
    }
    
    moveToHead(node) {
        this.removeNode(node);
        this.addToHead(node);
    }
    
    removeNode(node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    
    addToHead(node) {
        node.prev = this.head;
        node.next = this.head.next;
        this.head.next.prev = node;
        this.head.next = node;
    }
    
    removeTail() {
        const node = this.tail.prev;
        this.removeNode(node);
        return node;
    }
}

Common Interview Problems

Linked List vs Array

Skip List

Circular Linked List Applications

XOR Linked List (Memory Efficient)

Problem-Solving Patterns

Common Techniques

1. Dummy Node Pattern

// Simplifies edge cases
function operation(head) {
    const dummy = new Node(0);
    dummy.next = head;
    // Perform operations
    return dummy.next;
}

2. Runner Technique

// Two pointers at different speeds
function technique(head) {
    let slow = head;
    let fast = head;
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
}

3. Recursive Approach

// Elegant for certain problems
function reverseRecursive(head) {
    if (!head || !head.next) return head;
    
    const newHead = reverseRecursive(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
}

Performance Considerations