Linked List Insertion and Deletion Program in C

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.

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
Linked List insertion and Deletion Example

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 –

linked list insertion and deletion program in c insertion1
linked list insertion and deletion program in c insertion21
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 –

linked list insertion and deletion program in c deletion
linked list insertion and deletion program in c deletion3

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
linked list insertion and deletion program in c deletion3

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