× Home

Insertion of node in a linked list

Inserting in a linked list

Consider the following linked list:

Insertion in this list can be divided into the following categories:

For insertion follwoing any of the above-mentioned cases, we would first need to create that extra node. And then, we overwrite the current connection and make new conections. And that is how we insert a new node at our desired place.

Syntax for creating a node:
struct Node *ptr = (struct Node*) malloc (size of(struct Node));
The above syntax will create a node, and the next thing one would need to do is set the data for this node.

ptr -> data = 0;
This will set the data.

Case 1: Insert at the beginning

In order to insert the new node at the beginning, we would need to have the ead pointer pointing to this new node and the new node's pointer to the current head.

Inserting at the beginning has the time complexity O(1).

Code

Create a struct Node* function insertAtFirst which will return the pointer to the new head.
We’ll pass the current head pointer and the data to insert at the beginning, in the function.
Create a new struct Node* pointer ptr, and assign it a new memory location in the heap.
Assign head to the next member of the ptr structure using ptr-> next = head, and the given data to its data member.
Return this pointer ptr.

struct Node * insertAtFirst(struct Node *head, int data){
struct Node * ptr = (struct Node *) malloc(sizeof(struct Node));
ptr->data = data;

ptr->next = head;
return ptr;
}

#include <stdio.h>
#include <stdlib.h>

struct Node
{
int data;
struct Node *next;
};

void linkedListTraversal(struct Node *ptr)
{
while (ptr != NULL)
{
printf("Element : %d\n", ptr->data);
ptr = ptr->next;
}
}

struct Node *insertATFirst(struct Node *head, int data)
{
struct Node *ptr = (struct Node *)malloc(sizeof(struct Node));
ptr->data = data;
ptr->next = head;
return ptr;
}

int main()
{
struct Node *head;
struct Node *second;
struct Node *third;
struct Node *fourth;

// Allocate memory fornodes in linked list in heap (dynamic memory allocate)
head = (struct Node *)malloc(sizeof(struct Node));
second = (struct Node *)malloc(sizeof(struct Node));
third = (struct Node *)malloc(sizeof(struct Node));
fourth = (struct Node *)malloc(sizeof(struct Node));

// link first and second nodes
head->data = 7;
head->next = second;

// link second and third nodes
second->data = 11;
second->next = third;

// link third and fourth nodes
third->data = 211;
third->next = fourth;

// terminate the list a the third node
fourth->data = 66;
fourth->next = NULL;

linkedListTraversal(head);
head = insertATFirst(head, 69);
linkedListTraversal(head);
return 0;
}

Case 2: Insert in between:

Assuming index starts from 0, we can insert an element at index i>0 as follows:

Bring a temporary pointer p pointing to the node before the element you want to insert in the linked list.
Since we want to insert between 8 and 2, we bring pointer p to 8.

Inserting at some node in between puts the time comlexity O(n).
As we have to traverse to get to the element.

Code

Create a struct Node* function insertAtIndex which will return the pointer to the head.
We’ll pass the current head pointer and the data to insert and the index where it will get inserted, in the function.
Create a new struct Node* pointer ptr, and assign it a new memory location in the heap.
Create a new struct Node* pointer pointing to head, and run a loop until this pointer reaches the index, where we are inserting a new node.
Assign p->next to the next member of the ptr structure using ptr-> next = p->next, and the given data to its data member.
Break the connection between p and p->next by assigning p->next the new pointer. That is, p->next = ptr.
Return head.

#include <stdio.h>
#include <stdlib.h>

struct Node
{
int data;
struct Node *next;
};

void linkedListTraversal(struct Node *ptr)
{
while (ptr != NULL)
{
printf("Element : %d\n", ptr->data);
ptr = ptr->next;
}
}

struct Node *insertAtIndex(struct Node *head, int data, int index)
{
struct Node *ptr = (struct Node *)malloc(sizeof(struct Node));

struct Node *p = head;
int i = 0;
while (i != index - 1)
{
p=p->next;
i++;
}
ptr->data = data;
ptr->next = p->next;
p->next = ptr;
return head;
}

int main()
{
struct Node *head;
struct Node *second;
struct Node *third;
struct Node *fourth;

// Allocate memory fornodes in linked list in heap (dynamic memory allocate)
head = (struct Node *)malloc(sizeof(struct Node));
second = (struct Node *)malloc(sizeof(struct Node));
third = (struct Node *)malloc(sizeof(struct Node));
fourth = (struct Node *)malloc(sizeof(struct Node));

// link first and second nodes
head->data = 7;
head->next = second;

// link second and third nodes
second->data = 11;
second->next = third;

// link third and fourth nodes
third->data = 211;
third->next = fourth;

// terminate the list a the third node
fourth->data = 66;
fourth->next = NULL;

linkedListTraversal(head);
insertAtIndex(head,55,2);
linkedListTraversal(head);

return 0;
}

