Modify a Linked List by inserting a new node at the front, after a specified node, and at the end. These operations offer flexibility in updating the structure based on specific needs, enabling dynamic adjustments to the Linked List.

## Insertion at the Beginning of the Linked List

Insertion at the Beginning of the Linked List is also known as **Insertion at Head**. In this insertion type, the new node is inserted before the head of the Linked List and this new node that is inserted becomes the head of the Linked List.

Consider a Linked List,

and we have to insert a node at the beginning with value `5`

, thus the updated Linked List will look like this,

Now let’s follow the steps we discussed in the introduction section,

- We have drawn the Linked List before and after the insertion of the node.
- If we compare both the Linked List before and after the insertion we will find out that the
`next`

variable of node`5`

has changed and the head is also changed from node`1`

to node`5`

.

Since we are connecting node`5`

and node `1`

, we have to ensure that we have the address of both nodes. We have the address of node `5`

as we will create this node, but can you guess what is the address of node `1`

? Yes, you guessed it right the address of node `1`

is stored in the variable head.

Steps to Insert a node at the Beginning of the Linked List are,

- Create a new node.
- Initialize the
`data`

of this new node. - Update the
`next`

variable of the new node as`head`

. - Update the
`head`

as the new node.

## Insertion at the End of the Linked List

Insertion at the End of the Linked List is also known as **Insertion at Tail**. In this insertion type, the new node is inserted after the tail of the Linked List and this new node becomes the tail of the Linked List.

Consider a Linked List,

and we have to insert a node at the end with the value `5`

, thus the updated Linked List will look like this,

Let’s follow the common steps we discussed above,

- We have drawn the Linked List before and after the insertion of the node.
- If we compare both the Linked List before and after the insertion we will find out that the
`next`

variable of node`4`

has changed.

Since we are connecting node `4`

and node `5`

we have to ensure that we have the address of both the nodes. We have the address of node `5`

as we will create this node. But we don’t have the address of node `4`

.

For this let’s see how we can identify node `4`

. Node `4`

is the tail of the Linked List (Before Insertion), so the `next`

variable of node `4`

must be NULL. Now we can take a temp variable that will start from the head and will iterate over the Linked List. And when the `next`

variable of temp is NULL we will stop iteration as the temp will be at the tail of Linked List.

Steps to Insert a node at the End of the Linked List are,

- Create a new node and initialize the data of this new node.
- Create another node, temp with the value head.
- Iterate over the Linked List while temp’s
`next`

variable is not equal to NULL. - Now temp is at the tail of the Linked List and we have to just update the
`next`

variable of temp to the new node. - Also make sure to update the
`next`

variable of the new node as NULL.

Since we are iterating the linked list to take the `temp`

node to tail of the linked list, therefore time complexity is `O(N)`

.

However, if we have the address of tail as `temp`

then we can perform steps 4,5,6. Through this the time complexity will be `O(1)`

.

## Adding a Node After a Given Node in the Linked List

This is the third and last type of insertion in the Linked List. We are given a node say `x`

, and we have to insert a new node after `x`

.

Consider a Linked List,

And we have to insert a node with value `5`

, after node `2`

. So the updated Linked List will look like this,

Let’s follow the common steps we discussed above,

- We have drawn the Linked List before and after the insertion of the node.
- If we compare both the Linked List before and after the insertion we will find out that the
`next`

variable of node`2`

and node`5`

has changed.

Since we are connecting node `2`

with node `5`

and node `5`

with node `3`

we need the address of node `2`

, node `5`

, and node `3`

. We have the address of node `5`

as we will create this node. We also have the address of node `2`

as `x`

. But what is the address of node `3`

? The address of node `3`

is stored in the `next`

variable of `x`

. Now we have the required addresses and we can move to the insertion process. Let’s call node `2`

as `x`

and node `3`

as `y`

. So we have to insert node `5`

between `x`

and `y`

.

Steps to Insert a node after a given node `x`

in the Linked List are,

- Create a new node.
- Initialize the data of this new node.
- Create another node,
`y`

with the value of`x`

‘s`next`

variable. - Update the
`next`

variable of`x`

as the new node. - Update the
`next`

variable of the new node as`y`

.

## Example Program

### Insertion at the Beginning of the Linked List

**C++**

