Linked Lists

Definition

A linear data structure where elements are stored in nodes, each containing data and reference(s) to other node(s). Unlike arrays, elements are not stored in contiguous memory locations.

Singly Linked List

Doubly Linked List

Circular Linked List

---

Big O Complexity

---

When to Use

USE WHEN: - Frequent insertions/deletions at beginning - Size is unknown and changes frequently - Don't need random access - Memory allocation in small chunks is preferred - Implementing stacks, queues, or deques - Need to insert/delete in middle (with node reference)

DON'T USE WHEN: - Need fast random access by index - Memory efficiency is critical (pointer overhead) - Need cache-friendly traversal - Mostly doing lookups - Data size is fixed and known

Common Use Cases: - Implementing LRU Cache (with HashMap) - Undo functionality in applications - Music playlist (prev/next) - Browser history (back/forward) - Polynomial representation - Memory management (free lists)

---

Pros and Cons

PROS: - Dynamic size - grows/shrinks easily - O(1) insertion/deletion at head - No wasted memory from pre-allocation - Easy to implement stacks and queues - No shifting elements needed for insert/delete - Can easily split or merge lists

CONS: - O(n) random access - no indexing - Extra memory for pointers - Not cache-friendly (scattered memory) - No backward traversal (singly linked) - More complex to implement than arrays - Can't do binary search efficiently

SINGLY vs DOUBLY: - Singly: Less memory, simpler, can't traverse backward - Doubly: More memory, O(1) delete with node ref, bidirectional traversal

---

Implementation

Node Structure

// Singly Linked List Node
class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

// Doubly Linked List Node
class DoublyListNode {
    int val;
    DoublyListNode prev;
    DoublyListNode next;

    DoublyListNode(int val) {
        this.val = val;
        this.prev = null;
        this.next = null;
    }
}

Singly Linked List

public class SinglyLinkedList {
    private ListNode head;
    private ListNode tail;
    private int size;

    public SinglyLinkedList() {
        head = null;
        tail = null;
        size = 0;
    }

    // Insert at head - O(1)
    public void addFirst(int val) {
        ListNode newNode = new ListNode(val);
        newNode.next = head;
        head = newNode;
        if (tail == null) {
            tail = head;
        }
        size++;
    }

    // Insert at tail - O(1) with tail pointer
    public void addLast(int val) {
        ListNode newNode = new ListNode(val);
        if (tail == null) {
            head = tail = newNode;
        } else {
            tail.next = newNode;
            tail = newNode;
        }
        size++;
    }

    // Insert at index - O(n)
    public void addAt(int index, int val) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException();
        }
        if (index == 0) {
            addFirst(val);
            return;
        }
        if (index == size) {
            addLast(val);
            return;
        }

        ListNode prev = getNode(index - 1);
        ListNode newNode = new ListNode(val);
        newNode.next = prev.next;
        prev.next = newNode;
        size++;
    }

    // Delete at head - O(1)
    public int removeFirst() {
        if (head == null) {
            throw new NoSuchElementException();
        }
        int val = head.val;
        head = head.next;
        if (head == null) {
            tail = null;
        }
        size--;
        return val;
    }

    // Delete at tail - O(n) for singly linked
    public int removeLast() {
        if (head == null) {
            throw new NoSuchElementException();
        }
        if (head == tail) {
            return removeFirst();
        }

        ListNode prev = head;
        while (prev.next != tail) {
            prev = prev.next;
        }
        int val = tail.val;
        prev.next = null;
        tail = prev;
        size--;
        return val;
    }

    // Get by index - O(n)
    public int get(int index) {
        return getNode(index).val;
    }

    private ListNode getNode(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        ListNode current = head;
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        return current;
    }

    // Search - O(n)
    public boolean contains(int val) {
        ListNode current = head;
        while (current != null) {
            if (current.val == val) {
                return true;
            }
            current = current.next;
        }
        return false;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }
}

Doubly Linked List

public class DoublyLinkedList {
    private DoublyListNode head;
    private DoublyListNode tail;
    private int size;

    public void addFirst(int val) {
        DoublyListNode newNode = new DoublyListNode(val);
        if (head == null) {
            head = tail = newNode;
        } else {
            newNode.next = head;
            head.prev = newNode;
            head = newNode;
        }
        size++;
    }

    public void addLast(int val) {
        DoublyListNode newNode = new DoublyListNode(val);
        if (tail == null) {
            head = tail = newNode;
        } else {
            newNode.prev = tail;
            tail.next = newNode;
            tail = newNode;
        }
        size++;
    }

    // Delete given node - O(1)
    public void removeNode(DoublyListNode node) {
        if (node.prev != null) {
            node.prev.next = node.next;
        } else {
            head = node.next;
        }

        if (node.next != null) {
            node.next.prev = node.prev;
        } else {
            tail = node.prev;
        }
        size--;
    }

