Insertion in Linked List | DSA in C++ - Software Development PDF Download

Introduction

Linked lists are fundamental data structures in computer science that provide dynamic memory allocation and efficient insertion and deletion operations. In this article, we will explore the concept of insertion in a linked list using C++. We will cover various insertion scenarios, provide code examples, and explain the code step by step. Additionally, we will conclude with some sample problems and their solutions to reinforce the understanding of linked list insertion.

Overview of Linked Lists

Before diving into insertion operations, let's briefly understand the basics of linked lists. A linked list is a collection of nodes, where each node contains data and a pointer/reference to the next node. The first node is called the head, and the last node points to NULL, indicating the end of the list.

Insertion at the Beginning of a Linked List

Inserting a node at the beginning of a linked list involves creating a new node and updating the head pointer to point to the new node. Here's an example code snippet that demonstrates this operation:

#include <iostream>

struct Node {

    int data;

    Node* next;

};

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

    Node* newNode = new Node();

    newNode->data = newData;

    newNode->next = *head;

    *head = newNode;

}

int main() {

    Node* head = nullptr;

    insertAtBeginning(&head, 10);

    insertAtBeginning(&head, 20);

    insertAtBeginning(&head, 30);

    // Print the linked list

    Node* current = head;

    while (current != nullptr) {

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

        current = current->next;

    }

    return 0;

}

Output:

30 20 10

Explanation:

• We define a 'Node' struct to represent each node in the linked list.
• The 'insertAtBeginning' function takes a double pointer to the head node and the data for the new node.
• Inside the function, we allocate memory for the new node, assign the data, and update the next pointer to the current head.
• Finally, we update the head pointer to point to the new node.
• In the 'main' function, we insert three nodes at the beginning using 'insertAtBeginning'.
• The linked list is then printed by traversing through each node and displaying its data.

Insertion at the End of a Linked List

To insert a node at the end of a linked list, we need to find the last node and update its 'next' pointer to the new node. Here's an example code snippet:

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

    Node* newNode = new Node();

    newNode->data = newData;

    newNode->next = nullptr;

    if (*head == nullptr) {

        *head = newNode;

        return;

    }

    Node* lastNode = *head;

    while (lastNode->next != nullptr) {

        lastNode = lastNode->next;

    }

    lastNode->next = newNode;

}

// Usage example in main function similar to previous code snippet

Output:

10 20 30

Explanation:

• The 'insertAtEnd' function takes a double pointer to the head node and the data for the new node.
• It starts by allocating memory for the new node and assigning the data and NULL to its next pointer.
• If the linked list is empty (head is NULL), we update the head to point to the new node and return.
• Otherwise, we iterate through the list to find the last node.
• Once the last node is found, we update its next pointer to the new node.

Insertion at a Specific Position in a Linked List

To insert a node at a specific position in a linked list, we need to traverse to that position and update the necessary pointers. Here's an example code snippet:

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

    Node* newNode = new Node();

    newNode->data = newData;

    newNode->next = nullptr;

    if (position == 0) {

        newNode->next = *head;

        *head = newNode;

        return;

    }

    Node* prevNode = nullptr;

    Node* currentNode = *head;

    int currentPosition = 0;

    while (currentPosition < position && currentNode != nullptr) {

        prevNode = currentNode;

        currentNode = currentNode->next;

        currentPosition++;

    }

    if (currentPosition != position) {

        std::cout << "Invalid position!\n";

        return;

    }

    prevNode->next = newNode;

    newNode->next = currentNode;

}

// Usage example in main function similar to previous code snippets

Output:

10 20 30 40 50

Explanation:

• The 'insertAtPosition' function takes a double pointer to the head node, the data for the new node, and the position at which to insert.
• It starts by allocating memory for the new node and assigning the data and NULL to its next pointer.
• If the position is 0, we insert the node at the beginning by updating the new node's next pointer and the head pointer.
• Otherwise, we iterate through the list until we reach the desired position or the end of the list.
• If the desired position is not found, we display an error message and return.
• Otherwise, we update the previous node's next pointer to the new node and the new node's next pointer to the current node at that position.

Sample Problems and Solutions

Problem 1: Given a linked list, insert a node with data 25 after the node with data 20.

Node* findNode(Node* head, int searchData) {

    Node* current = head;

    while (current != nullptr) {

        if (current->data == searchData) {

            return current;

        }

        current = current->next;

    }

    return nullptr;

}

void insertAfterNode(Node* prevNode, int newData) {

    if (prevNode == nullptr) {

        std::cout << "Previous node is NULL!\n";

        return;

    }

    Node* newNode = new Node();

    newNode->data = newData;

    newNode->next = prevNode->next;

    prevNode->next = newNode;

}

// Usage example in main function

Node* node20 = findNode(head, 20);

if (node20 == nullptr) {

    std::cout << "Node with data 20 not found!\n";

} else {

    insertAfterNode(node20, 25);

}

Problem 2: Given a sorted linked list, insert a node in its correct position while keeping the list sorted.

void insertInSorted(Node** head, int newData) {

    Node* newNode = new Node();

    newNode->data = newData;

    newNode->next = nullptr;

    if (*head == nullptr || newData < (*head)->data){

        newNode->next = *head;

        *head = newNode;

        return;

    }

    Node* current = *head;

    while (current->next != nullptr && current->next->data < newData) {

        current = current->next;

    }

    newNode->next = current->next;

    current->next = newNode;

}

// Usage example in main function

insertInSorted(&head, 35);

Conclusion

In this article, we explored the concept of insertion in a linked list using C++. We covered insertion at the beginning, end, and a specific position in a linked list. Each insertion scenario was explained with code examples and step-by-step explanations. Additionally, we provided sample problems and their solutions to further enhance understanding. Linked lists are powerful data structures with various applications, and mastering their insertion operations is crucial for building efficient algorithms.