The linked list data structure in C++ is a type of linear data structure used to store data but stored in a continuous manner or at contiguous memory locations like arrays. But in a linked list data is stored at different memory locations which are linked with each other through pointers.

Structure of Linked List

A Linked list consists of a bunch of nodes with two parts, one is the data part, and the other one is the linking part.

• Data Part
• Linking part (Pointer to next node)

 As it is stated earlier, in a linked list in C++ data is not stored in contiguous memory locations so it needs to be linked with each other. So that is done by pointers to store the memory address of the next node, this type of linked list is known as singly linked list.

The structure of a singly linked list is given below:

• As in the above illustration, we can see that the basic structure of a singly linked list is composed of three nodes. The first node represents a head node or node n1, the second is Node n2, third one is Node n3.
• We have a head pointer (head ptr) that stores the address of the head pointer (Which will be null at the beginning of the linked list when it is empty).
• Node n1 has a memory address of “#101” which is stored in the head ptr pointer, one data part which is stored  “10” and a pointer that carries the address “#706” to the next node(Node n2).
• Node n2 has a data part that stores an integer value of “45” and the address “#004” to the next Node (Node n3).
• Node n3 has data part “57” and the address to the next Node is NULL which indicates the ending of the linked list.
• The node which points to NULL is also known as the Tail of the linked list Node n3 in our case.

By taking that picture in mind we will perform various operations on Linked List.

Insertion functions in Linked List data structure in C++

We can insert data in a linked list as much as we want because it has no storage limitations like an array. We know that when we add data, there will be a node created. In which one part will be the data part, and another is the linking part. So, by keeping that idea in mind there are the following operations that we will discuss step by step.

• insert at head
• Insert a node at a specific position in a linked list
• Insert at Tail

Insert at head in linked list in C++

When we discuss the insert at head in the linked list then we have two possibilities, The first is that when linked list is empty, there is no node before. Then we create a new node and point it as head its next part will point to the Null as it will be the first node. The second possibility is that when there is an existing list, we have to put data at its head.

In this case, we will create a new node and set its value, and this will be pointing to the previous head 2 in our case. Then we change the head pointer, and the head pointer will now be pointing to our new node 1 As shown in the figure below.

void LinkList::InsertAtHead(int x) {
node* temp = new node();
temp->data = x;
temp->next = head;
head = temp;
}

Insert a node at a specific position in a linked list in C++

Insertion at a specific position in the linked list is done by checking that location first if it’s available then we will create a temp node that will move at that position and then create a new node and set its data, the next pointer of the new node will point the next of temp variable and next pointer of temp will points to the new node.

void LinkList::InsertInBetween(int x, int position) {
    if (position <= 0) {
        cout << "Invalid position. Insertion failed." << endl;
        return;
    }

    node* newNode = new node();
    newNode->data = x;
    newNode->next = nullptr;

    if (position == 1) {
        newNode->next = head;
        head = newNode;
        return;
    }

    node* current = head;
    int currentPosition = 1;
    while (current != nullptr && currentPosition < position - 1) {
        current = current->next;
        currentPosition++;
    }

    if (current == nullptr) {
        cout << "Invalid position. Insertion failed." << endl;
    }
    else {
        newNode->next = current->next;
        current->next = newNode;
    }
}

Insert at the tail of linked list in C++

For insert at tail, we will check if the linked list is empty then we create a new node and indicate it as the head.

But if the list is present and we have to put a node at its end, then we will create a temp node move that node to the last node and create a new node to be inserted at tail. When the temp reaches the tail, its next pointer will be pointing to Null. We must change it to the new node and now our temp will point to the new node and the next pointer of the new node will pointing the Null as a result our new node will become the tail.

void LinkList::InsertAtTail(int x) {
    node* newNode = new node();
    newNode->data = x;
    newNode->next = nullptr;

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

    node* current = head;
    while (current->next != nullptr) {
        current = current->next;
    }
    current->next = newNode;
} 

Conclusion

A linked list in C++ is a linear data structure in which data is stored in a non-contagious manner. The linked list is composed of two parts, one is the data part, and the other is the pointer part. There can be many nodes in a linked list. The first node is called the head, and we have access to it through its memory address.

The first node in the linked list is called the head and the last node is called the tail which points to the Null and indicates the ending of our linked list. We cannot access the linked list directly like arrays, so it is hard to print or traverse.