# Linked List – Inserting a node

### 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.

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
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 */
{

Node* new_node = new Node();
new_node->data = new_data;
}

/* Using this function we will inserting a new node after a given node in the linked list */
{

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 */
{
Node* new_node = new Node();

new_node->data = new_data;

new_node->next = NULL;

{
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<<" "<data;
node = node->next;
}
}

/* Driver function */
int main()
{
return 0;
}

```
```public class LinkedList
{

/* 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);

}

/* 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);

{
return;
}

new_node.next = null;

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()
{
while (tnode != null)
{
System.out.print(tnode.data+" ");
tnode = tnode.next;
}
}

/* Driver function */
public static void main(String[] args)
{

llist.append(4);

llist.push(3);

llist.push(2);

llist.append(5);