Data Structure (Linked List Insertion)

Insertion is basically a method to add a new node into our existing linked list. We can add new node either at the beginning of our linked list or at the middle or at the end.

Let us move on to the process. We want to add a new node at the end of our linked list.

First we create a new node. Then we find the null point of our existing linked list.

Current node is not null. So, we move on.

We keep moving on.

Now that we have found the null point, we change it to our new node location and create a new link.

Pseudo code is given below for better understanding.

given head

new node = Node(New Data)
current node = head
while current node is not null {
     current node = current node.next node
}
current node = new node

Now we have a new node linked to our existing list.

For a Doubly linked list, instead of only updating the next node location, we update the previous node location of our new node as well.

First we create a new node.

Then we find the null point and update the next node location.

Then we update the previous node location of our new node.

Let us look at the pseudo code.

given head

new node = Node(New Data)
current node = head
while current node.next node is not null {
    current node = current node.next node
}
current node.next node = new node
new node.previous node = current node

As simple as that. We have now new node linked to our doubly linked list.

Moving on, adding a new node in the beginning is pretty much the same. Here we just don't have to run a loop. Moving on to the process.

First we create a new node.

Then we link the new node with the head of our existing list.

Most importantly we change our head location from node01 to the new node. Because now, we will have access of our list with the new node's location. Pseudo code is given.

given head

new node = Node(New Data)
new node.next node = head
head = new node

In Doubly linked list make we make link with both the previous node and next node.

First we create our new node.

Then we make link with the head.

Then we make link with the new node as previous node.

At last we change head as our new node.

given head

new node = Node(New Data)
new node.next node = head
head.previous node = new node
head = new node

Next, we are going to add a new node in the middle of our list.

Here, suppose we want to add the new node in the 3rd place so that new node's position will be k = 3. So, first we find the kth node.

Then we have to link our new node with the previous node as well as the next node.

When we make link with the previous node we change the previous node's next node location to our new node. If we do that we will lose the location which was storing in the previous node before.

So, make sure to link the new node with the next node first and then make link with the previous node.

Now we make link with the previous node.

In this way we can add a new node in any kth position of our existing list.

given head
given k

initiate i = 1
current node = head
for i is not k-1 increment i {
    current node = current node.next node
}
new node = Node(New Data)
new node.next node = current node.next node
current node.next node = new node

Now we are left with doubly linked list. Same thing just have to make link with both side.

First we make link same as singly linked list.

Then we make backward link.

Pseudo Code is given below.

given head
given k

initiate i = 1
current node = head
for i is not k-1 increment i {
    current node = current node.next node
}
new node = Node(New Data)
new node.next node = current node.next node
current node.next node = new node
new node.previous node = current node
current node = new node.next node
current node.previous node = new node

I hope this is understandable. Congratulations. We have completed the Insertion methods of a linked list. Feel free to add a comment anytime with issues.