# Insertion in Linked List | C Program

## Insertion in Singly linked list

Singly linked list has two field. first one is data and second field is link that refers to the second node. In a singly linked list, each node stores a reference to an object that is an element of the sequence, as well as a reference to the next node of the list.

 Insertion Time Complexity (AVG) Θ(1) Insertion Time Complexity (Worst) O(1) Space Complexity O(1)

There are three possible positions where we can enter a new node in a linked list –

• Insertion at beginning
• Insertion after nth position
• Insertion at end

Generally by definition, if a new node is added it is added at the beginning of the linked list and not the end. So, we do not need to traverse the list every time for insertion

### Singly Linked List Definition

```struct Node {
int Data;
Struct Node* next;
};```

## Insertion at beginning

Imagine our linked list is not necessarily sorted and there is no reason to insert a new node in any special place in the list. Then we have an easiest place to insert the node is at the beginning of the list.  An algorithm that does so follows.

#### Algorithm of insertion at the beginning

• Create a new node
• Assign its data value
• Assign newly created node’s next ptr to current head reference. So, it points to the previous start node of the linked list address
• Change the head reference to the new node’s address.
```void insertStart(struct Node** head, int data){

struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));

newNode->data = data;

//changing the new head to this freshly entered node
}``` ### Program

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

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

void insertStart(struct Node** head, int data){

struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));

newNode->data = data;

//changing the new head to this freshly entered node
}

void insertLast(struct Node** head, int data){

struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));

newNode->data = data;
newNode->next = NULL;

//need this if there is no node present in linked list at all
return;
}

struct Node* temp = *head;

while(temp->next!=NULL)
temp = temp->next;

temp->next = newNode;
}

void display(struct Node* node){

//as linked list will end when Node is Null
while(node!=NULL){
printf("%d ",node->data);
node = node->next;
}
printf("\n");
}

int main()
{

//creating 4 pointers of type struct Node
//So these can point to address of struct type variable
struct Node* head = NULL;
struct Node* node2 = NULL;
struct Node* node3 = NULL;
struct Node* node4 = NULL;

// allocate 3 nodes in the heap
head =  (struct Node*)malloc(sizeof(struct Node));
node2 = (struct Node*)malloc(sizeof(struct Node));
node3 = (struct Node*)malloc(sizeof(struct Node));
node4 = (struct Node*)malloc(sizeof(struct Node));

head->data = 15; // data set for head node
head->next = node2; // next pointer assigned to address of node2

node2->data = 10;
node2->next = node3;

node3->data = 12;
node3->next = node4;

node4->data = 3;
node4->next = NULL;

// Need '&' i.e. address as we need to change head

printf("\nAfter Inserting Element\n");
// no need for '&' as head need not be changed
// only doing traversal
return 0;
}```

#### Output

`20 16 12`

### Insertion at ending

To insert element in linked list last we would use the following steps to insert a new Node at the last of the doubly linked list.

• Create a new node
• Assign its data value
• Assign its next node to NULL as this will be the last(tail) node
• Check if the list is empty
• Change the head node to the new node
• If not then traverse till the last node
• Assign the last node’s next pointer to this new node
• Now, the new node has become the last node. ```#include<stdio.h>
#include<stdlib.h>

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

void insertStart(struct Node** head, int data){

struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));

newNode->data = data;

//changing the new head to this freshly entered node
}

void insertLast(struct Node** head, int data){

struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));

newNode->data = data;
newNode->next = NULL;

//need this if there is no node present in linked list at all
return;
}

struct Node* temp = *head;

while(temp->next!=NULL)
temp = temp->next;

temp->next = newNode;
}

void display(struct Node* node){

//as linked list will end when Node is Null
while(node!=NULL){
printf("%d ",node->data);
node = node->next;
}
printf("\n");
}

int main()
{
struct Node* head = NULL;

// Need '&' i.e. address as we need to change head

// no need for '&' as head need not be changed    // only doing traversal
return 0;
}```

#### Output

`20 16 12 10 14 18 11 `

## Insertion at After nth position node

First we will create a new node named by newnode and put the position where u want to insert the node.

Now give the address of the new node in previous node means link the new node with previous node.

After this, give the address of current node in new node.Means link your new node also with current node. ### Final Code for all three and insert After nth Node

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

struct Node{
int data;
struct Node *next;
};
int calcSize(struct Node* node){
int size=0;

while(node!=NULL){
node = node->next;
size++;
}
return size;
}

void insertPosition(int pos, int data, struct Node** head)
{
int size = calcSize(*head);

//If pos is 0 then should use insertStart method
//If pos is less than 0 then can't enter at all
//If pos is greater than size then bufferbound issue
if(pos < 1 || size < pos)     {         printf("Can't insert, %d is not a valid position\n",pos);     }     else     {         struct Node* temp = *head;         struct Node* newNode = (struct Node*)         malloc(sizeof(struct Node));         newNode->data = data;
newNode->next = NULL;

while(--pos)
{
temp=temp->next;
}
//(25)->next = 10 as 12->next is 10
newNode->next= temp->next;
// (12)->next = 25
temp->next = newNode;
//new node added in b/w 12 and 10
}
}

void insertStart(struct Node** head, int data){

struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));

newNode->data = data;

//changing the new head to this freshly entered node
}

void insertLast(struct Node** head, int data){

struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));

newNode->data = data;
newNode->next = NULL;

//need this if there is no node present in linked list at all
return;
}

struct Node* temp = *head;

while(temp->next!=NULL)
temp = temp->next;

temp->next = newNode;
}

void display(struct Node* node){

//as linked list will end when Node is Null
while(node!=NULL){
printf("%d ",node->data);
node = node->next;
}
printf("\n");
}

int main()
{
struct Node* head = NULL;

// Need '&' i.e. address as we need to change head

`20 16 12 25 10 14 18 11 ` 