LEARN WITH ME

Singly Linked List

Overview

A singly linked list is a linear data structure where each element (called a node) contains two parts: the data and a pointer (or reference) to the next node in the sequence. The list starts with a special node called the head, which points to the first element in the list. If the list is empty, the head points to null or None.

Key Operations on a Singly Linked List

• Insertion:
• At the Beginning: To insert a new node at the beginning, create a new node and set its next pointer to the current head. Then update the head to point to this new node.
  Time Complexity: O(1).
• At the Middle: To insert a new node in the middle, traverse the list to the node after which you want to insert the new node. Update the next pointer of the new node to the next pointer of the current node, then set the next pointer of the current node to the new node.
  Time Complexity: O(n).
• At the End: To insert a new node at the end, traverse to the end of the list, then set the next pointer of the last node to the new node.
  Time Complexity: O(n).

Insertion Operation


• Deletion:
• At the Beginning: To delete the first node, set the head to the next node of the current head.
  Time Complexity: O(1).
• At the Middle: To delete a node in the middle, find the node before the one to be deleted and set its next pointer to the next node of the node to be deleted.
  Time Complexity: O(n).
• At the End: To delete the last node, traverse to the second last node and set its next pointer to null.
  Time Complexity: O(n).

Deletion Operation


• Traversing: To traverse the list, start from the head and follow the next pointers until you reach the end of the list.
  Time Complexity: O(n).

Example Code

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

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

    // Insert at the beginning
    insertAtBeginning(data) {
        const newNode = new Node(data);
        newNode.next = this.head;
        this.head = newNode;
    }

    // Insert at the end
    insertAtEnd(data) {
        const newNode = new Node(data);
        if (!this.head) {
            this.head = newNode;
            return;
        }
        let current = this.head;
        while (current.next) {
            current = current.next;
        }
        current.next = newNode;
    }

    // Insert at the middle
    insertAtMiddle(data, position) {
        const newNode = new Node(data);
        if (position === 0) {
            this.insertAtBeginning(data);
            return;
        }
        let current = this.head;
        let previous = null;
        let index = 0;
        while (index < position && current) {
            previous = current;
            current = current.next;
            index++;
        }
        newNode.next = current;
        previous.next = newNode;
    }

    // Delete at the beginning
    deleteAtBeginning() {
        if (!this.head) return;
        this.head = this.head.next;
    }

    // Delete at the end
    deleteAtEnd() {
        if (!this.head) return;
        if (!this.head.next) {
            this.head = null;
            return;
        }
        let current = this.head;
        while (current.next.next) {
            current = current.next;
        }
        current.next = null;
    }

    // Delete at the middle
    deleteAtMiddle(position) {
        if (position === 0) {
            this.deleteAtBeginning();
            return;
        }
        let current = this.head;
        let previous = null;
        let index = 0;
        while (index < position && current) {
            previous = current;
            current = current.next;
            index++;
        }
        if (current) {
            previous.next = current.next;
        }
    }

    // Display the list
    display() {
        let current = this.head;
        while (current) {
            console.log(current.data);
            current = current.next;
        }
    }
}

// Example usage
const list = new SinglyLinkedList();
list.insertAtBeginning(1);
list.insertAtEnd(2);
list.insertAtMiddle(3, 1);
list.display();
list.deleteAtBeginning();
list.deleteAtEnd();
list.deleteAtMiddle(1);
list.display();