```
#include <bits/stdc++.h>
using namespace std;
class Node
{
public:
int data;
Node *next;
};
void print(Node *head){
while(head){
cout<<head->data<<" ";
head = head->next;
}
return;
}
void insertAtBeginning(int val, Node *&head){
if(head==NULL){
//Inserting First Node in the Linked List
head = new Node();
head->data = val;
}else{
//Creating New Node
Node *newNode = new Node();
//Updating data of newNode
newNode->data = val;
//Updating the next variable of newNode as head
newNode->next = head;
//Updating newNode as head
head = newNode;
}
return;
}
int main() {
Node *head = NULL;
insertAtBeginning(4,head);
insertAtBeginning(3,head);
insertAtBeginning(2,head);
insertAtBeginning(1,head);
//Inserting 5 at the Beginning of the Linked List
insertAtBeginning(5,head);
//Printing the Linked List
print(head);
return 0;
}
```

**Java**

```
class LinkedList {
//Head of the Linked List
Node head;
static class Node {
int data;
Node next;
}
public static void print(LinkedList list){
Node temp = list.head;
while(temp != null){
System.out.print(temp.data+" ");
temp = temp.next;
}
return;
}
public void insertAtBeginning(int val){
if(head==null){
//Inserting First Node in the Linked List
head = new Node();
head.data = val;
}else{
//Creating New Node
Node newNode = new Node();
//Updating data of newNode
newNode.data = val;
//Updating the next variable of newNode as head
newNode.next = head;
//Updating newNode as head
head = newNode;
}
return;
}
}
class Main{
public static void main(String args[]) {
LinkedList list = new LinkedList();
list.insertAtBeginning(4);
list.insertAtBeginning(3);
list.insertAtBeginning(2);
list.insertAtBeginning(1);
//Inserting 5 at the beginning of the Linked List
list.insertAtBeginning(5);
//Printing the Linked List
list.print(list);
}
}
```

**Python**

```
class Node:
# Constructor
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def print(self):
temp = self.head
while temp is not None:
print(temp.data,end = " ")
temp = temp.next
def insertAtBeginning(self, val):
if self.head == None:
# Inserting First Node in the Linked List
self.head = Node(val)
else:
# Creating New Node
newNode = Node(val)
# Updating the next variable of newNode as head
newNode.next = self.head
# Updating newNode as head
self.head = newNode
list = LinkedList()
list.insertAtBeginning(4)
list.insertAtBeginning(3)
list.insertAtBeginning(2)
list.insertAtBeginning(1)
# Inserting 5 at the beginning of the Linked List
list.insertAtBeginning(5)
# Printing the Linked List
list.print()
```

**Output:**

`5 1 2 3 4 `

### Insertion at the End of the Linked List

**C++**

```
#include <bits/stdc++.h>
using namespace std;
class Node
{
public:
int data;
Node *next;
};
void print(Node *head){
while(head){
cout<<head->data<<" ";
head = head->next;
}
return;
}
void insertAtEnd(int val, Node *&head){
if(head==NULL){
//Inserting First Node in the Linked List
head = new Node();
head->data = val;
}else{
//Creating New Node
Node *newNode = new Node();
//Updating data of newNode
newNode->data = val;
//Creating a temp node to iterate over Linked List so that head is not changed
Node *temp = head;
//Iterating till the `next` variable of temp is not equal to NULL
while(temp->next!=NULL){
temp = temp->next;
}
//Temp is at tail of the Linked List
temp->next = newNode;
//Updating `next` variable of newNode as NULL
newNode->next = NULL;
}
return;
}
int main() {
Node *head = NULL;
insertAtEnd(1,head);
insertAtEnd(2,head);
insertAtEnd(3,head);
insertAtEnd(4,head);
//Inserting 5 at the End of the Linked List
insertAtEnd(5,head);
//Printing the Linked List
print(head);
return 0;
}
```

**Java**

```
class LinkedList {
//Head of the Linked List
Node head;
static class Node {
int data;
Node next;
}
public static void print(LinkedList list){
Node temp = list.head;
while(temp != null){
System.out.print(temp.data+" ");
temp = temp.next;
}
return;
}
public void insertAtEnd(int val){
if(head==null){
//Inserting First Node in the Linked List
head = new Node();
head.data = val;
}else{
//Creating New Node
Node newNode = new Node();
//Updating data of newNode
newNode.data = val;
//Creating a temp node to iterate over Linked List so that head is not changed
Node temp = head;
//Iterating till the `next` variable of temp is not equal to NULL
while(temp.next!=null){
temp = temp.next;
}
//Temp is at tail of the Linked List
temp.next = newNode;
//Updating `next` variable of newNode as NULL
newNode.next = null;
}
return;
}
}
public class Main{
public static void main(String args[]) {
LinkedList list = new LinkedList();
list.insertAtEnd(1);
list.insertAtEnd(2);
list.insertAtEnd(3);
list.insertAtEnd(4);
//Inserting 5 at the End of the Linked List
list.insertAtEnd(5);
//Printing the Linked List
list.print(list);
}
}
```

