Back to Module 1

Linked Lists II: Advanced Operations

Master advanced linked list operations through hands-on implementation and practical exercises.

Advanced Linked List Operations

In this guided project, you'll implement advanced linked list operations with a focus on general insertion techniques. You'll learn how to handle edge cases, maintain list integrity, and optimize your implementations.

Key Concepts

  • General insertion at any position
  • Edge case handling
  • Reference management

Learning Objectives

  • Implement general insertion operation
  • Handle boundary conditions
  • Optimize insertion operations

General Insertion Implementation

Implementation Steps

  1. 1

    Create New Node

    Initialize a new node with the given value

    Node newNode = new Node(value);
  2. 2

    Handle Edge Cases

    Check for empty list and invalid positions

    if (position < 0 || position > size) {
    return false;
}
if (head == null && position == 0) {
    head = newNode;
    size++;
    return true;
}
  3. 3

    Traverse to Position

    Navigate to the insertion point

    Node current = head;
for (int i = 0; i < position - 1; i++) {
    current = current.next;
}
  4. 4

    Perform Insertion

    Update references to insert the new node

    newNode.next = current.next;
current.next = newNode;
size++;

Critical Considerations for Linked List Operations

When implementing linked list operations, keep these important points in mind:

Order of Operations

The sequence of operations is crucial, especially when modifying references:

  • Always set new nodes' next pointers before changing existing pointers
  • When deleting nodes, ensure you don't lose access to parts of the list
// CORRECT order for insertion
newNode.next = current.next;  // Set new node's reference first
current.next = newNode;       // Then update the current node's reference

// INCORRECT order would lose the rest of the list
// current.next = newNode;       // DON'T do this first
// newNode.next = current.next;  // This would point to itself!

Edge Cases That Must Be Handled

  • Empty List: Always check if head is null
  • Single Element List: Special handling when size is 1
  • Invalid Positions: Validate index bounds (0 to size inclusive for insertion, 0 to size-1 for deletion)
  • Head/Tail Operations: Treat beginning/end operations as special cases

Visualizing Pointer Changes

Imagine insertion at position 2 in a list:

// Before: head -> A -> B -> C -> null
//                       0    1    2
// Insert X at position 2
// After:  head -> A -> B -> X -> C -> null
//                       0    1    2    3

Steps to achieve this:

  1. Validate position (2 is valid if size >= 2)
  2. Create new node X
  3. Traverse to B (position-1)
  4. Store B's next (C) in a temporary reference or directly use in assignment
  5. Set X's next to point to C
  6. Set B's next to point to X

Common Implementation Mistakes

Off-by-One Errors

When traversing to nodes for insertion or deletion, be careful with zero-based indexing:

// To insert at position 2, we need to stop at position 1
Node current = head;
// Loop stops when i equals position-1
for (int i = 0; i < position - 1; i++) {
    current = current.next;
}
// Now current is at position 1, and we insert after it

Null Pointer Exceptions

Always check for null before dereferencing:

// INCORRECT - might cause NullPointerException
current.next = newNode;

// CORRECT - check first
if (current != null) {
    current.next = newNode;
} else {
    // Handle the error case
}

Memory Leaks

In Java, detached nodes are automatically garbage-collected. However, in other languages, you might need to explicitly free memory.

To ensure clean removal in any language:

// When removing node B in: A -> B -> C
// First update references
A.next = C;
// Then ensure B has no lingering references (important in some languages)
B.next = null; // In Java, this isn't strictly necessary but is good practice

Practice Exercises

Exercise 1: General Insert

Implement a function to insert a node at any valid position in a linked list. 

public boolean insert(int value, int position) {
    // Your implementation here
}

Implementation Hints

  1. Create a new node with the given value
  2. Validate that position is between 0 and the list's size
  3. Handle special cases:
    • Empty list (head == null)
    • Insertion at beginning (position == 0)
    • Insertion at end (position == size)
  4. For insertion in the middle:
    • Traverse to the node at position-1
    • Set new node's next to current node's next
    • Set current node's next to the new node
  5. Increment the size counter
  6. Return true to indicate successful insertion

