Mastering Linked Lists in C++: Inserting Nodes at Various Positions

Linked lists are a fundamental data structure in computer science, allowing for efficient insertion and deletion of elements. In this post, we will explore how to insert nodes into a linked list in C++ using three different methods: inserting at the front, at the end, and after a specific node.

Understanding Linked Lists

Before we dive into the insertion methods, it's essential to understand the structure of a linked list. A linked list consists of nodes, where each node contains two parts: a value and a pointer to the next node. The first node is referred to as the head of the list.

Basic Linked List Implementation

Here is a simple implementation of a linked list in C++:

class Node {
public:
    int value;
    Node* next;
};

Node* head = nullptr;

In this code, we define a Node class with an integer value and a pointer to the next node. The head pointer points to the first node in the list.

Inserting a Node at the Front

To insert a node at the front of the linked list, we will create a function called insertAtFront. This function will take the address of the head pointer and the value to be inserted as parameters.

Steps to Insert at the Front

1. Create a new node and allocate memory for it.
2. Set the new node's next pointer to the current head.
3. Update the head pointer to point to the new node.

Implementation

Here is how the insertAtFront function looks in C++:

void insertAtFront(Node** head, int newValue) {
    Node* newNode = new Node();
    newNode->value = newValue;
    newNode->next = *head;
    *head = newNode;
}

Testing the Function

To test this function, you can call it as follows:

insertAtFront(&head, -1);

After running this, the linked list will have -1 as the new head, followed by the previous elements.

Inserting a Node at the End

Next, we will implement a function to insert a node at the end of the linked list called insertAtEnd.

Steps to Insert at the End

1. Create a new node and allocate memory for it.
2. Check if the list is empty. If it is, set the head to the new node.
3. If the list is not empty, traverse to the last node.
4. Set the last node's next pointer to the new node.

Implementation

Here is the insertAtEnd function:

void insertAtEnd(Node** head, int newValue) {
    Node* newNode = new Node();
    newNode->value = newValue;
    newNode->next = nullptr;

    if (*head == nullptr) {
        *head = newNode;
        return;
    }

    Node* last = *head;
    while (last->next != nullptr) {
        last = last->next;
    }
    last->next = newNode;
}

Testing the Function

You can test this function by calling:

insertAtEnd(&head, 4);

This will add 4 to the end of the linked list.

Inserting a Node After a Specific Node

Finally, we will create a function called insertAfter to insert a node after a specific node in the linked list.

Steps to Insert After a Specific Node

1. Check if the previous node is null.
2. Create a new node and allocate memory for it.
3. Set the new node's next pointer to the previous node's next pointer.
4. Update the previous node's next pointer to point to the new node.

Implementation

Here is how the insertAfter function looks:

void insertAfter(Node* previous, int newValue) {
    if (previous == nullptr) {
        std::cout << "Previous node cannot be null";
        return;
    }

    Node* newNode = new Node();
    newNode->value = newValue;
    newNode->next = previous->next;
    previous->next = newNode;
}

Testing the Function

To test this function, you can call:

insertAfter(head, -1);

This will insert -1 after the head node.

Conclusion

In this blog post, we covered how to insert nodes into a linked list in C++ using three different methods: at the front, at the end, and after a specific node. Understanding these operations is crucial for working with linked lists effectively. If you have any questions or need further clarification, feel free to leave a comment below.