**Python**

```
class Node:
# Constructor
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def print(self):
temp = self.head
while temp is not None:
print(temp.data,end = " ")
temp = temp.next
def insertAtEnd(self, val):
if self.head == None:
# Inserting First Node in the Linked List
self.head = Node(val)
else:
# Creating New Node
newNode = Node(val)
# Updating the `next` variable of newNode as head
newNode.next = self.head
# Creating a temp node to iterate over Linked List so that head is not changed
temp = self.head
# Iterating till the `next` variable of temp is not equal to None
while temp.next is not None:
temp = temp.next
# Temp is at tail of the Linked List
temp.next = newNode;
# Updating `next` variable of newNode as None
newNode.next = None;
list = LinkedList()
list.insertAtEnd(1)
list.insertAtEnd(2)
list.insertAtEnd(3)
list.insertAtEnd(4)
# Inserting 5 at the End of the Linked List
list.insertAtEnd(5)
# Printing the Linked List
list.print()
```

**Output:**

`1 2 3 4 5 `

### Adding a Node after a Given Node in the Linked List

Here x is the position of a node. Consider the linked list,

`1->2->3->4->NULL`

1st node is `1`

. So if x=1, the node `1`

will be returned by `generateX`

function.

Similarly, if x = 3, the node `3`

will be returned.**C++**

```
#include <bits/stdc++.h>
using namespace std;
class Node
{
public:
int data;
Node *next;
};
void print(Node *head){
while(head){
cout<<head->data<<" ";
head = head->next;
}
return;
}
void insertAtEnd(int val, Node *&head){
if(head==NULL){
//Inserting First Node in the Linked List
head = new Node();
head->data = val;
}else{
//Creating New Node
Node *newNode = new Node();
//Updating data of newNode
newNode->data = val;
//Creating a temp node to iterate over Linked List
Node *temp = head;
//Iterating till the `next` variable of temp is not equal to NULL
while(temp->next!=NULL){
temp = temp->next;
}
//Temp is at tail of the Linked List
temp->next = newNode;
//Updating `next` variable of newNode as NULL
newNode->next = NULL;
}
return;
}
//Function to return the address of x'th Node
Node *generateX(Node *head,int pos){
//If the Linked List is empty return NULL
if(head==NULL) return head;
int cnt = 1;
Node *x = NULL;
while(head!=NULL){
if(cnt==pos){
//If the count is equal to pos store the address of head and break the iteration
x = head;
break;
}
cnt++;
head = head->next;
}
return x;
}
int main() {
Node *head = NULL;
insertAtEnd(1,head);
insertAtEnd(2,head);
insertAtEnd(3,head);
insertAtEnd(4,head);
//Creating New Node
Node *newNode = new Node();
//Updating data of newNode
newNode->data = 5;
//Generating the Address of x'th Node
Node *x = generateX(head,2);
//Storing the Address of y'th Node
Node *y = x->next;
//Updating the `next` variable of x as newNode
x->next = newNode;
//Updating the `next` variable of newNode as y
newNode->next = y;
//Printing the Linked List
print(head);
return 0;
}
```

**Java**