Test Cases to Consider

  • Insert into empty list
  • Insert at beginning of non-empty list
  • Insert in middle of list
  • Insert at end of list
  • Insert with invalid position (negative or > size)

Exercise 2: Sorted Insert

Implement a function to insert a node into a sorted linked list while maintaining the order. 

public void insertSorted(int value) {
    // Your implementation here
}

Implementation Hints

  1. Create a new node with the given value
  2. Handle special cases:
    • Empty list (head == null)
    • Insert before head if value < head.value
  3. Traverse the list to find the correct position:
    • Stop when current.next is null or current.next.value > value
  4. Insert the new node between current and current.next
  5. Increment the size counter

Example Walkthrough

// Given sorted list: 10 -> 20 -> 30 -> 40
// Insert value: 25

// After insertion: 10 -> 20 -> 25 -> 30 -> 40
//                           ^-- insert here

// Implementation logic:
// 1. Start at head (10)
// 2. Check: 10 < 25, move to next (20)
// 3. Check: 20 < 25, move to next (30)
// 4. Check: 30 > 25, found position! Insert between 20 and 30

Exercise 3: Remove Duplicates

Implement a function to remove duplicate values from a linked list. 

public void removeDuplicates() {
    // Your implementation here
}

Implementation Hints

  1. If the list is empty or has only one node, return immediately
  2. Use two pointers: one to iterate through the list, and another to check for duplicates ahead
  3. For each node:
    • Use the second pointer to check all nodes ahead
    • If a duplicate is found, remove it by updating references
    • Don't forget to update the size counter for each removal

Example Walkthrough

// Given list: 1 -> 2 -> 2 -> 3 -> 1 -> 4
// After removing duplicates: 1 -> 2 -> 3 -> 4

// Implementation logic:
// 1. Start with first node (1)
//    a. Check all nodes ahead for duplicates of 1
//    b. Find duplicate at position 4, remove it
// 2. Move to second node (2)
//    a. Check all nodes ahead for duplicates of 2
//    b. Find duplicate at position 2, remove it
// 3. Continue with remaining nodes...

Optimization (Optional Challenge)

For a more efficient solution, use a hash set to track seen values:

public void removeDuplicatesWithHashSet() {
    if (head == null) return;
    
    HashSet<Integer> seenValues = new HashSet<>();
    Node current = head;
    Node previous = null;
    
    while (current != null) {
        // If value has been seen before, remove node
        if (seenValues.contains(current.value)) {
            previous.next = current.next;
            size--;
        } else {
            // Add to set and move previous pointer
            seenValues.add(current.value);
            previous = current;
        }
        current = current.next;
    }
}

Bonus Exercise: Reverse a Linked List

Implement a function to reverse a linked list in-place. 

public void reverse() {
    // Your implementation here
}

Implementation Hints

  1. Use three pointers: previous, current, and next
  2. Initialize previous to null and current to head
  3. Iterate through the list:
    • Save the next node before changing current.next
    • Reverse the current node's pointer (current.next = previous)
    • Move previous and current pointers one step forward
  4. Update head to point to the new first node (previously the last)

Example Walkthrough

// Given list: 1 -> 2 -> 3 -> 4 -> null
// After reversal: 4 -> 3 -> 2 -> 1 -> null

// Implementation logic:
// Initial state:
// prev=null, current=1, next=null
// Step 1:
// next = current.next = 2
// current.next = prev = null, so 1 -> null
// prev = current = 1
// current = next = 2
// State: null <- 1, 2 -> 3 -> 4
// Step 2:
// next = current.next = 3
// current.next = prev = 1, so 2 -> 1
// prev = current = 2
// current = next = 3
// State: null <- 1 <- 2, 3 -> 4
// Continue until current is null
// Final step: update head = prev (which is 4)
Ready to master advanced linked list operations?