Home/Data Structures/Linked Lists

Linked Lists

🎯 Explain Like I'm 5...

Imagine you have a train with toy cars! Each train car holds one toy and knows which car comes next because they're holding hands!

🚂 Linked Lists - Train Cars Holding Hands:

  • • Car 1: Has a teddy bear 🧸 and holds hands with Car 2
  • • Car 2: Has a ball ⚽ and holds hands with Car 3
  • • Car 3: Has a robot 🤖 and doesn't hold any more hands (it's the last one!)

To find the ball, start at Car 1, then follow the hand-holding to Car 2! 🚂💨

📦 Different from Array Boxes:

Arrays are like boxes on a shelf - all lined up and numbered. Linked lists are like train cars - each one just knows the next one!

  • • Array: Can jump to any box instantly (Box 5!)
  • • Linked List: Must walk car by car to find what you want
  • • But adding new train cars is super easy - just hold hands! 🤝

🚀 Why Are They Useful?

  • • Adding or removing items is super fast - just change who's holding hands!
  • • You can make them as long as you want - add more train cars anytime!
  • • Perfect when you don't know how many items you'll have!

🔧 Basic Operations

Creating Node Class (Train Car)

Node.java
java
1
2
3
4
5
6
7
8
9
10
11
// A Node is like a train car - it holds data and knows the next car!
public class Node {
    int data;        // The toy in this car
    Node next;       // Holding hands with the next car
    // Constructor - creating a new train car with a toy
    public Node(int data) {
        this.data = data;
        this.next = null;  // Not holding hands with anyone yet
    }
}

Creating a Linked List

LinkedList.java
java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class LinkedList {
    Node head;  // The first train car (front of the train)
    // Constructor - start with an empty train
    public LinkedList() {
        this.head = null;
    }
    // Check if train is empty
    public boolean isEmpty() {
        return head == null;
    }
    public static void main(String[] args) {
        // Create an empty linked list
        LinkedList train = new LinkedList();
        System.out.println("Train is empty: " + train.isEmpty());  // true
        // Add first car manually
        train.head = new Node(10);
        System.out.println("Train is empty: " + train.isEmpty());  // false
        System.out.println("First car has: " + train.head.data);   // 10
    }
}

Inserting Nodes (Adding Train Cars)

LinkedListInsert.java
java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
public class LinkedList {
    Node head;
    // Insert at the beginning (add new car at front of train)
    public void insertAtBeginning(int data) {
        Node newNode = new Node(data);  // Create new car
        newNode.next = head;            // New car holds hands with old first car
        head = newNode;                 // New car becomes the front!
    }
    // Insert at the end (add new car at back of train)
    public void insertAtEnd(int data) {
        Node newNode = new Node(data);
        // If train is empty, new car is the first car
        if (head == null) {
            head = newNode;
            return;
        }
        // Walk to the last car
        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        // Last car holds hands with new car
        current.next = newNode;
    }
    // Insert at specific position (add car in the middle somewhere)
    public void insertAtPosition(int data, int position) {
        if (position == 0) {
            insertAtBeginning(data);
            return;
        }
        Node newNode = new Node(data);
        Node current = head;
        // Walk to one car before where we want to insert
        for (int i = 0; i < position - 1 && current != null; i++) {
            current = current.next;
        }
        if (current == null) {
            System.out.println("Position out of bounds!");
            return;
        }
        // Insert new car in between
        newNode.next = current.next;  // New car holds hands with next car
        current.next = newNode;       // Previous car holds hands with new car
    }
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        // Build train: 10 -> 20 -> 30
        list.insertAtEnd(10);
        list.insertAtEnd(20);
        list.insertAtEnd(30);
        // Add car at front: 5 -> 10 -> 20 -> 30
        list.insertAtBeginning(5);
        // Insert in middle: 5 -> 10 -> 15 -> 20 -> 30
        list.insertAtPosition(15, 2);
    }
}

Deleting Nodes (Removing Train Cars)