Case 3: Insert at the end:

In order to insert an element at the end of the linked list, we bring a temporary pointer to the last element.

Inserting at the end has the time complexity as O(n).
As we have to traverse till we get to the end of the linklist.

Code

struct Node * insertAtEnd(struct Node *head, int data){
struct Node * ptr = (struct Node *) malloc(sizeof(struct Node));
ptr->data = data;
struct Node * p = head;

while(p->next!=NULL){
p = p->next;
}
p->next = ptr;
ptr->next = NULL;
return head;
}

#include <stdio.h>
#include <stdlib.h>

struct Node
{
int data;
struct Node *next;
};

void linkedListTraversal(struct Node *ptr)
{
while (ptr != NULL)
{
printf("Element : %d\n", ptr->data);
ptr = ptr->next;
}
}

struct Node *insertAtEnd(struct Node *head, int data)
{
struct Node *ptr = (struct Node *)malloc(sizeof(struct Node));

struct Node *p = head;

while (p->next!=NULL)
{
p=p->next;

}
ptr->data = data;
ptr->next = NULL;
p->next = ptr;
return head;
}

int main()
{
struct Node *head;
struct Node *second;
struct Node *third;
struct Node *fourth;

// Allocate memory fornodes in linked list in heap (dynamic memory allocate)
head = (struct Node *)malloc(sizeof(struct Node));
second = (struct Node *)malloc(sizeof(struct Node));
third = (struct Node *)malloc(sizeof(struct Node));
fourth = (struct Node *)malloc(sizeof(struct Node));

// link first and second nodes
head->data = 7;
head->next = second;

// link second and third nodes
second->data = 11;
second->next = third;

// link third and fourth nodes
third->data = 211;
third->next = fourth;

// terminate the list a the third node
fourth->data = 66;
fourth->next = NULL;

linkedListTraversal(head);
insertAtEnd(head,8888);
linkedListTraversal(head);

return 0;
}

Case 4: Insert after a node:

Similar to other cases, ptr can be inserted after a node as follows:
Ptr-> next = prevNode -> next;
prevNode -> next = ptr;

If we know the pointer to the previous node where we want to insert the new node, it would just take constant time O(1).

Code

Here, we already have a struct Node* pointer to insert the new node just next to it.
Create a struct Node* function insertAfterNode which will return the pointer to the head.
Pass into this function, the head node, the previous node, and the data.
Create a new struct Node* pointer ptr, and assign it a new memory location in the heap.
Since we already have a struct Node* prevNode given as a parameter, use it as p we had in the previous functions.
Assign prevNode->next to the next member of the ptr structure using ptr-> next = prevNode->next, and the given data to its data member.
Break the connection between prevNode and prevNode->next by assigning prevNode->next the new pointer. That is, prevNode->next = ptr.
Return head.

#include <stdio.h>
#include <stdlib.h>

struct Node
{
int data;
struct Node *next;
};

void linkedListTraversal(struct Node *ptr)
{
while (ptr != NULL)
{
printf("Element : %d\n", ptr->data);
ptr = ptr->next;
}
}

struct Node *insertAfterNode(struct Node *head, struct Node * prevNode, int data)
{
struct Node *ptr = (struct Node *)malloc(sizeof(struct Node));

ptr->data = data;
ptr->next = prevNode->next;
prevNode->next=ptr;
return head;
}

int main()
{
struct Node *head;
struct Node *second;
struct Node *third;
struct Node *fourth;

// Allocate memory fornodes in linked list in heap (dynamic memory allocate)
head = (struct Node *)malloc(sizeof(struct Node));
second = (struct Node *)malloc(sizeof(struct Node));
third = (struct Node *)malloc(sizeof(struct Node));
fourth = (struct Node *)malloc(sizeof(struct Node));

// link first and second nodes
head->data = 7;
head->next = second;

// link second and third nodes
second->data = 11;
second->next = third;

// link third and fourth nodes
third->data = 211;
third->next = fourth;

// terminate the list a the third node
fourth->data = 66;
fourth->next = NULL;

linkedListTraversal(head);
insertAfterNode(head,second,8888);
linkedListTraversal(head);

return 0;
}