Singly & Doubly Linked Lists

Node Structure

The fundamental building block of a linked list is the Node. Think of a node like a box with two compartments: one compartment holds your actual data (like a number), and the other compartment holds an arrow (pointer) that tells you where the next box is located in memory. Each node stores data and a reference to the next node in the sequence. When you create a linked list, you are essentially creating a chain of these boxes connected by arrows.

class ListNode {
    int val;        // Data stored in this node
    ListNode next;  // Reference to the next node
    
    // Default constructor
    ListNode() {}
    
    // Constructor with value
    ListNode(int val) {
        this.val = val;
    }
    
    // Constructor with value and next pointer
    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

List Class Structure

The list class is like a manager that keeps track of your chain of nodes. It maintains a head pointer which is like a bookmark pointing to the very first node - this is your entry point into the list. Without the head, you would have no way to find where your list starts! It also tracks the size (total number of nodes) so you can instantly know how many elements you have without counting them one by one.

class SinglyLinkedList {
    private ListNode head;  // Points to first node
    private int size;       // Tracks number of nodes
    
    public SinglyLinkedList() {
        this.head = null;   // Empty list
        this.size = 0;
    }
    
    public boolean isEmpty() {
        return head == null;
    }
    
    public int size() {
        return size;
    }
}

Add at Head - O(1)

The fastest insertion because it takes the same amount of time no matter how big your list is! Here is how it works: first, create a brand new node with your data. Then, make this new node point to whatever the current head is pointing to (the old first node). Finally, update the head to point to your new node. Now your new node is the first one in line! This is O(1) because we only change two pointers regardless of list size.

   STEP 1: Create new node with value 5
   
   newNode
      │
      ▼
   ┌──────┐
   │  5   │     ┌──────┐     ┌──────┐
   │ null │     │  10  │────▶│  20  │────▶ null
   └──────┘     └──────┘     └──────┘
                    ▲
                    │
                  HEAD

   STEP 2: Point newNode.next to current HEAD
   
   newNode
      │
      ▼
   ┌──────┐     ┌──────┐     ┌──────┐
   │  5   │────▶│  10  │────▶│  20  │────▶ null
   └──────┘     └──────┘     └──────┘
                    ▲
                    │
                  HEAD

   STEP 3: Move HEAD to point to newNode - DONE!
   
   ┌──────┐     ┌──────┐     ┌──────┐
   │  5   │────▶│  10  │────▶│  20  │────▶ null
   └──────┘     └──────┘     └──────┘
      ▲
      │
    HEAD

   Result: [5 -> 10 -> 20] - Only 2 pointer operations!

public void addFirst(int val) {
    ListNode newNode = new ListNode(val);
    newNode.next = head;  // Point new node to current head
    head = newNode;       // Update head to new node
    size++;
}
// Example: addFirst(5) on [10 -> 20] becomes [5 -> 10 -> 20]

Add at Tail - O(n)

Adding at the end is slower because we need to walk through every single node to find the last one! Starting from the head, we follow each arrow until we find a node whose next pointer is null (meaning there is no node after it). Once we find this last node, we simply change its next pointer to point to our new node. The time depends on how many nodes we have to visit, so it is O(n) where n is the list length.

public void addLast(int val) {
    ListNode newNode = new ListNode(val);
    
    if (head == null) {
        head = newNode;  // List was empty
    } else {
        ListNode curr = head;
        while (curr.next != null) {  // Find last node
            curr = curr.next;
        }
        curr.next = newNode;  // Attach at end
    }
    size++;
}
// Example: addLast(30) on [10 -> 20] becomes [10 -> 20 -> 30]

Add at Index - O(n)

To insert at a specific position (like index 2), you need to find the node right before that spot. Why? Because you need to change that node's next pointer to point to your new node, and your new node needs to point to what was previously next. It is like cutting a chain, inserting a new link, and reconnecting everything. We traverse index-1 nodes to reach the spot, making this O(n) in the worst case.

public void addAtIndex(int index, int val) {
    if (index < 0 || index > size) return;  // Invalid index
    
    if (index == 0) {
        addFirst(val);  // Reuse existing method
        return;
    }
    
    ListNode newNode = new ListNode(val);
    ListNode curr = head;
    
    for (int i = 0; i < index - 1; i++) {  // Stop one before target
        curr = curr.next;
    }
    
    newNode.next = curr.next;  // New node points to next
    curr.next = newNode;       // Previous points to new node
    size++;
}

Remove First - O(1)

Removing the first node is super simple and fast! Just move the head pointer to point to the second node instead of the first. What happens to the old first node? Since nothing points to it anymore, it becomes "orphaned" and Java's garbage collector automatically cleans it up from memory. No need to traverse anything - just one pointer change - so it is O(1) constant time!

public int removeFirst() {
    if (head == null) throw new RuntimeException("List is empty");
    
    int val = head.val;   // Save value to return
    head = head.next;     // Move head forward
    size--;
    return val;
}
// Example: removeFirst() on [10 -> 20 -> 30] returns 10, list becomes [20 -> 30]

Remove at Index - O(n)

To remove a node at a specific position, you first need to find the node just before it. Why? Because you need to update that previous node's next pointer to skip over the node being deleted and point directly to the node after it. This "bypasses" the unwanted node, effectively removing it from the chain. The bypassed node gets garbage collected. Since we may need to traverse up to n-1 nodes to find the position, this is O(n).