    // Delete at tail - O(1) for doubly linked
    public int removeLast() {
        if (tail == null) {
            throw new NoSuchElementException();
        }
        int val = tail.val;
        if (head == tail) {
            head = tail = null;
        } else {
            tail = tail.prev;
            tail.next = null;
        }
        size--;
        return val;
    }
}

---

Common Patterns & Problems

Reverse Linked List

// Iterative - O(n) time, O(1) space
public ListNode reverseIterative(ListNode head) {
    ListNode prev = null;
    ListNode current = head;

    while (current != null) {
        ListNode next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }
    return prev;
}

// Recursive - O(n) time, O(n) space (call stack)
public ListNode reverseRecursive(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }

    ListNode newHead = reverseRecursive(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
}

Detect Cycle (Floyd's Algorithm)

// Detect if cycle exists - O(n) time, O(1) space
public boolean hasCycle(ListNode head) {
    if (head == null) return false;

    ListNode slow = head;
    ListNode fast = head;

    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            return true;
        }
    }
    return false;
}

// Find cycle start
public ListNode detectCycle(ListNode head) {
    if (head == null) return null;

    ListNode slow = head;
    ListNode fast = head;

    // Find meeting point
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            break;
        }
    }

    if (fast == null || fast.next == null) {
        return null;  // No cycle
    }

    // Find cycle start
    slow = head;
    while (slow != fast) {
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
}

Find Middle Element

// O(n) time, O(1) space
public ListNode findMiddle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;

    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;  // For even length, returns second middle
}

Merge Two Sorted Lists

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode current = dummy;

    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            current.next = l1;
            l1 = l1.next;
        } else {
            current.next = l2;
            l2 = l2.next;
        }
        current = current.next;
    }

    current.next = (l1 != null) ? l1 : l2;
    return dummy.next;
}

Remove Nth Node From End

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode fast = dummy;
    ListNode slow = dummy;

    // Move fast n+1 steps ahead
    for (int i = 0; i <= n; i++) {
        fast = fast.next;
    }

    // Move both until fast reaches end
    while (fast != null) {
        fast = fast.next;
        slow = slow.next;
    }

    slow.next = slow.next.next;
    return dummy.next;
}

Check Palindrome

public boolean isPalindrome(ListNode head) {
    if (head == null || head.next == null) return true;

    // Find middle
    ListNode slow = head, fast = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    // Reverse second half
    ListNode secondHalf = reverseIterative(slow.next);

    // Compare
    ListNode p1 = head, p2 = secondHalf;
    while (p2 != null) {
        if (p1.val != p2.val) return false;
        p1 = p1.next;
        p2 = p2.next;
    }

    return true;
}

LRU Cache (Doubly Linked List + HashMap)

class LRUCache {
    private Map<Integer, DoublyListNode> cache;
    private DoublyListNode head, tail;
    private int capacity;

    class DoublyListNode {
        int key, value;
        DoublyListNode prev, next;
        DoublyListNode(int k, int v) { key = k; value = v; }
    }

    public LRUCache(int capacity) {
        this.capacity = capacity;
        cache = new HashMap<>();
        head = new DoublyListNode(0, 0);
        tail = new DoublyListNode(0, 0);
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        if (!cache.containsKey(key)) return -1;
        DoublyListNode node = cache.get(key);
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        if (cache.containsKey(key)) {
            DoublyListNode node = cache.get(key);
            node.value = value;
            moveToHead(node);
        } else {
            DoublyListNode newNode = new DoublyListNode(key, value);
            cache.put(key, newNode);
            addToHead(newNode);
            if (cache.size() > capacity) {
                DoublyListNode removed = removeTail();
                cache.remove(removed.key);
            }
        }
    }

    private void addToHead(DoublyListNode node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(DoublyListNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void moveToHead(DoublyListNode node) {
        removeNode(node);
        addToHead(node);
    }

    private DoublyListNode removeTail() {
        DoublyListNode node = tail.prev;
        removeNode(node);
        return node;
    }
}

---

Tips & Tricks

Dummy Head: - Use dummy node to simplify edge cases - Avoids special handling for head operations - Return dummy.next as the actual head

Two Pointers: - Fast/slow for middle, cycle detection - Gap of n for finding nth from end

Common Edge Cases: - Empty list (head == null) - Single node - Two nodes - Cycle at head or tail

Java Collections: - LinkedList<E> - doubly linked - Implements List, Deque interfaces - Use for stack/queue implementations

Interview Tips: - Draw pictures - linked lists are visual - Track pointers carefully - Consider using recursion for elegance - Don't forget to update all pointers

---