LinkedListDelete.java
java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
public class LinkedList {
    Node head;
    // Delete from beginning (remove first car)
    public void deleteFromBeginning() {
        if (head == null) {
            System.out.println("Train is already empty!");
            return;
        }
        // First car lets go, second car becomes first
        head = head.next;
    }
    // Delete from end (remove last car)
    public void deleteFromEnd() {
        if (head == null) {
            System.out.println("Train is already empty!");
            return;
        }
        // If only one car, remove it
        if (head.next == null) {
            head = null;
            return;
        }
        // Walk to second-to-last car
        Node current = head;
        while (current.next.next != null) {
            current = current.next;
        }
        // Second-to-last car lets go of last car
        current.next = null;
    }
    // Delete specific value (remove car with specific toy)
    public void deleteValue(int value) {
        if (head == null) {
            return;
        }
        // If first car has the value
        if (head.data == value) {
            head = head.next;
            return;
        }
        // Find the car before the one we want to delete
        Node current = head;
        while (current.next != null && current.next.data != value) {
            current = current.next;
        }
        // If found, skip over it (hand-holding changes)
        if (current.next != null) {
            current.next = current.next.next;
        }
    }
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        // Build train: 10 -> 20 -> 30 -> 40
        list.insertAtEnd(10);
        list.insertAtEnd(20);
        list.insertAtEnd(30);
        list.insertAtEnd(40);
        // Remove first car: 20 -> 30 -> 40
        list.deleteFromBeginning();
        // Remove last car: 20 -> 30
        list.deleteFromEnd();
        // Remove car with 20: 30
        list.deleteValue(20);
    }
}

Traversing the List (Walking Through Train Cars)

LinkedListTraverse.java
java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
public class LinkedList {
    Node head;
    // Display all elements (walk through entire train)
    public void display() {
        if (head == null) {
            System.out.println("Train is empty!");
            return;
        }
        Node current = head;
        System.out.print("Train: ");
        // Walk through each car until we reach the end
        while (current != null) {
            System.out.print(current.data);
            if (current.next != null) {
                System.out.print(" -> ");
            }
            current = current.next;
        }
        System.out.println(" -> null");
    }
    // Search for a value
    public boolean search(int value) {
        Node current = head;
        while (current != null) {
            if (current.data == value) {
                return true;  // Found it!
            }
            current = current.next;
        }
        return false;  // Not found
    }
    // Get size of list (count train cars)
    public int size() {
        int count = 0;
        Node current = head;
        while (current != null) {
            count++;
            current = current.next;
        }
        return count;
    }
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        // Build train: 10 -> 20 -> 30 -> 40
        list.insertAtEnd(10);
        list.insertAtEnd(20);
        list.insertAtEnd(30);
        list.insertAtEnd(40);
        // Display the train
        list.display();  // Train: 10 -> 20 -> 30 -> 40 -> null
        // Search for values
        System.out.println("Has 20? " + list.search(20));  // true
        System.out.println("Has 50? " + list.search(50));  // false
        // Get size
        System.out.println("Number of cars: " + list.size());  // 4
    }
}

💡 Common Problems & Solutions

Problem 1: Reverse a Linked List

Flip the entire train around - make all cars hold hands with the car behind them instead!

💡 How it works (The 3-Pointer Technique):

The Challenge: Make each node point backwards instead of forwards

Step-by-Step Process:

1. Start with 3 pointers: prev=null, current=head, next=null

2. For each node:

