Linked List

A linked list stores elements in nodes connected by pointers rather than in a single contiguous array.

Each node typically contains:

• The value.
• A pointer/reference to the next node (and optionally the previous node).

This gives linked lists different trade‑offs from arrays.

Singly vs Doubly Linked Lists

• Singly linked list:
  • Each node has next.
  • Can traverse forward only.
• Doubly linked list:
  • Each node has prev and next.
  • Can traverse both directions.
  • Slightly more memory and pointer complexity, but more flexible for insert/delete.

In high‑level languages:

• Java: LinkedList<E> is a doubly‑linked list.
• Many libraries implement custom lists as internal nodes with prev/next.

Operations and Complexity

Operation	Complexity
Access k‑th element by index	O(k) (must traverse from head)
Insert/delete at head	O(1)
Insert/delete after given node	O(1) (if you already have the node)
Insert/delete at arbitrary index	O(n) (need to traverse first)
Search by value	O(n)

Compared to arrays:

• Linked lists are good at local insert/delete when you already have a pointer to the node.
• They are bad at random indexing and cache locality.

When Linked Lists Shine

Typical use cases:

• Implementing queues and stacks when you frequently push/pop at ends.
• Maintaining ordered collections with frequent insert/delete in the middle, where you already have node references.
• Building LRU caches in combination with hash maps:
  • HashMap for O(1) key → node lookup.
  • Doubly linked list to move recently used items to the front and evict from the tail.

In modern high‑level languages, dynamic arrays (ArrayList, vector) often outperform linked lists for general workloads due to better cache behavior, but linked lists are still valuable for specific patterns.

Linked Lists in Interviews

Common linked list problems:

• Reverse a list (iterative or recursive).
• Detect cycle (Floyd’s fast/slow pointer).
• Find the middle node (fast/slow pointer).
• Merge two sorted lists.
• Remove N‑th node from end (two pointers).

These problems are more about pointer manipulation and invariants than about asymptotic complexity.

Example: Iteratively Reversing a Singly Linked List (Java)

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

ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode next = curr.next; // save next
        curr.next = prev;          // reverse pointer
        prev = curr;               // move prev
        curr = next;               // move curr
    }
    return prev; // new head
}

Tracing this on a 3‑node list by hand is a good exercise to internalize pointer updates.

Pitfalls

• Null pointer bugs (forgetting to check head == null, node.next == null).
• Losing references when rearranging nodes (update order matters).
• Off‑by‑one errors in deletion (especially near head/tail).

When coding, draw a small diagram and trace each pointer change step by step to avoid mistakes.