```
class Node {
int data;
Node next;
}
class LinkedList {
//Head of the Linked List
Node head;
public static void print(LinkedList list){
Node temp = list.head;
while(temp != null){
System.out.print(temp.data+" ");
temp = temp.next;
}
return;
}
public void insertAtEnd(int val){
if(head==null){
//Inserting First Node in the Linked List
head = new Node();
head.data = val;
}else{
//Creating New Node
Node newNode = new Node();
//Updating data of newNode
newNode.data = val;
//Creating a temp node to iterate over Linked List
Node temp = head;
//Iterating till the `next` variable of temp is not equal to NULL
while(temp.next!=null){
temp = temp.next;
}
//Temp is at the tail of the Linked List
temp.next = newNode;
//Updating the` next` variable of newNode as NULL
newNode.next = null;
}
return;
}
public Node generateX(int pos){
//If the Linked List is empty return NULL
if(head==null) return head;
int cnt = 1;
Node x = null, temp = head;
while(temp!=null){
if(cnt==pos){
//If the count is equal to pos store the address of the head and break the iteration
x = temp;
break;
}
cnt++;
temp = temp.next;
}
return x;
}
}
class Main{
public static void main(String args[]) {
LinkedList list = new LinkedList();
list.insertAtEnd(1);
list.insertAtEnd(2);
list.insertAtEnd(3);
list.insertAtEnd(4);
//Creating New Node
Node newNode = new Node();
//Updating data of newNode
newNode.data = 5;
//Generating the Address of x'th Node
Node x = list.generateX(2);
//Storing the Address of the Node
Node y = x.next;
//Updating the `next` variable of x as newNode
x.next = newNode;
//Updating the `next` variable of newNode as y
newNode.next = y;
//Printing the Linked List
list.print(list);
}
}
```

**Python**

```
class Node:
# Constructor
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def print(self):
temp = self.head
while temp is not None:
print(temp.data,end = " ")
temp = temp.next
def insertAtEnd(self, val):
if self.head == None:
# Inserting First Node in the Linked List
self.head = Node(val)
else:
# Creating New Node
newNode = Node(val)
# Updating the `next` variable of newNode as head
newNode.next = self.head
# Creating a temp node to iterate over Linked List
temp = self.head
# Iterating till the `next` variable of temp is not equal to None
while temp.next is not None:
temp = temp.next
# Temp is at tail of the Linked List
temp.next = newNode;
# Updating `next` variable of newNode as None
newNode.next = None;
def generateX(self,pos):
# If the Linked List is empty return None
if self.head == None:
return self.head
cnt = 1
x = None
temp = self.head
while temp is not None:
if cnt == pos:
# If the count is equal to pos store the address of head and break the iteration
x = temp
break
cnt+=1
temp = temp.next
return x
list = LinkedList()
list.insertAtEnd(1)
list.insertAtEnd(2)
list.insertAtEnd(3)
list.insertAtEnd(4)
# Creating New Node
newNode = Node(5);
# Generating the Address of x'th Node
x = list.generateX(2);
# Storing the Address of y'th Node
y = x.next;
# Updating the `next` variable of x as newNode
x.next = newNode;
# Updating the `next` variable of newNode as y
newNode.next = y;
# Printing the Linked List
list.print()
```

**Output:**

`1 2 5 3 4 `

:::

:::section{.main}

## Using Constructor Call

In the above codes, you can observe that we are creating the node and then we are initializing the data to the node as,

```
//Creating New Node
Node *newNode = new Node();
//Updating data of newNode
newNode->data = val;
```

But we can eliminate this using Constructor Call. We can declare a constructor in the `Node`

class and this constructor will initialize the `data`

and the `next`

variable of the node. Let’s see how we can initialize `data`

and `next`

variable to a node using a constructor call.

```
class Node
{
public:
int data;
Node *next;
//Constructor
Node(int val,Node *address = NULL){
data = val;
next = address;
}
};
```

Now, all we have to do is pass the val and address to the `Node()`

method and the constructor will initialize them to the node. Also, the default value of the address is `NULL`

, so if we don’t pass the address then the `next`

variable of the node will be set as `NULL`

.

### Node With Value and NULL as Address of Next Node

`Node *newNode = new Node(5);`

Now the `newNode`

has `data`

as `5`

and `next`

as `NULL`

. The time complexity of above operation is `O(1)`

.

### Node With Value and Node x as Address of Next Node

```
Node *x = new Node(6);
Node *newNode = new Node(5,x);
```

Now the `newNode`

has `data`

as `5`

and the `next`

variable of `newNode`

is x. The time complexity of above operations is `O(1)`

.

## Conclusion

- Linked List is a
`linear data structure`

that stores elements in non-contiguous memory locations. - Insertion in Linked List can be divided into three cases, Insert Node in Linked List at the Beginning, Insert Node in Linked List at the End, and Insert Node in Linked List after a given Node.
- There are some common steps that are important when we insert a node in Linked List, these are
- Draw the Linked List before and after insertion of the node.
- Identify the nodes whose
`next`

variable is changed and also identify the variables that have been changed in the insertion process. - Update the
`next`

variable of the required nodes and also update the required variables.