How to add a node in the middle of a linked list using C++

Linked lists are a data structure used for dynamic memory allocation. Unlike arrays, linked lists do not require a fixed size, making them ideal for scenarios where the number of elements is unknown or may change. Each element in a linked list is called a node and contains two parts: the data and a pointer to the next node in the sequence.

Structure of a linked list

Before diving into the implementation, let’s recap some basic concepts of linked lists:

Node structure: Each node in a linked list contains two fields: the data field, which stores the node’s value, and the next field, which is a pointer to the next node in the list.
Head pointer: The linked list is typically represented by a pointer to the first node known as the head. If the list is empty, the head points to null.
Traversal: To perform any operation on a linked list, you often need to traverse it. This involves starting from the head and following the pointers from one node to the next until you reach the desired position or the end of the list.

Now, let’s explore the problem of adding a node to a linked list:

In the image above, there are two linked lists: the first list has four nodes, and the second list has five nodes with a new node inserted in the middle. We will explain later how to add this new node.

Problem statement

Given a linked list with several nodes, the new node should be inserted exactly at the middle point, ensuring the list remains properly connected and ordered.

Algorithm

Create a new node with the given data.
If the linked list is empty, make the new node the head and return.
Initialize two pointers, slow_ptr and fast_ptr, both pointing to the head.
Traverse the list using these pointers:
- Move slow_ptr one step at a time.
- Move fast_ptr two steps at a time.
- Continue until fast_ptr reaches the end or one node before the end.
Insert the new node after the slow_ptr (middle node):
- Set the new node’s next to slow_ptr's next.
- Update slow_ptr's next to point to the new node.

Code example

Let’s look at the complete code below:

#include <iostream>
using namespace std;
class Node {
public:
    int data;
    Node* next;
};
// Function to add a new node in the middle of the linked list
void insertInMiddle(Node** head_ref, int new_data) {
    // Create a new node
    Node* new_node = new Node();
    new_node->data = new_data;
    new_node->next = nullptr;
    // If the linked list is empty, make the new node the head
    if (*head_ref == nullptr) {
        *head_ref = new_node;
        return;
    }
    // Initialize pointers for finding the middle
    Node* slow_ptr = *head_ref;
    Node* fast_ptr = *head_ref;
    // Traverse the list to find the middle
    while (fast_ptr->next != nullptr && fast_ptr->next->next != nullptr) {
        slow_ptr = slow_ptr->next;
        fast_ptr = fast_ptr->next->next;
    }
    // Insert the new node after the middle node
    new_node->next = slow_ptr->next;
    slow_ptr->next = new_node;
}
// Function to print the linked list
void printList(Node* node) {
    while (node != nullptr) {
        cout << node->data << " ";
        node = node->next;
    }
    cout << endl;
}
int main() {
    Node* head = nullptr;
    // Creating a linked list with 4 nodes
    Node* first = new Node();
    Node* second = new Node();
    Node* third = new Node();
    Node* fourth = new Node();
    head = first;
    first->data = 1;
    first->next = second;
    second->data = 2;
    second->next = third;
    third->data = 3;
    third->next = fourth;
    fourth->data = 4;
    fourth->next = nullptr;
    cout << "Original Linked List: ";
    printList(head);
    // Adding a node with value 5 in the middle
    insertInMiddle(&head, 5);
    cout << "Linked List after inserting in the middle: ";
    printList(head);
    return 0;
}

Code explanation

Lines 4–8: The Node class defines the structure of a node. Each node contains an integer data and a pointer next to the next node in the list.
Lines 11–36: This function inserts a new node with the given data new_data into the middle of the linked list.
- Lines 13–15: A new node is created and its data is set.
- Lines 18–21: If the linked list is empty (head_ref is nullptr), the new node becomes the head of the list.
- Lines 28–31: If the list is not empty, two pointers, slow_ptr and fast_ptr, are used to find the middle of the list. slow_ptr moves one step at a time, while fast_ptr moves two steps at a time.
- Lines 34–35: Once the middle is found, the new node is inserted after the middle node.
Lines 39–45: This function prints the elements of the linked list. It iterates through each node, printing its data until the end of the list is reached.

Time complexity

The time complexity of the code to insert a node in the middle of a linked list is O(n).

Space complexity

The function uses a constant amount of extra space for the pointers. So, the space complexity is O(1).

Conclusion

We used two pointers to find the middle of the list. We ensure that the new node is correctly inserted, preserving the list’s order and structure. This technique is both time-efficient, with a complexity of O(n), and space-efficient, using only a constant amount of extra space.

Free Resources