   STEP 1: Traverse to node BEFORE index 1 (stop at index 0)
   
   ┌──────┐     ┌──────┐     ┌──────┐
   │  10  │────▶│  20  │────▶│  30  │────▶ null
   └──────┘     └──────┘     └──────┘
      ▲            ▲
      │            │
    HEAD         TARGET
    curr        (to remove)

   STEP 2: Save the value (20) to return later
   
   val = curr.next.val = 20

   STEP 3: Bypass - Make curr.next skip over the target
   
   curr.next = curr.next.next
   
   ┌──────┐     ┌──────┐     ┌──────┐
   │  10  │──┐  │  20  │────▶│  30  │────▶ null
   └──────┘  │  └──────┘     └──────┘
      ▲      │      ▲            ▲
      │      │   (orphaned)      │
    HEAD     └───────────────────┘
    curr         BYPASSED!

   STEP 4: Garbage collector cleans up orphaned node - DONE!
   
   ┌──────┐     ┌──────┐
   │  10  │────▶│  30  │────▶ null
   └──────┘     └──────┘
      ▲
      │
    HEAD

   Result: [10 -> 30], returned value: 20

public int removeAtIndex(int index) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException();
    }
    
    if (index == 0) return removeFirst();
    
    ListNode curr = head;
    for (int i = 0; i < index - 1; i++) {  // Stop one before target
        curr = curr.next;
    }
    
    int val = curr.next.val;       // Save value
    curr.next = curr.next.next;    // Bypass the node
    size--;
    return val;
}

Get and Print - O(n)

Unlike arrays where you can jump directly to any index, linked lists require you to start from the head and follow the chain node by node. To get the element at index 3, you must visit nodes 0, 1, 2, and then 3 - there are no shortcuts! Similarly, printing the entire list means visiting every single node from head to tail. Both operations are O(n) because the time grows linearly with the number of elements you need to traverse.

public int get(int index) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException();
    }
    
    ListNode curr = head;
    for (int i = 0; i < index; i++) {
        curr = curr.next;
    }
    return curr.val;
}

public void printList() {
    ListNode curr = head;
    while (curr != null) {
        System.out.print(curr.val + " -> ");
        curr = curr.next;
    }
    System.out.println("null");
}
// Output: 10 -> 20 -> 30 -> null

Basic Traversal - O(n)

Traversal means visiting every node in the list one by one. Think of it like walking through a train - you start at the engine (head) and walk through each carriage until you reach the end. We use a curr pointer that starts at the head and keeps moving to curr.next until it becomes null (end of the list). This is the foundation for almost every linked list operation!

void traverse(ListNode head) {
    ListNode curr = head;       // Start at the beginning
    while (curr != null) {      // Keep going until we hit null
        System.out.println(curr.val);  // Process current node
        curr = curr.next;       // Move to next node
    }
}
// Example: For [10 -> 20 -> 30], prints: 10, 20, 30

Find Length - O(n)

To count how many nodes are in the list, we traverse the entire list while incrementing a counter for each node we visit. Since we do not have random access like arrays, we cannot just ask for the length - we must physically walk through and count each node. This is why many linked list classes store a size variable to avoid counting every time!

int length(ListNode head) {
    int count = 0;              // Start counter at zero
    ListNode curr = head;
    while (curr != null) {
        count++;                // Found a node, increment!
        curr = curr.next;
    }
    return count;               // Total nodes visited
}
// Example: For [10 -> 20 -> 30], returns 3

Search for Value - O(n)

Searching means checking if a specific value exists in the list. We traverse the list and compare each node's data with our target value. If we find a match, we return true immediately (no need to keep searching). If we reach the end (null) without finding it, the value does not exist in the list. In the worst case, we check every single node.

boolean search(ListNode head, int target) {
    ListNode curr = head;
    while (curr != null) {
        if (curr.val == target) {
            return true;        // Found it! Stop searching
        }
        curr = curr.next;
    }
    return false;               // Reached end, not found
}
// Example: search([10 -> 20 -> 30], 20) returns true

Get Nth Node - O(n)

To get the node at a specific position (like index 2), we start from the head and move forward exactly n times. Unlike arrays where arr[n] is instant, linked lists require us to "hop" through n nodes to reach our destination. If n is larger than the list size, we will hit null before reaching position n.

