### Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

In this article, we are going to learn about the insertion operations in a singly linked list.

There are three primary insertion operations.

**Insert at the beginning of the list**.**Insert at the end of the list**.**Insert after a given node**.

Let us have a look at all these Insertion operations.

### Approach (Insert at the beginning)

What should we do to insert a node at the beginning?

It is pretty simple. Let us take an example to understand it.

- Suppose the given list is 2 → 3, and we have to insert 1 at the front of the list. So, to insert 1 at front, we will simply make 1’s next point to 2 and make 1 as the new head of the linked list and our final linked list will be: 1 → 2 → 3.

Also, keep in mind that, the new node which gets added at the front of the list, will be the **new head** of the list.

This is quite simple. Let the newly created node be **x** and make **x → next = head** and then make **head = x**, as explained above.

### Algorithm

1) Create the node which is to be inserted, say **newnode**.

2) If the **list is empty**, the **head** will point to the **newnode**, and we will return.

3) Else, If the **list is not empty**:

- Make
**newnode → next = head**. This step ensures that the**new node**is being added at the beginning of the list. - Then after that, make
**head = newnode**, as the**new node**is now the first node of the list, hence the**new head**.

**Time Complexity:** O(1), as we are only accessing and changing the head of the list.

**Space Complexity:** O(1), as no extra space is being used.

### Approach (Insert at the end)

What should we do to insert an element at the end of a linked list?

It is pretty simple. Let us take an example to understand it.

- Suppose the list is 1 → 2 →3, and we have to add 4 at the end of this list. So, we just have to make the connection between 3 and 4, and finally, make the next of 4 as null as it is the
**new last node**.

So, following the above approach of insertion at the end, we will first take a pointer **curr** and using it we will traverse to the **last node** of the list. As explained above, after reaching the **last node**, we will simply make **curr → next = newnode** and **newnode → next = NULL**.

### Algorithm

1) Create the node which is to be inserted, say **newnode**.

2) If the **list is empty**, make **head** point to the **newnode**, and return.

3) Else, if the **list is not empty**:

- Using a pointer
**curr**, traverse the list up to the**last node**of the list. - After the traversal,
**curr**will be standing at the**last node**, and now, to insert the**newnode**at the**end of the list**, make**curr → next = newnode**and then**newnode → next = NULL**, as**newnode**is the new last node of the linked list.

**Time Complexity:** O(N), as we have to traverse the list to reach the end of the list.

**Space Complexity:** O(1), as no extra space is being used.

### Approach (Insert after a given node)

In this approach, we will be given a node’s address. We will have to insert the new node just after this given node.

As we have the address of the node, we don’t have to traverse the linked list. Let take an example to understand it more clearly; suppose the given list is: 1 → 2 → 3, and we have the address of 2, and we want to insert a new node (say **x**) after this node 2.

- So, to insert the node, we will simply do
**x → next = 2 → next**and then**2 → next = x**. - By doing
**x → next = 2 → next**, we are making sure that**x**is being inserted after 2, and by doing**2 → next = x**, we are again making sure that the links are complete.

Suppose the address of the node after which we have to insert the new node is **NODE**. So, now to insert the **newnode** just after this node, we will do the following steps.

- First, we will make
**newnode → next = NODE → next** - Then, we will make
**NODE → next = newnode** - And our insertion will be done.

### Algorithm

1) Create the node which is to be inserted, say **NewNode**, and the node whose address is given is **prevnode**.

2) If the **address of the given node is NULL**, simply return.

3) Else, if **address is not NULL**:

- Make the
**next of NewNode**point to the**next of prevnode**and then make**next of prevnode point to NewNode**(see steps below).- NewNode → next = prevnode→ next
- prevnode – > next= NewNode

4) After performing the above steps, our new node **NewNode** will get inserted after the **prevnode**.

**Time Complexity:** O(1), as we have the address of the node after which the new node is to be inserted.

**Space Complexity:** O(1), as no extra space is being used.

To get a clearer understanding, have a look at the dry run. Let us head on to the dry run of these methods.

### Dry Run

### Code Implementation

