# insertion in linked list

Given the head node of a linked list, the task is to insert a new node in this already created linked list.

You can insert/add elements to either the beginning, middle or end of the linked list.

**insert a node at beginning:**

*Allocate memory for new node

*Store data

*Change next of new node to point to head

*Change head to point to recently created new node

for example, if the given linked list is **17->25->40->45**** **and we add item 12 at the front ,then the linked list becomes **12->17->25->40->45**

Below is the 4 step process of adding a new node at the front of Linked List declared at the beginning of this post:

**c++:**

void push(struct Node** head_ref, int new_data) { /* 1. allocate node */ Node* new_node = new Node; /* 2. store data */ new_node->data = new_data; /* 3. Make next of new node as head */ new_node->next = (*head_ref); /* 4. move the head to point to the new node */ (*head_ref) = new_node; }

**Java:**

public void push(int new_data) { /* 1 & 2: Allocate the Node & Put in the data*/ Node new_node = new Node(new_data); /* 3. Make next of new Node as head */ new_node.next = head; /* 4. Move the head to point to new Node */ head = new_node; }

The **time complexity** of inserting a node at start of the List is O(1).

### Inserting a Node at the End:

**c++:**

void append(struct Node** head_ref, int new_data) { /* 1. allocate node */ Node* new_node = new Node; struct Node *cursor= *head_ref; /* used in step 5*/ /* 2. put in the data */ new_node->data = new_data; /* 3. This new node is going to be the last node, so make next of it as NULL*/ new_node->next = NULL; /* 4. If the Linked List is empty, then make the new node as head */ if (*head_ref == NULL) { *head_ref = new_node; return; } /* 5. Else traverse till the last node */ while (cursor->next != NULL) cursor = cursor->next; /* 6. Change the next of cursor node */ cursor->next = new_node; return; }

**java:**

```
public void append(int new_data)
{
/* 1. Allocate the Node &
2. Put in the data
3. Set next as null */
Node new_node = new Node(new_data);
/* 4. If the Linked List is empty, then make the
new node as head */
if (head == null)
{
head = new Node(new_data);
return;
}
/* 4. This new node is going to be the last node, so
make next of it as null */
new_node.next = null;
/* 5. Else traverse till the last node */
Node last = head;
while (last.next != null)
last = last.next;
/* 6. Change the next of last node */
last.next = new_node;
return;
}
```

**time complexity**of this operation is O(N) where N is the number of nodes in the Linked List as one have to traverse the complete list in order to find the last node.

**inserting a node after a given node:**

```
void insertAfter(struct Node* prev_node, int new_data)
{
/* 1. check if the given prev_node is NULL */
if (prev_node == NULL)
{
printf("the given previous node cannot be NULL");
return;
}
/* 2. allocate new node */
Node* new_node = new Node;
/* 3. put in the data */
new_node->data = new_data;
/* 4. Make next of new node as next of prev_node */
new_node->next = prev_node->next;
/* 5. move the next of prev_node as new_node */
prev_node->next = new_node;
}
```

**Java:**

```
public void insertAfter(Node prev_node, int new_data)
{
/* 1. Check if the given Node is null */
if (prev_node == null)
{
System.out.println("The given previous node cannot be null");
return;
}
/* 2. Allocate the Node &
3. Put in the data*/
Node new_node = new Node(new_data);
/* 4. Make next of new Node as next of prev_node */
new_node.next = prev_node.next;
/* 5. make next of prev_node as new_node */
prev_node.next = new_node;
}
```

**time complexity**of inserting a node at start of the List is O(1).

```
struct node *cursor = head;
for(int i=1; i < position; i++) {
if(cursor->next != NULL) {
cursor = cursor->next;
}
}
```