ListNode getNth(ListNode head, int n) {
    ListNode curr = head;
    for (int i = 0; i < n && curr != null; i++) {
        curr = curr.next;       // Hop to next node
    }
    return curr;                // Returns node at position n (or null)
}
// Example: getNth([10 -> 20 -> 30], 1) returns node with value 20

Reverse List (Iterative) - O(n)

Reversing a linked list is a classic interview question! The idea is to flip all the arrows so they point backward instead of forward. We use three pointers: prev (node behind us), curr (current node), and next (temporarily saves the next node before we flip the arrow). We visit each node once and flip its pointer to point to the previous node instead of the next.

ListNode reverse(ListNode head) {
    ListNode prev = null;       // Nothing before head initially
    ListNode curr = head;
    
    while (curr != null) {
        ListNode next = curr.next;  // Save next before we lose it!
        curr.next = prev;           // Flip the arrow backward
        prev = curr;                // Move prev forward
        curr = next;                // Move curr forward
    }
    
    return prev;  // prev is now the new head (old tail)
}
// Example: [1 -> 2 -> 3] becomes [3 -> 2 -> 1]

Reverse List (Recursive) - O(n)

The recursive approach is trickier to understand but elegant! We keep diving deeper until we reach the last node (our new head). Then, as the recursion unwinds back up, we flip each pointer. The key trick is head.next.next = head which makes the next node point back to us. This uses O(n) extra space due to the call stack storing each recursive call.

ListNode reverseRecursive(ListNode head) {
    // Base case: empty list or single node
    if (head == null || head.next == null) {
        return head;
    }
    
    // Recursively reverse the rest of the list
    ListNode newHead = reverseRecursive(head.next);
    
    // Make next node point back to current node
    head.next.next = head;  // The magic line!
    head.next = null;       // Remove old forward pointer
    
    return newHead;  // Keep passing back the new head
}

Find Middle (Two Pointers) - O(n)

This clever technique uses two pointers moving at different speeds - like a race between a turtle and a rabbit! The slow pointer moves one step at a time, while the fast pointer moves two steps. When fast reaches the end, slow will be exactly at the middle! This works because fast covers twice the distance in the same number of iterations.

ListNode findMiddle(ListNode head) {
    ListNode slow = head;       // Turtle - 1 step at a time
    ListNode fast = head;       // Rabbit - 2 steps at a time
    
    while (fast != null && fast.next != null) {
        slow = slow.next;       // Move turtle 1 step
        fast = fast.next.next;  // Move rabbit 2 steps
    }
    
    return slow;  // Turtle is at the middle!
}
// Example: [1 -> 2 -> 3 -> 4 -> 5] returns node with value 3
// For even length [1 -> 2 -> 3 -> 4], returns second middle (3)

   DOUBLY LINKED LIST:

         ┌───────────────┐     ┌───────────────┐     ┌───────────────┐
   null◀─┤  prev: null   │◀────┤  prev: ●      │◀────┤  prev: ●      │
         │   data: 10    │     │   data: 20    │     │   data: 30    │
         │  next: ●──────┼────▶│  next: ●──────┼────▶│  next: null   │─▶null
         └───────────────┘     └───────────────┘     └───────────────┘
              ▲                                            ▲
              │                                            │
            HEAD                                         TAIL

   [+] Can traverse BOTH directions!
   [+] With TAIL pointer: addLast() and removeLast() are O(1)

Node Structure (Doubly)

A doubly linked list node has three compartments instead of two: the data, a next pointer (arrow pointing forward to the next node), and a prev pointer (arrow pointing backward to the previous node). Think of it like a train carriage with doors on both ends - you can move forward to the next carriage OR backward to the previous one. This extra pointer costs more memory but gives us powerful bidirectional traversal!

class DoublyListNode {
    int val;                // Data stored in this node
    DoublyListNode prev;    // Arrow pointing BACKWARD
    DoublyListNode next;    // Arrow pointing FORWARD
    
    DoublyListNode(int val) {
        this.val = val;
        // prev and next are null by default
    }
}
// Each node now uses more memory (2 pointers instead of 1)

List Class Structure (Doubly)

The doubly linked list class keeps track of both ends of the chain - a head pointer for the first node AND a tail pointer for the last node. This is the magic that makes tail operations O(1)! Without a tail pointer, we would have to traverse the entire list to find the end. With it, we can instantly access either end of the list in constant time.

class DoublyLinkedList {
    private DoublyListNode head;  // Points to FIRST node
    private DoublyListNode tail;  // Points to LAST node
    private int size;             // Track count
    
    public DoublyLinkedList() {
        this.head = null;   // Empty list
        this.tail = null;   // No tail either
        this.size = 0;
    }
}
// head and tail give us O(1) access to both ends!

Add at Head - O(1)

Adding at the head is similar to singly linked lists, but now we also need to update the prev pointer. After creating the new node, we point its next to the current head, then update the old head's prev to point back to our new node. Finally, we move the head to our new node. If the list was empty, both head and tail point to the new node!

public void addFirst(int val) {
    DoublyListNode newNode = new DoublyListNode(val);
    
    if (head == null) {
        head = tail = newNode;  // First node is both head AND tail
    } else {
        newNode.next = head;    // New node points forward to old head
        head.prev = newNode;    // Old head points back to new node
        head = newNode;         // Update head to new node
    }
    size++;
}
// Example: addFirst(5) on [10 <-> 20] becomes [5 <-> 10 <-> 20]

Add at Tail - O(1)

This is where doubly linked lists really shine! Because we have a tail pointer, adding at the end is now O(1) - no traversal needed! We create the new node, make the current tail's next point to it, set the new node's prev to point back to the old tail, and finally update tail to the new node. Compare this to singly linked lists where we had to traverse the entire list!

public void addLast(int val) {
    DoublyListNode newNode = new DoublyListNode(val);
    
    if (tail == null) {
        head = tail = newNode;  // First node is both head AND tail
    } else {
        tail.next = newNode;    // Old tail points forward to new node
        newNode.prev = tail;    // New node points back to old tail
        tail = newNode;         // Update tail to new node
    }
    size++;
}
// Example: addLast(30) on [10 <-> 20] becomes [10 <-> 20 <-> 30]
// This is O(1) - no traversal needed!

Remove First - O(1)

Removing the first node requires updating the head to point to the second node, then clearing the new head's prev pointer (since there is nothing before the head now). We also need to handle the special case where removing the only node leaves the list empty - both head and tail become null. The old head gets garbage collected automatically!

public int removeFirst() {
    if (head == null) throw new RuntimeException("Empty list!");
    
    int val = head.val;         // Save value to return
    
    if (head == tail) {
        head = tail = null;     // Was the only node, list now empty
    } else {
        head = head.next;       // Move head to second node
        head.prev = null;       // New head has nothing before it
    }
    size--;
    return val;
}
// Example: removeFirst() on [10 <-> 20 <-> 30] returns 10, list becomes [20 <-> 30]

Remove Last - O(1)

Another huge advantage of doubly linked lists! In a singly linked list, removing from the end is O(n) because we cannot go backward to find the second-to-last node. But here, we simply use tail.prev to instantly access it! We update tail to point to the second-to-last node and set its next to null. No traversal needed!

public int removeLast() {
    if (tail == null) throw new RuntimeException("Empty list!");
    
    int val = tail.val;         // Save value to return
    
    if (head == tail) {
        head = tail = null;     // Was the only node, list now empty
    } else {
        tail = tail.prev;       // Move tail backward to second-to-last
        tail.next = null;       // New tail has nothing after it
    }
    size--;
    return val;
}
// Example: removeLast() on [10 <-> 20 <-> 30] returns 30, list becomes [10 <-> 20]
// This is O(1) - no traversal needed! (vs O(n) in singly linked list)

Initial State:
head                                    tail
  |                                       |
  v                                       v
[10] <--> [20] <--> [30]
         prev      prev
         
=== STEP 1: Save the value to return ===
val = tail.val = 30

=== STEP 2: Move tail backward ===
tail = tail.prev
        
head               tail     (old tail)
  |                  |           |
  v                  v           v
[10] <--> [20]      [30]
                      ^
            tail.next still points here

=== STEP 3: Cut the forward connection ===
tail.next = null

head               tail
  |                  |
  v                  v
[10] <--> [20] --> null     [30] (orphaned)
                              ^
                      Gets garbage collected!

Final State:
head               tail
  |                  |
  v                  v
[10] <--> [20]

Return 30

Remove Any Node - O(1)

This is the killer feature of doubly linked lists! If you already have a reference to a node (like from a HashMap in an LRU cache), you can remove it in O(1) time without knowing its position. You just tell the previous node to skip over you and point to your next, and tell the next node to point back to your previous. You are essentially "unlinking" yourself from the chain!

public void removeNode(DoublyListNode node) {
    // Update the node BEFORE us (if it exists)
    if (node.prev != null) {
        node.prev.next = node.next;  // Skip over us
    } else {
        head = node.next;            // We were the head
    }
    
    // Update the node AFTER us (if it exists)
    if (node.next != null) {
        node.next.prev = node.prev;  // Skip back over us
    } else {
        tail = node.prev;            // We were the tail
    }
    size--;
}
// Given a direct reference to a node, removal is O(1)!
// This is why doubly linked lists are used in LRU caches

Initial State:
head                                    tail
  |                                       |
  v                                       v
