Guided Project: Linked Lists II

Insertion at Position

Example Implementation

                        class Node {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}

class LinkedList {
    constructor() {
        this.head = null;
        this.length = 0;
    }
    
    // Add a node to the end of the list
    append(value) {
        const newNode = new Node(value);
        this.length++;
        
        if (!this.head) {
            this.head = newNode;
            return;
        }
        
        let current = this.head;
        while (current.next) {
            current = current.next;
        }
        current.next = newNode;
    }
    
    // Insert a node at a specific position
    insertAtPosition(position, value) {
        // If position is out of range
        if (position < 0 || position > this.length) {
            return false;
        }
        
        const newNode = new Node(value);
        
        // Insert at the beginning
        if (position === 0) {
            newNode.next = this.head;
            this.head = newNode;
            this.length++;
            return true;
        }
        
        // Insert at any other position
        let current = this.head;
        let previous = null;
        let index = 0;
        
        while (index < position) {
            previous = current;
            current = current.next;
            index++;
        }
        
        newNode.next = current;
        previous.next = newNode;
        this.length++;
        
        return true;
    }
}
                    

Example Usage:

const list = new LinkedList();
list.append(1);
list.append(3);
list.append(4);

// Insert 2 at position 1 (between 1 and 3)
list.insertAtPosition(1, 2);

// Output: 1 -> 2 -> 3 -> 4

Deletion at Position

Example Implementation

                        class LinkedList {
    // ... previous methods
    
    // Remove a node at a specific position
    removeAtPosition(position) {
        // If the list is empty or position is out of range
        if (!this.head || position < 0 || position >= this.length) {
            return null;
        }
        
        let removedNode;
        
        // Remove the first node
        if (position === 0) {
            removedNode = this.head;
            this.head = this.head.next;
            this.length--;
            return removedNode.value;
        }
        
        // Remove node at any other position
        let current = this.head;
        let previous = null;
        let index = 0;
        
        while (index < position) {
            previous = current;
            current = current.next;
            index++;
        }
        
        removedNode = current;
        previous.next = current.next;
        this.length--;
        
        return removedNode.value;
    }
}
                    

Example Usage:

const list = new LinkedList();
list.append(1);
list.append(2);
list.append(3);
list.append(4);

// Remove node at position 2 (value 3)
const removed = list.removeAtPosition(2);
console.log(removed); // 3

// Output: 1 -> 2 -> 4

Practice Challenges

Now that you've learned how to implement insertion and deletion at specific positions in a linked list, try these practice challenges:

Challenge 1: Reverse a Linked List

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

                        class LinkedList {
    // ... previous methods
    
    reverse() {
        // Your code here
    }
}
                    

Challenge 2: Find the Middle Node

Implement a method to find the middle node of a linked list using only one pass.

                        class LinkedList {
    // ... previous methods
    
    findMiddle() {
        // Your code here
    }
}
                    

Additional Resources

If you want more practice with linked lists, check out these LeetCode problems: