Linked List

Basic Structure

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

class LinkedList {
    constructor() {
        this.head = null;
        this.size = 0;
    }
}

Core Methods

1. Insert at Beginning

insertAtBeginning(data) {
    const newNode = new Node(data);
    newNode.next = this.head;
    this.head = newNode;
    this.size++;
}

Time Complexity: O(1)

2. Insert at End

insertAtEnd(data) {
    const newNode = new Node(data);
    
    if (!this.head) {
        this.head = newNode;
        this.size++;
        return;
    }
    
    let current = this.head;
    while (current.next) {
        current = current.next;
    }
    current.next = newNode;
    this.size++;
}

Time Complexity: O(n)

3. Delete from Beginning

deleteFromBeginning() {
    if (!this.head) {
        return null;
    }
    
    const removedData = this.head.data;
    this.head = this.head.next;
    this.size--;
    return removedData;
}

Time Complexity: O(1)

4. Delete from End

deleteFromEnd() {
    if (!this.head) {
        return null;
    }
    
    if (!this.head.next) {
        const removedData = this.head.data;
        this.head = null;
        this.size--;
        return removedData;
    }
    
    let current = this.head;
    while (current.next.next) {
        current = current.next;
    }
    
    const removedData = current.next.data;
    current.next = null;
    this.size--;
    return removedData;
}

Time Complexity: O(n)

5. Search for Element

search(data) {
    let current = this.head;
    let position = 0;
    
    while (current) {
        if (current.data === data) {
            return position;
        }
        current = current.next;
        position++;
    }
    
    return -1;
}

Time Complexity: O(n)

Advanced Operations

1. Reverse List

reverse() {
    let prev = null;
    let current = this.head;
    
    while (current) {
        const next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }
    
    this.head = prev;
}

Time Complexity: O(n)

2. Detect Cycle

hasCycle() {
    if (!this.head) return false;
    
    let slow = this.head;
    let fast = this.head;
    
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        
        if (slow === fast) {
            return true;
        }
    }
    
    return false;
}

Time Complexity: O(n)

3. Find Middle Node

findMiddle() {
    if (!this.head) return null;
    
    let slow = this.head;
    let fast = this.head;
    
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    
    return slow.data;
}

Time Complexity: O(n)

4. Remove Duplicates (Sorted List)

removeDuplicates() {
    let current = this.head;
    
    while (current && current.next) {
        if (current.data === current.next.data) {
            current.next = current.next.next;
            this.size--;
        } else {
            current = current.next;
        }
    }
}

Time Complexity: O(n)

Utility Methods

1. Print List

print() {
    let current = this.head;
    const elements = [];
    
    while (current) {
        elements.push(current.data);
        current = current.next;
    }
    
    return elements.join(' -> ');
}

2. Get Size

getSize() {
    return this.size;
}

3. Is Empty

isEmpty() {
    return this.size === 0;
}

Common Interview Questions

1. Merge Two Sorted Lists

mergeSortedLists(list1, list2) {
    const dummy = new Node(0);
    let current = dummy;
    
    while (list1 && list2) {
        if (list1.data <= list2.data) {
            current.next = list1;
            list1 = list1.next;
        } else {
            current.next = list2;
            list2 = list2.next;
        }
        current = current.next;
    }
    
    current.next = list1 || list2;
    return dummy.next;
}

2. Find Nth Node from End

findNthFromEnd(n) {
    if (!this.head) return null;
    
    let fast = this.head;
    let slow = this.head;
    
    // Move fast n nodes ahead
    for (let i = 0; i < n; i++) {
        if (!fast) return null;
        fast = fast.next;
    }
    
    // Move both pointers until fast reaches end
    while (fast) {
        slow = slow.next;
        fast = fast.next;
    }
    
    return slow.data;
}

Time Complexity Summary

Operation	Time Complexity
Insert at Beginning	O(1)
Insert at End	O(n)
Delete from Beginning	O(1)
Delete from End	O(n)
Search	O(n)
Reverse	O(n)
Detect Cycle	O(n)
Find Middle	O(n)
Remove Duplicates	O(n)

Usage Example

const list = new LinkedList();

// Insert elements
list.insertAtBeginning(3);
list.insertAtEnd(7);
list.insertAtBeginning(1);

// Print list: 1 -> 3 -> 7
console.log(list.print());

// Find element
console.log(list.search(3)); // Output: 1

// Reverse list
list.reverse();
// Print list: 7 -> 3 -> 1
console.log(list.print());