[10] <--> [20] <--> [30]
           ^
         node (we have direct reference)
         
=== STEP 1: Make node.prev.next skip over node ===
node.prev.next = node.next

head                                    tail
  |                                       |
  v                                       v
[10] -----> [30]           [20] still points to both
       ^                        |   |
       |-------- skipped -------|   |
                                    v
                               still linked
                               
=== STEP 2: Make node.next.prev skip back over node ===
node.next.prev = node.prev

head                                    tail
  |                                       |
  v                                       v
[10] <--> [30]             [20] (orphaned)
                            ^
                    No one points to [20] now
                    Gets garbage collected!

Final State:
head               tail
  |                  |
  v                  v
[10] <--> [30]

Print Forward and Backward - O(n)

The beauty of bidirectional traversal! We can print the list from head to tail (following next pointers) OR from tail to head (following prev pointers). This is impossible with singly linked lists where we can only go forward. This flexibility makes doubly linked lists perfect for browser history (back/forward), undo/redo features, and music playlists!

// Print from HEAD to TAIL (forward)
public void printForward() {
    DoublyListNode curr = head;
    while (curr != null) {
        System.out.print(curr.val + " <-> ");
        curr = curr.next;       // Follow forward arrows
    }
    System.out.println("null");
}
// Output: 10 <-> 20 <-> 30 <-> null

// Print from TAIL to HEAD (backward)
public void printBackward() {
    DoublyListNode curr = tail;
    while (curr != null) {
        System.out.print(curr.val + " <-> ");
        curr = curr.prev;       // Follow backward arrows
    }
    System.out.println("null");
}
// Output: 30 <-> 20 <-> 10 <-> null

Understanding the Trade-offs

Let us break down why these differences exist. This deeper understanding will help you make better decisions in interviews and real projects.

Array Memory:
Address:  100  104  108  112  116
Data:    [ 5 ][ 3 ][ 8 ][ 1 ][ 9 ]
Index:     0    1    2    3    4

To access index 3:
Address = BaseAddress + (index × size)
        = 100 + (3 × 4) = 112
One calculation, instant access!

LinkedList Memory:
[5|ptr]-->[3|ptr]-->[8|ptr]-->[1|null]
 @100      @500      @200      @800

To insert at head (before 5):
1. Create new node at any free spot
2. Point new node to old head
3. Update head pointer

No shifting needed!

Cache Performance Explained

Modern CPUs have multiple levels of cache (L1, L2, L3) that are much faster than main memory. When you access memory, the CPU loads nearby data into cache, assuming you will need it next. This is called a "cache line".

When you access arr[0], CPU loads:
[arr[0]][arr[1]][arr[2]][arr[3]]...

Next access to arr[1]?
Already in cache! Super fast!

This is called "spatial locality"

Node at @100, next node at @5000:
CPU loads data around @100...
Node at @5000 not in cache!

Cache miss! Load from main memory
(~100x slower than cache hit)

Understanding where linked lists are used in the real world helps you recognize when to use them in your own projects.

Google <--> YouTube <--> GitHub <--> StackOverflow
                              ^
                         (current page)

Back button: move to prev node
Forward button: move to next node
New URL: insert after current, remove future nodes

Song1 <--> Song2 <--> Song3 <--> Song4
  ^                                 |
  |_________________________________|
        (circular for repeat)

Next: current = current.next
Prev: current = current.prev
Shuffle: rearrange node pointers

Action Stack (linked list of states):

[Empty] <-- [Type "H"] <-- [Type "Hi"] <-- [Delete "i"]
                                              ^
                                          (current)

Undo: move backward, restore previous state
Redo: move forward, re-apply change
New action: insert after current, clear redo history

Process Queue (circular linked list):

[Chrome] --> [VSCode] --> [Spotify] --> [Chrome]...
    ^
(currently running)

Give each process a time slice
Move to next process
Circular ensures fair rotation

Most Recent                    Least Recent
[Page D] <--> [Page A] <--> [Page C] <--> [Page B]
    ^                                         ^
   HEAD                                      TAIL
(newest)                                   (evict)

Access Page C: move it to head
Cache full + new page: remove tail, add at head

Hash Table with Chaining:

Index 0: [K1,V1] --> [K5,V5] --> null
Index 1: [K2,V2] --> null
Index 2: [K3,V3] --> [K8,V8] --> [K9,V9] --> null
Index 3: null

K1 and K5 both hash to index 0
They form a linked list at that bucket

Java provides a built-in LinkedList class in the java.util package. This is a fully-featured doubly linked list implementation that you can use right away without building your own. It implements both the List and Deque interfaces, making it incredibly versatile!

Creating a LinkedList

To use Java's LinkedList, first import it from java.util. When creating a LinkedList, you specify the type of elements it will hold using generics (the angle brackets). For example, LinkedList<Integer> creates a list that stores integers. You can also create a LinkedList from an existing collection to copy all its elements.

