# 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 ComplexityO(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

```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
```void insertStart (struct Node **head, int data)
{

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

newNode - >
data = data;
newNode - >

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

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

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

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

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

#### Output

```Linklist : 15 10 12 3

After Inserting Element

Linklist : 25 15 10 12 3```

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

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 ()
{

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

Run
```#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)
{

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

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 ()
{

//Inserts after 3rd position

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

#### Output

`20 16 12 25 10 14 18 11 ` ### Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

## Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

## Checkout list of all the video courses in PrepInsta Prime Subscription

• Introduction to Linked List in Data Structure
• Linked List in – C | C++ | Java
• Singly Linked List in – C | C++ | Java
• Insertion in singly Linked List – C | C++ | Java
• Insertion at beginning in singly Linked List  – C | C++Java
• Insertion at nth position in singly Linked List  – C | C++Java
• Insertion at end in singly Linked List  – C | C++Java
• Deletion in singly Linked List  – C | C++Java
• Deletion from beginning in singly linked list : C | C++ | Java
• Deletion from nth position in singly linked list : C | C++ | Java
• Deletion from end in singly linked list : C | C++ | Java
• Reverse a linked list without changing links between nodes (Data reverse only) – C | C++Java
• Linked List Insertion and Deletion – C | C++Java
• Reverse a linked list by changing links between nodes – C | C++Java
• Linked List insertion in the middle – C | C++Java
• Print reverse of a linked list without actually reversing – C |C++Java
• Search an element in a linked list – C | C++Java
• Insertion in a Sorted Linked List – C | C++Java
• Delete alternate nodes of a Linked List – C | C++Java
• Find middle of the linked list – C | C++Java
• Reverse a linked list in groups of given size – C | C++Java
• Find kth node from end of the linked list – C | C++Java
• Append the last n nodes of a linked list to the beginning of the list – C | C++Java
• Check whether linked list is palindrome or not – C | C++Java
• Fold a Linked List – C | C++Java
• Insert at a given position – C | C++Java
• Delete at a given position – C | C++Java

• Introduction to Linked List in Data Structure
C | C++ | Java
• Singly Linked List in –
C | C++ | Java
• Insertion in singly Linked List –
C | C++ | Java
• Insertion at beginning in singly Linked List  –
C | C++Java
• Insertion at nth position in singly Linked List  –
C | C++Java
• Insertion at end in singly Linked List  –
C | C++Java
• Deletion in singly Linked List  –
C | C++Java
• Deletion from beginning in singly linked list :
C | C++ | Java
• Deletion from nth position in singly linked list :
C | C++ | Java
• Deletion from end in singly linked list :
C | C++ | Java
• Linked List Insertion and Deletion –
C | C++Java
• Reverse a linked list without changing links between nodes (Data reverse only) –
C | C++Java
C | C++Java
• Print reverse of a linked list without actually reversing –
C |C++Java
• Print reverse of a linked list without actually reversing –
C |C++Java
• Insertion in the middle Singly Linked List –
C | C++Java
• Insertion in a Sorted Linked List –
C | C++Java
• Delete alternate nodes of a Linked List –
C | C++Java
• Find middle of the linked list –
C | C++Java
• Reverse a linked list in groups of given size –
C | C++Java
• Find kth node from end of the linked list –
C | C++Java
• Append the last n nodes of a linked list to the beginning of the list –
C | C++Java
• Check whether linked list is palindrome or not –
C | C++Java
• Fold a Linked List –
C | C++Java
• Insert at given Position –
C | C++Java
• Deletion at given Position –
C | C++Java