Speed:

Singly Linked List

Search: O(n)Insert: O(1) at headDelete: O(1) at headUnidirectional

🔗Singly Linked List Operations

Each node contains data and one pointer: next (forward direction). Simpler structure than doubly linked list with less memory overhead.

Insert at beginning or specific position. Only need to update 2 pointers. Simpler than doubly linked list but requires traversal for middle insertion.

Traverse from head only to find elements. Cannot search backwards. Suitable for sequential access patterns.

Remove nodes by finding predecessor and updating next pointer. Must traverse to find predecessor node.

🔧Setup - Node Structure

A Singly Linked List is the simplest form of linked list where each node contains data and a single pointer to the next node. This unidirectional structure allows traversal only in the forward direction. Each node has two components: the data value and a next pointer to the following node. The list maintains a reference only to the head node, which serves as the entry point. This minimal structure results in lower memory overheadcompared to doubly linked lists, making it ideal for scenarios where backward traversal is not required and memory efficiency is important.

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

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

➕Insert - Add Operation

Insertion in a singly linked list is simpler than in doubly linked lists due to fewer pointer updates. There are two main scenarios: inserting at the beginning and inserting at a specific position. Beginning insertion is O(1) as it only requires updating the new node's next pointer to the current head and updating the head reference. For middle insertion, we must traverse to the position before the insertion point, then update onlytwo pointers: the new node's next and the predecessor's next. This simplicity comes at the cost of requiring traversal for non-head insertions, making it less efficient than doubly linked lists for frequent middle insertions.

insertAtPosition(data, position) {
    if (position < 0 || position > this.size) return false;
    
    const newNode = new Node(data);
    
    if (position === 0) {
        // Insert at beginning
        newNode.next = this.head;
        this.head = newNode;
    } else {
        // Traverse to position - 1
        let current = this.head;
        for (let i = 0; i < position - 1; i++) {
            current = current.next;
        }
        
        newNode.next = current.next;
        current.next = newNode;
    }
    
    this.size++;
    return true;
}

// Insert at beginning
prepend(data) {
    const newNode = new Node(data);
    newNode.next = this.head;
    this.head = newNode;
    this.size++;
}

// Insert at end
append(data) {
    const newNode = new Node(data);
    
    if (!this.head) {
        this.head = newNode;
    } else {
        let current = this.head;
        while (current.next) {
            current = current.next;
        }
        current.next = newNode;
    }
    
    this.size++;
}

🔍Search - Find Operation

Search operation in a singly linked list follows a straightforward linear traversal from the head node. Unlike doubly linked lists, there's no option for backward traversal, so all searches must start from the beginning. The algorithm compares each node's data with the target value, continuing until either the value is found or the end of the list is reached. While this results in O(n) time complexity in the worst case, the unidirectional nature makes it suitable for applications with primarily sequential access patterns. For sorted lists, early termination can be implemented to improve average-case performance.

search(data) {
    let current = this.head;
    let position = 0;
    
    while (current !== null) {
        if (current.data === data) {
            return { found: true, position: position, node: current };
        }
        current = current.next;
        position++;
    }
    
    return { found: false, position: -1, node: null };
}

// Search with early termination for sorted lists
searchSorted(data) {
    let current = this.head;
    let position = 0;
    
    while (current !== null) {
        if (current.data === data) {
            return { found: true, position: position, node: current };
        }
        
        // Early termination if list is sorted
        if (current.data > data) {
            break;
        }
        
        current = current.next;
        position++;
    }
    
    return { found: false, position: -1, node: null };
}

🗑️Delete - Remove Operation

Deletion in a singly linked list requires careful handling due to the inability to access the previous node directly. Two main cases exist: deleting the first node (simply update the head pointer) and deleting any other node (find the predecessor and update its next pointer). The challenge lies in finding the predecessor node, which requires traversal from the head. Once the predecessor is found, deletion is accomplished by updating its next pointer to skip the node being deleted. While this makes deletionO(n) for arbitrary positions, head deletion remains O(1). This limitation is addressed in doubly linked lists with backward pointers.

deleteAtPosition(position) {
    if (position < 0 || position >= this.size || this.head === null) {
        return false;
    }
    
    if (position === 0) {
        // Delete first node
        this.head = this.head.next;
    } else {
        // Traverse to position - 1
        let current = this.head;
        for (let i = 0; i < position - 1; i++) {
            current = current.next;
        }
        
        // Skip the node to delete
        current.next = current.next.next;
    }
    
    this.size--;
    return true;
}

deleteByValue(data) {
    if (!this.head) return false;
    
    // If head contains the data
    if (this.head.data === data) {
        this.head = this.head.next;
        this.size--;
        return true;
    }
    
    let current = this.head;
    while (current.next && current.next.data !== data) {
        current = current.next;
    }
    
    if (current.next) {
        current.next = current.next.next;
        this.size--;
        return true;
    }
    
    return false;
}