import java.util.LinkedList;

// Create an empty LinkedList that stores Integers
LinkedList list = new LinkedList<>();

// Create from existing collection
LinkedList names = new LinkedList<>(Arrays.asList("Alice", "Bob"));
// Result: names = ["Alice", "Bob"]

Add Operations - O(1) at ends, O(n) at index

LinkedList provides multiple ways to add elements. addFirst() and addLast() are O(1) since we have direct access to both ends. The generic add() method adds at the tail by default. To insert at a specific position, use add(index, value) which is O(n) since it must traverse to that position first.

LinkedList list = new LinkedList<>();

list.addFirst(1);    // Add at head: [1]
list.addLast(2);     // Add at tail: [1, 2]
list.add(3);         // Add at tail (same as addLast): [1, 2, 3]
list.add(1, 10);     // Add 10 at index 1: [1, 10, 2, 3]

// addFirst/addLast = O(1), add(index) = O(n)

Get Operations - O(1) at ends, O(n) at index

Retrieving elements follows the same pattern. getFirst() and getLast() are O(1) instant access. However, get(index) is O(n) because linked lists do not support random access - you must traverse from the nearest end (head or tail) to reach the target index. Java's implementation is smart enough to start from the closer end!

// Assuming list = [1, 10, 2, 3]

int first = list.getFirst();   // Get head: 1 (O(1))
int last = list.getLast();     // Get tail: 3 (O(1))
int atIndex = list.get(2);     // Get at index 2: 2 (O(n))

// Safe versions that return null instead of throwing exception
Integer peeked = list.peekFirst();  // null if empty
Integer peekedLast = list.peekLast();

Remove Operations - O(1) at ends, O(n) otherwise

Removal at head or tail is O(1). When removing by index with remove(int), it is O(n) to find the position. Here is a tricky part: remove(1) removes the element at index 1, but remove(Integer.valueOf(1)) removes the first occurrence of value 1. This distinction matters when your list contains integers!

// Assuming list = [1, 10, 2, 3]

list.removeFirst();  // Remove head: list = [10, 2, 3]
list.removeLast();   // Remove tail: list = [10, 2]

// IMPORTANT: remove(int) vs remove(Object)
list.remove(0);      // Removes at INDEX 0
list.remove(Integer.valueOf(10));  // Removes VALUE 10

// Safe versions that return null instead of throwing exception
Integer polled = list.pollFirst();  // null if empty
Integer polledLast = list.pollLast();

Utility Methods - O(1) or O(n)

These helper methods make working with LinkedList easier. size() and isEmpty() are O(1) since the size is tracked internally. contains() and indexOf() are O(n) because they must search through the list. clear() removes all elements and resets the list to empty state.

LinkedList list = new LinkedList<>();
list.addAll(Arrays.asList(10, 20, 30, 20));

int size = list.size();           // 4 (O(1))
boolean empty = list.isEmpty();   // false (O(1))
boolean has = list.contains(20);  // true (O(n) - must search)
int idx = list.indexOf(20);       // 1 (first occurrence, O(n))
int lastIdx = list.lastIndexOf(20);  // 3 (last occurrence, O(n))

list.clear();  // Remove all elements, list is now empty

Using as Stack (LIFO) - O(1)

LinkedList can act as a Stack (Last-In-First-Out). Think of a stack of plates - you add and remove from the top only. push() adds to the front (top of stack), pop() removes from the front, and peek() looks at the top without removing. All operations are O(1) since they work at the head!

LinkedList stack = new LinkedList<>();

// Push elements onto stack (adds at head)
stack.push(1);   // Stack: [1]
stack.push(2);   // Stack: [2, 1]
stack.push(3);   // Stack: [3, 2, 1]

// Peek at top without removing
int top = stack.peek();   // Returns 3, stack unchanged

// Pop from stack (removes from head)
int popped = stack.pop(); // Returns 3, stack: [2, 1]

// LIFO: Last pushed (3) was first popped

Using as Queue (FIFO) - O(1)

LinkedList also works as a Queue (First-In-First-Out). Think of a line at a store - first person in line is first to be served. offer() adds to the back of the line (tail), poll() removes from the front (head), and peek() looks at who is first without removing them. Perfect for task scheduling!

LinkedList queue = new LinkedList<>();

// Offer elements to queue (adds at tail)
queue.offer("Task1");  // Queue: [Task1]
queue.offer("Task2");  // Queue: [Task1, Task2]
queue.offer("Task3");  // Queue: [Task1, Task2, Task3]

// Peek at front without removing
String front = queue.peek();   // Returns "Task1"

// Poll from queue (removes from head)
String processed = queue.poll();  // Returns "Task1", queue: [Task2, Task3]

