by Jasleen Chhabra | Updated on 24 August 2024

A singly linked list is a fundamental data structure in computer science, where each node points to the next node in the sequence, and the last node points to null, indicating the end of the list. This structure is highly flexible and efficient for dynamic memory allocation, making it essential for various applications.

Key Operations on Singly Linked Lists

1. Insertion
2. Deletion
3. Traversal
4. Searching

---

Insertion: Adding a New Node to the Linked List

Insertion in a singly linked list involves creating a new node and adding it to the list. This can be done at the beginning, end, or any position within the list. Here’s how it works:

At the Beginning

Algorithm:

1. Create a new node.
2. Point the new node’s next reference to the current head.
3. Update the head to the new node.

C++ Implementation:

struct Node {

    int data;

    Node* next;

};

 

void insertAtBeginning(Node*& head, int newData) {

    Node* newNode = new Node();

    newNode->data = newData;

    newNode->next = head;

    head = newNode;

}

At the End

Algorithm:

1. Create a new node.
2. Traverse to the last node.
3. Point the last node’s next reference to the new node.

C++ Implementation:

void insertAtEnd(Node*& head, int newData) {

    Node* newNode = new Node();

    newNode->data = newData;

    newNode->next = nullptr;

 

    if (head == nullptr) {

        head = newNode;

        return;

    }

 

    Node* last = head;

    while (last->next != nullptr) {

        last = last->next;

    }

    last->next = newNode;

}

At a Specific Position

Algorithm:

1. Create a new node.
2. Traverse to the node just before the desired position.
3. Point the new node’s next reference to the next node.
4. Update the previous node’s next reference to the new node.

C++ Implementation:

void insertAtPosition(Node*& head, int position, int newData) {

    if (position == 0) {

        insertAtBeginning(head, newData);

        return;

    }

 

    Node* newNode = new Node();

    newNode->data = newData;

 

    Node* current = head;

    for (int i = 0; current != nullptr && i < position - 1; i++) {

        current = current->next;

    }

 

    if (current == nullptr) {

        return;

    }

 

    newNode->next = current->next;

    current->next = newNode;

}

---

Deletion: Removing an Existing Node from the Linked List

Deletion involves removing a node and adjusting the pointers accordingly. This can be done for the first node, a specific node, or the last node.

First Node

Algorithm:

1. Update the head to the next node.
2. Delete the original first node.

C++ Implementation:

void deleteFirstNode(Node*& head) {

    if (head == nullptr) return;

 

    Node* temp = head;

    head = head->next;

    delete temp;

}

Specific Node

Algorithm:

1. Traverse to the node just before the target node.
2. Update the previous node’s next reference to skip the target node.
3. Delete the target node.

C++ Implementation:

void deleteNode(Node*& head, int key) {

    Node* temp = head;

    Node* prev = nullptr;

 

    if (temp != nullptr && temp->data == key) {

        head = temp->next;

        delete temp;

        return;

    }

 

    while (temp != nullptr && temp->data != key) {

        prev = temp;

        temp = temp->next;

    }

 

    if (temp == nullptr) return;

 

    prev->next = temp->next;

    delete temp;

}

Last Node

Algorithm:

1. Traverse to the second-to-last node.
2. Update its next reference to null.
3. Delete the original last node.

C++ Implementation:

void deleteLastNode(Node*& head) {

    if (head == nullptr) return;

    if (head->next == nullptr) {

        delete head;

        head = nullptr;

        return;

    }

 

    Node* secondLast = head;

    while (secondLast->next->next != nullptr) {

        secondLast = secondLast->next;

    }

 

    delete secondLast->next;

    secondLast->next = nullptr;

}

---

Traversal: Accessing Each Node in the Linked List

Traversal involves accessing each node in a sequential manner.

Algorithm:

1. Start from the head.
2. Access each node and move to the next until the end of the list.

C++ Implementation:

void traverseList(Node* head) {

    Node* current = head;

    while (current != nullptr) {

        std::cout << current->data << " ";

        current = current->next;

    }

    std::cout << std::endl;

}

---

Searching: Finding a Node with a Specific Value

Searching involves finding a node that contains a specific value.

Algorithm:

1. Start from the head.
2. Compare each node’s data with the target value.
3. If found, return the node; otherwise, continue until the end.

C++ Implementation:

Node* search(Node* head, int key) {

    Node* current = head;

    while (current != nullptr) {

        if (current->data == key) {

            return current;

        }

        current = current->next;

    }

    return nullptr;

}

This blog content provides a comprehensive overview of singly linked lists, including key operations such as insertion, deletion, traversal, and searching, along with their algorithms and C++ implementations.

---