• Save the next node (so we don't lose the rest of the list)

• Point current node backwards to prev

• Move prev and current one step forward

3. When done: prev becomes the new head

Visual Example:

Original: 1 → 2 → 3 → 4 → 5 → null

Step 1: null ← 1 2 → 3 → 4 → 5 → null
Step 2: null ← 1 ← 2 3 → 4 → 5 → null
Step 3: null ← 1 ← 2 ← 3 4 → 5 → null
Step 4: null ← 1 ← 2 ← 3 ← 4 5 → null
Step 5: null ← 1 ← 2 ← 3 ← 4 ← 5

Result: 5 → 4 → 3 → 2 → 1 → null

⏱️ Time Complexity: O(n) - visit each node once

💾 Space Complexity: O(1) - only use 3 pointers

ReverseLinkedList.java
java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public class ReverseLinkedList {
    // Reverse the entire linked list
    public static Node reverse(Node head) {
        Node prev = null;
        Node current = head;
        Node next = null;
        // Walk through and flip all hand-holdings!
        while (current != null) {
            next = current.next;        // Remember next car
            current.next = prev;        // Current car holds hands backwards
            prev = current;             // Move prev forward
            current = next;             // Move current forward
        }
        return prev;  // Prev is now the new head (front car)
    }
    // Helper method to print list
    public static void printList(Node head) {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }
    public static void main(String[] args) {
        // Create list: 1 -> 2 -> 3 -> 4 -> 5
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(4);
        head.next.next.next.next = new Node(5);
        System.out.println("Original:");
        printList(head);  // 1 -> 2 -> 3 -> 4 -> 5 -> null
        head = reverse(head);
        System.out.println("Reversed:");
        printList(head);  // 5 -> 4 -> 3 -> 2 -> 1 -> null
    }
}

Problem 2: Detect Cycle in Linked List

Check if the train forms a circle (does a car hold hands with one we already passed?)

💡 How it works (Floyd's Cycle Detection - Tortoise & Hare):

The Problem: A node might point back to an earlier node, creating an infinite loop!

The Clever Solution:

1. Use two pointers:

• Slow pointer (🐢 tortoise): moves 1 step at a time

• Fast pointer (🐰 hare): moves 2 steps at a time

2. If there's NO cycle: Fast pointer reaches null (end of list)

3. If there IS a cycle: Fast pointer will eventually catch up to slow pointer (they meet!)

Why does this work?

Think of a circular race track:

• If slow runs at 1 mph and fast runs at 2 mph

• Fast is gaining 1 mph on slow

• Eventually fast will lap slow and they'll meet!

Visual Example:

List with cycle: 1 → 2 → 3 → 4 → 5
↑ ↓
└─────────┘

Step 1: slow@1, fast@1
Step 2: slow@2, fast@3
Step 3: slow@3, fast@5
Step 4: slow@4, fast@4 ← They meet! Cycle detected! ✅

⏱️ Time Complexity: O(n) - will meet in at most n steps

💾 Space Complexity: O(1) - only use 2 pointers

DetectCycle.java
java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public class DetectCycle {
    // Detect if there's a cycle using Floyd's Algorithm (Tortoise and Hare)
    public static boolean hasCycle(Node head) {
        if (head == null || head.next == null) {
            return false;
        }
        Node slow = head;      // Slow walker (moves 1 step)
        Node fast = head;      // Fast runner (moves 2 steps)
        // Fast runner tries to catch slow walker
        while (fast != null && fast.next != null) {
            slow = slow.next;           // Move 1 step
            fast = fast.next.next;      // Move 2 steps
            // If they meet, there's a cycle!
            if (slow == fast) {
                return true;
            }
        }
        // Fast runner reached the end, no cycle
        return false;
    }
    public static void main(String[] args) {
        // Create list: 1 -> 2 -> 3 -> 4 -> 5
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(4);
        head.next.next.next.next = new Node(5);
        System.out.println("Has cycle? " + hasCycle(head));  // false
        // Create a cycle: 5 -> 3 (train forms a circle!)
        head.next.next.next.next.next = head.next.next;
        System.out.println("Has cycle? " + hasCycle(head));  // true
    }
}

Problem 3: Find Middle of Linked List

Find the middle train car using the slow and fast pointer technique!

💡 How it works (Slow & Fast Pointer Trick):

The Challenge: Find middle without knowing the length of the list first

The Smart Solution:

1. Use two pointers starting at head:

• Slow pointer: moves 1 step at a time

• Fast pointer: moves 2 steps at a time

2. When fast reaches the end:

• Slow will be exactly at the middle!

Why does this work?

• Fast moves twice as fast as slow

• When fast travels 100%, slow traveled 50%

• 50% = middle of the list! 🎯

Visual Example (Odd length):

List: 1 → 2 → 3 → 4 → 5 → null

Start: slow@1, fast@1
Step 1: slow@2, fast@3
Step 2: slow@3, fast@5
Step 3: slow@3, fast@null (reached end!)

Middle = 3 ✅

Visual Example (Even length):

List: 1 → 2 → 3 → 4 → null

Start: slow@1, fast@1
Step 1: slow@2, fast@3
Step 2: slow@3, fast@null

Middle = 3 (second middle) ✅

⏱️ Time Complexity: O(n) - traverse list once

💾 Space Complexity: O(1) - only use 2 pointers

FindMiddle.java
java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public class FindMiddle {
    // Find middle node using slow and fast pointers
    public static Node findMiddle(Node head) {
        if (head == null) {
            return null;
        }
        Node slow = head;      // Slow walker (1 step at a time)
        Node fast = head;      // Fast runner (2 steps at a time)
        // When fast reaches end, slow will be at middle!
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;  // This is the middle car!
    }
    public static void main(String[] args) {
        // Create list: 1 -> 2 -> 3 -> 4 -> 5
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(4);
        head.next.next.next.next = new Node(5);
        Node middle = findMiddle(head);
        System.out.println("Middle element: " + middle.data);  // 3
        // Create list with even number: 1 -> 2 -> 3 -> 4
        Node head2 = new Node(1);
        head2.next = new Node(2);
        head2.next.next = new Node(3);
        head2.next.next.next = new Node(4);
        Node middle2 = findMiddle(head2);
        System.out.println("Middle element: " + middle2.data);  // 3
    }
}

Problem 4: Merge Two Sorted Linked Lists

Combine two sorted trains into one big sorted train!

💡 How it works (Merge Like Shuffling Cards):

The Challenge: Combine two sorted lists into one sorted list

The Solution (Compare & Connect):

1. Create a dummy node: Makes connecting easier (we'll skip it at the end)

2. Compare the front of both lists:

• Take the smaller one

• Connect it to our merged list

• Move that list's pointer forward

3. Repeat until one list is empty

4. Attach the remaining nodes from whichever list still has items

Think of it like: Merging two sorted piles of cards by always picking the smaller card

Visual Example:

List 1: 1 → 3 → 5 → null
List 2: 2 → 4 → 6 → null

Step 1: Compare 1 vs 2 → pick 1
Result: dummy → 1

Step 2: Compare 3 vs 2 → pick 2
Result: dummy → 1 → 2

Step 3: Compare 3 vs 4 → pick 3
Result: dummy → 1 → 2 → 3

Step 4: Compare 5 vs 4 → pick 4
Result: dummy → 1 → 2 → 3 → 4

Step 5: Compare 5 vs 6 → pick 5
Result: dummy → 1 → 2 → 3 → 4 → 5

Step 6: List1 empty, attach rest of List2
Result: dummy → 1 → 2 → 3 → 4 → 5 → 6 → null

Final (skip dummy): 1 → 2 → 3 → 4 → 5 → 6 → null ✅

⏱️ Time Complexity: O(n + m) - visit each node once

💾 Space Complexity: O(1) - only reconnect existing nodes

MergeSortedLists.java
java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
public class MergeSortedLists {
    // Merge two sorted linked lists into one sorted list
    public static Node mergeTwoLists(Node l1, Node l2) {
        // Create a dummy node to make merging easier
        Node dummy = new Node(0);
        Node current = dummy;
        // Compare and merge while both lists have cars
        while (l1 != null && l2 != null) {
            if (l1.data <= l2.data) {
                current.next = l1;  // Take car from first train
                l1 = l1.next;
            } else {
                current.next = l2;  // Take car from second train
                l2 = l2.next;
            }
            current = current.next;
        }
        // Attach remaining cars from whichever train still has them
        if (l1 != null) {
            current.next = l1;
        }
        if (l2 != null) {
            current.next = l2;
        }
        return dummy.next;  // Return merged train (skip dummy)
    }
    // Helper method to print list
    public static void printList(Node head) {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }
    public static void main(String[] args) {
        // Create first sorted list: 1 -> 3 -> 5
        Node l1 = new Node(1);
        l1.next = new Node(3);
        l1.next.next = new Node(5);
        // Create second sorted list: 2 -> 4 -> 6
        Node l2 = new Node(2);
        l2.next = new Node(4);
        l2.next.next = new Node(6);
        System.out.println("List 1:");
        printList(l1);
        System.out.println("List 2:");
        printList(l2);
        Node merged = mergeTwoLists(l1, l2);
        System.out.println("Merged:");
        printList(merged);  // 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null
    }
}

🔑 Key Points to Remember

  • 1️⃣Insertion/Deletion at beginning is O(1) - super fast!
  • 2️⃣Accessing elements is O(n) - must walk through from start
  • 3️⃣Each node has data and a reference (pointer) to next node
  • 4️⃣Head is the first node, tail is the last (points to null)
  • 5️⃣Dynamic size - can grow or shrink easily

💪 Practice Problems

  • • Remove duplicates from linked list
  • • Find nth node from end of list
  • • Palindrome linked list
  • • Intersection of two linked lists
  • • Remove nth node from end of list