// FIFO: First offered (Task1) was first polled

Iteration Methods - O(n)

You can loop through a LinkedList in several ways. The enhanced for-loop is the simplest and most readable. For backward traversal, use descendingIterator() which walks from tail to head. The ListIterator allows bidirectional traversal and even modification while iterating - useful for complex scenarios!

LinkedList list = new LinkedList<>(Arrays.asList(10, 20, 30));

// Forward iteration (most common)
for (int num : list) {
    System.out.print(num + " ");  // Output: 10 20 30
}

// Backward iteration using descendingIterator
var descIt = list.descendingIterator();
while (descIt.hasNext()) {
    System.out.print(descIt.next() + " ");  // Output: 30 20 10
}

// ListIterator for bidirectional traversal
var listIt = list.listIterator();
while (listIt.hasNext()) {
    int val = listIt.next();
    if (val == 20) listIt.set(25);  // Modify during iteration!
}
// list is now [10, 25, 30]

Even experienced developers make these mistakes when working with linked lists. Learn to recognize and avoid them to write bug-free code!

int getFirst() {
    return head.val;  // CRASH if empty!
}

int getFirst() {
    if (head == null) {
        throw new RuntimeException("Empty!");
    }
    return head.val;
}

while (curr != null) {
    curr.next = prev;  // LOST the rest!
    prev = curr;
    curr = curr.next;  // curr.next is now prev!
}

while (curr != null) {
    ListNode next = curr.next;  // SAVE first!
    curr.next = prev;
    prev = curr;
    curr = next;  // Use saved reference
}

// Delete at index 2
for (int i = 0; i < index; i++) {
    curr = curr.next;
}
// curr is now at index 2
// How do we update index 1's next?

// Delete at index 2
for (int i = 0; i < index - 1; i++) {
    curr = curr.next;
}
// curr is at index 1
curr.next = curr.next.next; // Skip 2

while (fast != null) {
    slow = slow.next;
    fast = fast.next.next;  // CRASH!
}

while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;  // Safe!
}

LinkedList list = new LinkedList<>();
list.addAll(Arrays.asList(5, 1, 3, 1, 7));  // [5, 1, 3, 1, 7]

list.remove(1);                    // Removes at INDEX 1: [5, 3, 1, 7]
list.remove(Integer.valueOf(1));   // Removes VALUE 1: [5, 3, 7]

// To remove a specific value, use Integer.valueOf() or (Integer) cast!

Before jumping to code, learn how to think through linked list problems step by step. This methodical approach will help you solve any linked list problem you encounter.

The 5-Step Problem Solving Framework

Use this framework every time you face a linked list problem:

Example: Reverse list [1, 2, 3]

Before:
[1] --> [2] --> [3] --> null

After:
null <-- [1] <-- [2] <-- [3]

Walk through mentally: What changes at each step?

// Find middle of linked list
1. Create two pointers: slow and fast, both at head
2. While fast can move two steps:
   - Move slow one step
   - Move fast two steps
3. When fast reaches end, slow is at middle
4. Return slow

Walkthrough: Reverse a Linked List

Let us apply the framework to the classic "reverse a linked list" problem.

Original: [1] --> [2] --> [3] --> null

Step-by-step reversal:

Initial:
prev = null
curr = [1] --> [2] --> [3] --> null

After processing [1]:
null <-- [1]    [2] --> [3] --> null
  ^       ^      ^
 prev   (done)  curr

After processing [2]:
null <-- [1] <-- [2]    [3] --> null
          ^       ^      ^
        (done)  prev   curr

After processing [3]:
null <-- [1] <-- [2] <-- [3]    null
                   ^       ^      ^
                (done)   prev   curr

curr is null, we're done! Return prev as new head.

function reverse(head):
    prev = null
    curr = head
    
    while curr is not null:
        next = curr.next    // Save next before we lose it
        curr.next = prev    // Reverse the pointer
        prev = curr         // Move prev forward
        curr = next         // Move curr forward
    
    return prev  // prev is now the new head

public ListNode reverseList(ListNode head) {
    // Handle edge cases
    if (head == null || head.next == null) {
        return head;  // Empty or single node
    }
    
    ListNode prev = null;  // Will become new tail
    ListNode curr = head;  // Start at original head
    
    while (curr != null) {
        // Save next node before we overwrite curr.next
        ListNode nextTemp = curr.next;
        
        // Reverse the pointer
        curr.next = prev;
        
        // Move prev and curr one step forward
        prev = curr;
        curr = nextTemp;
    }
    
    // curr is null, prev points to last node (new head)
    return prev;
}

Walkthrough: Find Middle Node

Another classic problem using the fast/slow pointer technique.

Odd length: [1] --> [2] --> [3] --> [4] --> [5] --> null

Initial:
slow = [1]
fast = [1]