#include<stdio.h> #include<stdlib.h> struct Node { int data; struct Node* next; }; void push(struct Node** head_ref, int new_data) { struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } /* Using this function we will inserting a new node after a given node in the linked list */ void addtAfter(struct Node* prev_node, int new_data) { if (prev_node == NULL) { printf("the given previous node cannot be NULL"); return; } struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); new_node->data = new_data; new_node->next = prev_node->next; prev_node->next = new_node; } /* Using this function we will inserting a new node at the end of the linked list */ void append(struct Node** head_ref, int new_data) { struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); struct Node *last = *head_ref; new_node->data = new_data; new_node->next = NULL; if (*head_ref == NULL) { *head_ref = new_node; return; } while (last->next != NULL) last = last->next; last->next = new_node; return; } /* Using this function we will be printing the content of the linked list */ void printList(struct Node *node) { while (node != NULL) { printf("%d ",node->data); node = node->next; } } /* Driver function */ int main() { struct Node* head = NULL; append(&head, 4); push(&head, 3); push(&head, 2); append(&head, 5); addtAfter(head->next, 8); printf("Created Linked list is: "); printList(head); return 0; }

#include <bits stdc++.h=""> using namespace std; /* Node structure of a linked list node */ class Node { public: int data; Node *next; }; /* Using this function we will be inserting new nodes at the head of the list */ void push(Node** head_ref, int new_data) { Node* new_node = new Node(); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } /* Using this function we will inserting a new node after a given node in the linked list */ void addtAfter(Node* prev_node, int new_data) { if (prev_node == NULL) { cout<<"the given previous node cannot be NULL"; return; } Node* new_node = new Node(); new_node->data = new_data; new_node->next = prev_node->next; prev_node->next = new_node; } /* Using this function we will inserting a new node at the end of the linked list */ void append(Node** head_ref, int new_data) { Node* new_node = new Node(); Node *last = *head_ref; new_node->data = new_data; new_node->next = NULL; if (*head_ref == NULL) { *head_ref = new_node; return; } while (last->next != NULL) last = last->next; last->next = new_node; return; } /* Using this function we will be printing the content of the linked list */ void printList(Node *node) { while (node != NULL) { cout<<" "<<node->data; node = node->next; } } /* Driver function */ int main() { Node* head = NULL; append(&head, 4); push(&head, 3); push(&head, 2); append(&head, 5); addtAfter(head->next, 8); cout<<"Created Linked list is: "; printList(head); return 0; }

public class LinkedList { Node head; /* Node structure of a linked list node */ class Node { int data; Node next; Node(int d) {data = d; next = null; } } /* Using this function we will be inserting new nodes at the head of the list */ public void push(int new_data) { Node new_node = new Node(new_data); new_node.next = head; head = new_node; } /* Using this function we will inserting a new node after a given node in the linked list */ public void insertAfter(Node prev_node, int new_data) { if (prev_node == null) { System.out.println("The given previous node cannot be null"); return; } Node new_node = new Node(new_data); new_node.next = prev_node.next; prev_node.next = new_node; } /* Using this function we will inserting a new node at the end of the linked list */ public void append(int new_data) { Node new_node = new Node(new_data); if (head == null) { head = new Node(new_data); return; } new_node.next = null; Node last = head; while (last.next != null) last = last.next; last.next = new_node; return; } /* Using this function we will be printing the content of the linked list */ public void printList() { Node tnode = head; while (tnode != null) { System.out.print(tnode.data+" "); tnode = tnode.next; } } /* Driver function */ public static void main(String[] args) { LinkedList llist = new LinkedList(); llist.append(4); llist.push(3); llist.push(2); llist.append(5); llist.insertAfter(llist.head.next, 8); System.out.println("\nCreated Linked list is: "); llist.printList(); } }

# Node structure of a linked list node class Node: def __init__(self, data): self.data = data self.next = None # Linked List class contains a Node object class LinkedList: def __init__(self): self.head = None # Using this function we will be inserting new nodes at the head of the list def push(self, new_data): new_node = Node(new_data) new_node.next = self.head self.head = new_node # Using this function we will inserting a new node after a given node in the linked list def addAfter(self, prev_node, new_data): if prev_node is None: print("the given previous node cannot be NULL") return new_node = Node(new_data) new_node.next = prev_node.next prev_node.next = new_node # Using this function we will inserting a new node at the end of the linked list def append(self, new_data): new_node = Node(new_data) if self.head is None: self.head = new_node return last = self.head while (last.next): last = last.next last.next = new_node # Using this function we will be printing the content of the linked list def printList(self): temp = self.head while (temp): print(temp.data,end=" ") temp = temp.next if __name__=='__main__': llist = LinkedList() llist.append(4) llist.push(3) llist.push(2) llist.append(5) llist.addAfter(llist.head.next, 8) print("Created Linked list is:") llist.printList()

#### Output

Created Linked list is: 2 3 8 4 5

**Time Complexity:** O(n), as list traversal is needed

[forminator_quiz id=”5751″]

So, in this article, we have tried to explain how to insert nodes at different positions in a linked list. As we are doing the insertions in O(1) time mostly (not in the case of inserting at the end), this problem becomes an important one for coding interviews. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.