Linked Lists Basics

1. Introduction: The Dynamic Chain

Imagine a train where each car is connected to the next one. You can easily add a new car in the middle by unhooking two cars and placing the new one between them. You don't have to move all the passengers to new cars. This is the essence of a Linked List.

In contrast to an Array, which is a contiguous block of memory (like a stadium where all seats are strictly next to each other), a Linked List is a dynamic data structure scattered throughout memory. Each element (a Node) contains its data and a "pointer" or "reference" to the exact memory address of the next node.

This fundamental difference means that Linked Lists excel at insertions and deletions ($O(1)$ if you have the pointer), but struggle with random access ($O(N)$ because you can't just jump to index 5; you must traverse from the beginning).

2. Core Concept: Nodes and Pointers

A Linked List is built using a recursive object structure. Every Node contains two components:

1. val (or data): The actual information being stored (an integer, string, object).
2. next: A reference (pointer) to the next Node in the sequence. If it is the last node, next is null.

The entire list is referenced by a single pointer called the head. If you lose the head, the entire list becomes unreachable and gets destroyed by the Garbage Collector!

Singly vs Doubly Linked Lists

• Singly Linked List: Nodes only point strictly forward (next). You cannot traverse backward.
• Doubly Linked List: Nodes contain an additional prev pointer pointing to the previous node. This allows $O(1)$ backward traversal at the cost of double the pointer memory overhead.

3. Beginner Code Example: The Node Class and Traversal

Problem: Define a Singly Linked List and traverse it to print all its values.

// The standard LeetCode Node Definition
class ListNode {
    int val;
    ListNode next;
    
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

public class LinkedListTraversal {
    public static void printList(ListNode head) {
        // ALWAYS use a temporary pointer for traversal. 
        // If you move 'head', you lose the start of your list forever!
        ListNode current = head;
        
        while (current != null) {
            System.out.print(current.val + " -> ");
            current = current.next; // Move to the next node
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        // Building a list: 1 -> 2 -> 3 -> null
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        
        printList(head);
    }
}

Complexity Analysis:

• Time Complexity: $O(N)$ because we visit every node exactly once.
• Space Complexity: $O(1)$ since we only use a single current pointer, regardless of the list size.

4. Intermediate Code Example: Search and Count

Problem Statement: Write a method to search for a specific value in a Singly Linked List, and another method to count the total number of nodes.

This reinforces the concept that we have no .length property like arrays. We must calculate the length manually.

public class LinkedListOperations {
    
    // O(N) Time, O(1) Space
    public static boolean search(ListNode head, int target) {
        ListNode current = head;
        
        while (current != null) {
            if (current.val == target) {
                return true; // Target found
            }
            current = current.next;
        }
        
        return false; // Reached the end without finding target
    }
    
    // O(N) Time, O(1) Space
    public static int getLength(ListNode head) {
        int count = 0;
        ListNode current = head;
        
        while (current != null) {
            count++;
            current = current.next;
        }
        
        return count;
    }
}

5. Advanced Code Example: Doubly Linked List

In advanced real-world applications (like a browser's Back/Forward history, or building an LRU Cache), we use Doubly Linked Lists.

Implementation Insight: We must manage both next and prev pointers. When inserting or deleting, failing to update even one of these pointers leads to memory leaks or broken traversals.

class DoublyNode {
    int val;
    DoublyNode prev;
    DoublyNode next;
    
    DoublyNode(int val) { this.val = val; }
}

public class DoublyLinkedListDemo {
    public static void printReverse(DoublyNode tail) {
        // Assuming we are given the tail pointer
        DoublyNode current = tail;
        
        while (current != null) {
            System.out.print(current.val + " <- ");
            current = current.prev; // Traverse BACKWARD
        }
        System.out.println("null");
    }
    
    // Deleting a node in O(1) time (assuming we already have the node reference)
    public static void deleteNode(DoublyNode nodeToDelete) {
        if (nodeToDelete == null) return;
        
        DoublyNode prevNode = nodeToDelete.prev;
        DoublyNode nextNode = nodeToDelete.next;
        
        // Link the previous node to the next node (bypassing nodeToDelete)
        if (prevNode != null) {
            prevNode.next = nextNode;
        }
        
        // Link the next node to the previous node
        if (nextNode != null) {
            nextNode.prev = prevNode;
        }
        
        // Isolate the deleted node to help the Garbage Collector
        nodeToDelete.prev = null;
        nodeToDelete.next = null;
    }
}

Complexity Analysis:

• Time Complexity: $O(1)$ for deletion IF you are provided the node pointer. (Unlike Arrays which take $O(N)$ to shift elements).
• Space Complexity: $O(1)$ auxiliary space.

6. Common Mistakes Beginners Make

1. Losing the Head Pointer

   • The Mistake: Writing while(head != null) { head = head.next; }.
   • Why it's wrong: The function executes fine, but when you return to your main program, your head variable now points to null! You have permanently lost access to the entire data structure.
   • The Fix: Always create a dummy/temporary pointer: ListNode current = head;.

2. NullPointerException on .next

   • The Mistake: if (current.next.val == target) without checking if current.next is null.
   • Why it's wrong: If you are at the last node, current.next is null. Attempting to access .val on null crashes the program.
   • The Fix: Always verify pointers are non-null before dereferencing them.

3. Thinking .length exists

   • The Mistake: for(int i = 0; i < list.length; i++)
   • Why it's wrong: Arrays track length internally. Linked Lists do not. If you need the length, you must traverse the whole list manually.

7. Interview Q&A

Q1: Why use a Linked List over an Array? Answer: Linked Lists are preferred when you expect frequent $O(1)$ insertions and deletions in the middle of a sequence, and you don't know the final size of the data structure in advance (avoiding the massive $O(N)$ array resizing penalty).

Q2: What is the main disadvantage of a Linked List? Answer: Poor Cache Locality. Array elements are physically adjacent in RAM, meaning the CPU can load them in a single fast cache line. Linked List nodes are scattered randomly across the heap, causing frequent CPU Cache Misses, which makes them physically slower to traverse than arrays, even though both are mathematically $O(N)$. Furthermore, the lack of $O(1)$ index access is a major limitation.

Q3: Does Java have a built-in Linked List? Answer: Yes, java.util.LinkedList. It is a Doubly Linked List implementation. However, in technical interviews, you are almost always required to use the custom ListNode class and manipulate pointers manually, rather than using the built-in Collection.

8. Practice Problems

1. Middle of the Linked List (LeetCode 876)
   • Hint: Traverse to find the length, then traverse again to length / 2.
2. Design Linked List (LeetCode 707)
   • Goal: Build a Singly or Doubly linked list class from scratch with add, delete, and get operations.
3. Delete Node in a Linked List (LeetCode 237)
   • Hint: A trick question where you are given the node to delete, but NOT the head pointer! You must copy the next node's value into the current node, and delete the next node instead.

9. Summary

• Nodes: The building blocks. They hold data and a pointer to the next block.
• Head: The anchor of the list. Never reassign the original head pointer during traversal.
• Traversal: Always use a temporary current pointer and a while (current != null) loop.
• Complexity: $O(N)$ Search and Access. $O(1)$ Insertion and Deletion (if pointer is known).