After 1 move:
slow = [2], fast = [3]

After 2 moves:
slow = [3], fast = [5]

After 3 moves:
fast.next is null, STOP
slow = [3] is the middle!

---

Even length: [1] --> [2] --> [3] --> [4] --> null

Initial:
slow = [1], fast = [1]

After 1 move:
slow = [2], fast = [3]

After 2 moves:
slow = [3], fast = null (went past end)
STOP! slow = [3] is the second middle.

function findMiddle(head):
    slow = head
    fast = head
    
    while fast is not null AND fast.next is not null:
        slow = slow.next       // Move 1 step
        fast = fast.next.next  // Move 2 steps
    
    return slow  // slow is at middle

public ListNode middleNode(ListNode head) {
    // Edge case: empty list
    if (head == null) {
        return null;
    }
    
    // Both pointers start at head
    ListNode slow = head;
    ListNode fast = head;
    
    // Fast moves 2x speed of slow
    // Loop while fast can move 2 steps
    while (fast != null && fast.next != null) {
        slow = slow.next;       // 1 step
        fast = fast.next.next;  // 2 steps
    }
    
    // When fast reaches end, slow is at middle
    return slow;
}

// Time: O(n) - traverse half the list
// Space: O(1) - only two pointers

Keep this cheat sheet handy when solving linked list problems. These code snippets are building blocks you can combine.

// Visit every node
ListNode curr = head;
while (curr != null) {
    // Process curr.val
    curr = curr.next;
}

// Count nodes
int count = 0;
ListNode curr = head;
while (curr != null) {
    count++;
    curr = curr.next;
}

// Find first occurrence
ListNode curr = head;
while (curr != null) {
    if (curr.val == target) {
        return curr;  // Found it!
    }
    curr = curr.next;
}
return null;  // Not found

// Find index of value
int index = 0;
while (curr != null) {
    if (curr.val == target) return index;
    curr = curr.next;
    index++;
}
return -1;

// Insert newNode after target
ListNode newNode = new ListNode(val);

// Save what comes after
newNode.next = target.next;

// Insert newNode
target.next = newNode;

// Visual:
// Before: [A] --> [B]
// After:  [A] --> [new] --> [B]

// Need previous node reference!
// Or use dummy node trick

// With prev reference:
ListNode newNode = new ListNode(val);
newNode.next = prev.next;
prev.next = newNode;

// Dummy node approach:
ListNode dummy = new ListNode(0);
dummy.next = head;
// Now dummy is "prev" of head

// Delete the node after prev
// (You need prev to rewire)
prev.next = prev.next.next;

// Visual:
// Before: [prev] --> [X] --> [B]
// After:  [prev] ---------> [B]
//               [X] orphaned, garbage collected

// Delete head (special case):
head = head.next;

// Copy-and-delete trick
// Cannot delete tail this way!
void deleteNode(ListNode node) {
    // Copy next value into current
    node.val = node.next.val;
    // Delete next node
    node.next = node.next.next;
}

// Visual:
// [1] --> [2] --> [3]  delete [2]
// [1] --> [3] --> [3]  copy val
// [1] --> [3]          skip next

ListNode prev = null;
ListNode curr = head;

while (curr != null) {
    ListNode next = curr.next;  // Save
    curr.next = prev;  // Reverse
    prev = curr;       // Advance
    curr = next;
}
return prev;  // New head

// Key: save before you modify!

ListNode reverse(ListNode head) {
    // Base case
    if (head == null || head.next == null) {
        return head;
    }
    
    // Reverse rest of list
    ListNode newHead = reverse(head.next);
    
    // Reverse the link
    head.next.next = head;
    head.next = null;
    
    return newHead;
}

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

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

// Find nth node from end
// Use two pointers, n apart

ListNode first = head;
ListNode second = head;

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

// Move both until first reaches end
while (first != null) {
    first = first.next;
    second = second.next;
}
// second is n-th from end

// Simplifies edge cases
ListNode dummy = new ListNode(0);
dummy.next = head;

// Now even operations on head
// have a "prev" node (dummy)

// At the end:
return dummy.next;  // Actual head

// Useful for: merge lists,
// partition, remove nodes

ListNode merge(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;
    
    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            curr.next = l1;
            l1 = l1.next;
        } else {
            curr.next = l2;
            l2 = l2.next;
        }
        curr = curr.next;
    }
    curr.next = (l1 != null) ? l1 : l2;
    return dummy.next;
}

Linked list problems are interview favorites because they test your understanding of pointers, edge cases, and algorithmic thinking. Here is how to ace them.

Before the Interview

During the Interview

Common Interview Mistakes to Avoid

Complexity Analysis Cheat Sheet

*O(1) if tail pointer is maintained

Visualize how linked list operations work in real-time. Add nodes, remove them, and see the pointer connections update!