Linked List Insertion and Deletion Program in C

June 9, 2022

Singly linked list Insertion and Deletion in C

We will look at all possible ways of insertion and deleting a node in a Single Linked List.

Things Discussed in the Post

We will be discussing the following in this post –

Insertion in a Linked List
- At Start
- At end
- After a given position
Deletion in a Linked List
- At start
- At end
- After a given position

First Lets understand what a Linked List is?

A linked List as the name suggests is a chain of linked data connected to one another in a sequential format just like a chain. A linked list has the following components in general –

Data – This contains the data value held in any individual node of the linked list
Next Pointer – This contains the address to the next node in a Linked List

Following are also some commonly used terminologies with a Linked List –

Node – Individual component with its data and next pointer value together is called a node
Head – The first node in the Linked List is called the head node.
Tail – The last node in the Linked list is called as a tail node. Which points towards a NULL value.

Structure of Linked List

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

Let us first Look at Insertion

Possible positions to insert –

At Start
At end
A given position

Lets look at some pictures on how to insert and then we will look at the code –

Run

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

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

void insertStart(struct Node** head, int data){
    
    // dynamically create memory for this newNode
    struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
    
    // assign data value
    newNode->data = data;
    // change the next node of this newNode 
    // to current head of Linked List
    newNode->next = *head;

    //re-assign head to this newNode
    *head = newNode;
}

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

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

    newNode->data = data;
    // since this will be the last node so it will point to NULL
    newNode->next = NULL;

    // if the Linked List is empty this is the first node being entered
    if(*head==NULL){
        *head = newNode;
        return;
    }
    
    // create another variable to traverse the LL
    // *head should not be used as we do not want to change head
    struct Node* temp = *head;
    
    // traverse to the last node of Linked List
    while(temp->next!=NULL)
        temp = temp->next;
    
    // assign last node's next to this newNode
    temp->next = newNode;
}

// required for insertAfter
int getCurrSize(struct Node* node){
    int size=0;

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

void insertAfter(int n, int data, struct Node** head)
{
    int size = getCurrSize(*head);

    // Can only insert after 1st position
    // Can't insert if position to insert is greater than size of Linked List
    if(n < 1 || n > size) 
        printf("Invalid position to insert"); 
    
    else 
    { 
        struct Node* newNode = (struct Node*) malloc(sizeof(struct Node)); 
        newNode->data = data;
        newNode->next = NULL;        
        
        // temp used to traverse the Linked List
        struct Node* temp = *head; 
        
        // traverse till the nth node
        while(--n)
            temp=temp->next;
        
        // assign newNode's next to nth node's next
        newNode->next= temp->next;
        // assign nth node's next to this new node
        temp->next = newNode;
        // newNode inserted b/w 3rd and 4th 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()
{
    struct Node* head = NULL;

    // Need '&' i.e. address as we need to change head
    insertStart(&head,3);
    insertStart(&head,2);
    insertStart(&head,1);

    // no need for '&' as head need not be changed
    // only doing traversal
    display(head); 
    
    insertEnd(&head,5);
    insertEnd(&head,6);
    insertEnd(&head,7);

    display(head); 

    //Inserts data: 4 after 3rd position
    insertAfter(3,4,&head);
    
    display(head); 
    return 0; 
}

Output

1 2 3 
1 2 3 5 6 7 
1 2 3 4 5 6 7

Let us Look at Deletion

Possible positions to delete –

At Start
At end
A given position

Lets look at some pictures on how to delete and then we will look at the code –

Code for Delete from Start and Delete From End

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

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

void deleteStart(struct Node** head){
    struct Node* temp = *head;
  
    // if there are no nodes in Linked List can't delete
    if(*head == NULL){
        printf("Linked List Empty, nothing to delete");
        return;
    }
    
    // move head to next node
    *head = (*head)->next;
    free(temp);
}

void deleteEnd(struct Node** head){
    struct Node* temp = *head;
    struct Node* previous;
    
    // if there are no nodes in Linked List can't delete
    if(*head == NULL){
        printf("Linked List Empty, nothing to delete");
        return;
    }
    
    // if Linked List has only 1 node
    if(temp->next == NULL){
        *head = NULL;
        return;
    }
    
    // else traverse to the last node
    while (temp->next != NULL) 
    {
        // store previous link node as we need to change its next val
        previous = temp; 
        temp = temp->next; 
    }
    // Curr assign 2nd last node's next to Null
    previous->next = NULL;
    // delete the last node
    free(temp);
    // 2nd last now becomes the last node
}
void insertStart(struct Node** head, int data){
    
    // dynamically create memory for this newNode
    struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
    
    // assign data value
    newNode->data = data;
    // change the next node of this newNode 
    // to current head of Linked List
    newNode->next = *head;

    //re-assign head to this newNode
    *head = 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
    insertStart(&head,6);
    insertStart(&head,5);
    insertStart(&head,4);
    insertStart(&head,3);
    insertStart(&head,2);
    insertStart(&head,1);
    
    display(head);
    
    deleteStart(&head);
    display(head);
    
    deleteEnd(&head);
    display(head);
    
    return 0; 
}

Output

1 2 3 4 5 6 
2 3 4 5 6 
2 3 4 5

Deletion nth Node (A position)

Let us look at the code for deletion of a node at a position that is deletion nth node.

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

struct Node{
    int data;
    struct Node *next;
};
void deleteStart(struct Node** head);
int getCurrSize(struct Node* node);

// to delete nth node
void deletePosition(struct Node** head, int n){
    struct Node* temp = *head;
    struct Node* previous;

    //if the head node itself needs to be deleted
    int size = getCurrSize(*head);
    
    // not valid
    if(n < 1 || n > size){
        printf("Enter valid position\n");
        return;
    }
    
    // delete the first node
    if(n == 1){
        deleteStart(head);
        return;
    }
    
    // traverse to the nth node
    while (--n) 
    {
        // store previous link node as we need to change its next val
        previous = temp; 
        temp = temp->next; 
    }
    // change previous node's next node to nth node's next node
    previous->next = temp->next;
    // delete this nth node
    free(temp);
}

void deleteStart(struct Node** head){
    struct Node* temp = *head;
  
    // if there are no nodes in Linked List can't delete
    if(*head == NULL){
        printf("Linked List Empty, nothing to delete");
        return;
    }
    
    // move head to next node
    *head = (*head)->next;
    free(temp);
}

// required for deletePosition
int getCurrSize(struct Node* node){
    int size=0;

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

void insertStart(struct Node** head, int data){
    
    // dynamically create memory for this newNode
    struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
    
    // assign data value
    newNode->data = data;
    // change the next node of this newNode 
    // to current head of Linked List
    newNode->next = *head;

    //re-assign head to this newNode
    *head = 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
    insertStart(&head,5);
    insertStart(&head,4);
    insertStart(&head,3);
    insertStart(&head,2);
    insertStart(&head,1);
    
    display(head);
    
    // delete 3rd node
    deletePosition(&head, 3);
    display(head);    
    
    // delete 1st node
    deletePosition(&head, 1);
    display(head);
    
    return 0; 
}

Output

1 2 3 4 5 
1 2 4 5 
2 4 5