Data Structure (Linked List Insertion)
Published: 2023-03-30 07:50:18

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.

![End Insertion SLL01](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/1v7j5jw8czv2pr8z141r.png)

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


![End Insertion SLL02](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/evdfpazzu87r97dhrcmp.png)

We keep moving on.


![End Insertion SLL03](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/czvbko7f0n26x9onk1t4.png)

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


![End Insertion SLL04](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/12j1hdyou7q32q4x5mtg.png)

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.


![End Insertion DLL01](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/cfo6yhfgi063jgk5b66h.png)

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

![End Insertion DLL01](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ey78osakjockz40hjc1r.png)

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

![End Insertion DLL01](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/40rbrn0oy36exxdvc3a7.png)

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. 

![Head Insertion SLL01](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/b4k75u700ju4rm814eqb.png)

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

![Head Insertion SLL02](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/0iehby9rwjf0k35wzp7c.png)

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.

![Head Insertion DLL01](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/wyp159352eptzs3ywgo5.png)

Then we make link with the head.

![Head Insertion DLL02](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/n8lv4hb14pwk6fqplt4y.png)

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

![Head Insertion DLL03](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/cot3h6elf2kmbll9itef.png)

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.

![Middle Insertion SLL01](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/n71na3sfe9tewux6thit.png)

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. 

![Middle Insertion SLL02](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/5ikzh9sbf2t7nzhwy3k1.png)

Now we make link with the previous node.

![Middle Insertion SLL03](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/oyld9oq9958a3xxf2y6z.png)

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. 

![Middle Insertion DLL01](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/u3oh2fzyjlucq42sx207.png)

![Middle Insertion DLL02](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/sml3jv19q0xjoryyv2ss.png)

Then we make backward link.

![Middle Insertion DLL03](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/szu7ki0278ht0d9a7aza.png)

![Middle Insertion DLL04](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/507b1f9o1ulkm90e1pn1.png)

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.