Linked List Insertion and Deletion Program in C++

Program for Singly Linked List Insertion and Deletion in C++

Lets try to understand how we can do Insertion and deletion Operations on a Linked List in C++. We will look at most effective methods to do so.

Linked List

We will look at all different methods to insert and delete in the Linked List.

Make sure that you are acquainted with what Linked List is, all terminologies like

  • head
  • tail
  • node
  • data
  • pointer
  • next etc.

If you are new to Linked List, please do check this page here –

Structure of the Linked List

struct Node{
    int data;
    struct Node *next;
};
class Node{
    public:
    int data;
    Node *next;
};

Insertion in Linked List in C++

We will look at three different methods –

  • Method 1: Linked List Insertion using Struct
  • Method 2: Linked List Insertion using class (without class methods)
  • Method 3: Linked List Insertion using class (with class methods)

Insertion Positions

Insertion can be done at the following positions, we will write separate methods for each to demonstrate all possible variations –

  • At start (Default)
  • At last
  • After a certain Node
Singly Linked List Insertion and Deletion in C++ img1
Singly Linked List Insertion and Deletion in C++ img2
Singly Linked List Insertion and Deletion in C++ img3
Run
#include<iostream>
using namespace std;

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) 
        cout << "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){
        cout << node->data << " "; node = node->next;
    }
    cout << endl;
}

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

    // Need '&' i.e. address as we need to change head
    insertStart(&head,5);
    insertStart(&head,10);
    insertStart(&head,15);

    
    insertEnd(&head,20);
    insertEnd(&head,25);
    insertEnd(&head,30);
    insertEnd(&head,35);

    //Inserts data: 100 after 3rd position
    insertAfter(3, 100,&head);
    
    display(head); 
    return 0; 
}
Run
#include<iostream>
using namespace std;

class Node
{
    public:
    int data;
    Node *next;
};

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

    Node* newNode = new Node();

    // assign data value
    newNode->data = data;
    // change the next node of this newNode 
    // to current head of Linked List
    newNode->next = *head;

    //changing the new head to this freshly entered node
    *head = newNode;

}

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

    Node* newNode = new Node();

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

    //need this if there is no node present in linked list at all
    if(*head==NULL){
        *head = newNode;
        return;
    }

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

int calcSize(Node* node){
    int size=0;

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

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

    // Can only insert after 1st position
    // Can't insert if position to insert is greater than size of Linked List
    if(n < 1 || size < n)
    {
        cout << "Not Valid position to insert" << endl; 
    } 
    else { 

        Node* temp = *head; 
        Node* newNode = new Node(); 
        
        newNode->data = data;
        newNode->next = NULL;

        // 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(Node* node){

    //as linked list will end when Node is Null
    while(node!=NULL){
        cout << node->data << " "; node = node->next;
    }
    cout << endl;
}

int main(){

    Node* head = NULL;

     /*Need & i.e. address as we
    need to change head address
    */
    insertStart(&head,5);
    insertStart(&head,10);
    insertStart(&head,15);

    insertLast(&head,20);
    insertLast(&head,25);
    insertLast(&head,30);
    insertLast(&head,35);

    //Inserts after 3rd position
    insertPosition(3,100,&head);

    /*No need for & i.e. address as we do not
    need to change head address
    */
    display(head); 
    return 0;  
}
Run
#include<iostream>
using namespace std;

class Node
{
    public:
    int data;
    Node *next;
};

class LinkedList
{
    private:
        Node* head;
    public:
        LinkedList() { // constructor
        head = NULL;
    }
        int calcSize();
        void insertStart(int data);
        void insertLast(int data);
        void insertPosition(int pos, int data);
        void display();
};

void LinkedList::insertStart(int data){

    Node* newNode = new Node();
    
    // assign data value
    newNode->data = data;
    // change the next node of this newNode 
    // to current head of Linked List
    newNode->next = head;

    //changing the new head to this freshly entered node
    head = newNode;

}

void LinkedList::insertLast(int data){

    Node* newNode = new Node();

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

    //need this if there is no node present in linked list at all
    if(head==NULL){
        head = newNode;
        return;
    }

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

int LinkedList::calcSize(){
    
    Node* node = new Node();
    node = head;
    
    int size=0;

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

void LinkedList::insertPosition(int n, int data)
{
    int size = calcSize();

    // Can only insert after 1st position
    // Can't insert if position to insert is greater than size of Linked List
    if( n < 1 || size < n)
    {
        cout << "Not Valid position to insert" << endl; 
    } 
    else { 

        Node* temp = head; 
        Node* newNode = new Node(); 

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

        // 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 LinkedList::display(){
    
    Node* node = new Node();
    node = head;
    
    //as linked list will end when Node is Null
    while(node!=NULL){
        cout << node->data << " "; node = node->next;
    }
    cout << endl; 
} 

int main()
{ 
    LinkedList* list = new LinkedList(); 
    list->insertStart(5);
    list->insertStart(10);
    list->insertStart(15);

    list->insertLast(20);
    list->insertLast(25);
    list->insertLast(30);
    list->insertLast(35);

    // Inserts after 3rd position
    list->insertPosition(3, 100);

    list->display(); 
    return 0;  
}

Output

15 10 5 100 20 25 30 35 

Deletion in Linked List in C++

Again, we will look at three different methods –

  • Method 1: Linked List deletion using Struct
  • Method 2: Linked List deletion using class (without class methods)
  • Method 3: Linked List deletion using class (with class methods)

Insertion Positions

Deletion can be done at the following positions, we will write separate methods for each to demonstrate all possible variations –

  • At start (Default)
  • At last
  • After a certain Node
linked list insertion and deletion program in c++ part1
linked list insertion and deletion program in c++ part2
linked list insertion and deletion program in c++ part3
#include<iostream>
#include<stdlib.h> using namespace std; struct Node{ int data; struct Node *next; }; void insert(struct Node** head, int data); int getCurrSize(struct Node* node); void deleteStart(struct Node** head){ struct Node* temp = *head; // if there are no nodes in Linked List can't delete if(*head == NULL){ cout << "Linked List Empty, nothing to delete" ;
return;
}

// move head to next node
*head = (*head)->next; cout << "\nValue deleted: " << temp->data << endl; 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){ cout << "Linked List Empty, nothing to delete" ;
return;
}

// if Linked List has only 1 node
if(temp->next == NULL){ *head = NULL; cout << "\nValue deleted: " << temp->data << endl;
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; cout << "\nValue deleted: " << temp->data << endl; // delete the last node free(temp); // 2nd last now becomes the last node } // to deletePos nth node void deletePos(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){ cout << "\nEnter 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;
cout << "\nValue deleted: " << temp->data << endl;

// delete this nth node
free(temp);
}

void insert(struct Node** head, int data)
{
struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
newNode->data = data; newNode->next = *head; *head = newNode; } // required for deletePos int getCurrSize(struct Node* node){ int size=0; while(node!=NULL){ node = node->next; size++; } return size; } void display(struct Node* node){ // as linked list will end when Node is Null while(node!=NULL){ cout << node->data << " "; node = node->next; } cout << endl; } int main() { struct Node* head = NULL; insert(&head,10); insert(&head,20); insert(&head,30); insert(&head,40); insert(&head,50); insert(&head,60); insert(&head,70); display(head); deleteStart(&head); display(head); deleteEnd(&head); display(head); // delete 4th node deletePos(&head,4); display(head); // delete the 1st node deletePos(&head,1); display(head); deletePos(&head,-2); // invalid pos deletePos(&head,10); // invalid pos return 0; }
#include<iostream>
using namespace std;

class Node
{
    public:
    int data;
    Node *next;
};

int calcSize(Node* node){
    int size=0;

    while(node!=NULL){
        node = node->next;
        size++;
    }
    return size;
}
void deleteStart(Node** head){
    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;
    }
    
    cout << "\nValue Deleted: " << temp->data;
    
    // move head to next node
    *head = (*head)->next;
    free(temp);
}
void deleteEnd(Node** head){
    Node* temp = *head;
    Node* previous;
    
    // Can't delete from empty Linked List
    if(*head == NULL){
        cout << ("Empty List, can't delete"); 
return;
}

// if Linked List has only 1 node
if(temp->next == NULL){ cout << "\nValue Deleted: " << (*head)->data; *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; cout << "\nValue Deleted: " << temp->data; // delete the last node free(temp); // 2nd last now becomes the last node } void deletePos(Node** head, int n) { Node* temp = *head; Node* previous; int size = calcSize(*head); if(n < 1 || n > size){ cout << "\nEnter valid position\n";
return;
}

// if first node has to be deleted
if(n == 1) {
deleteStart(head);
return;
}

//traverse till the nth node
while (--n) {
// store previous link as we need to change its next val
previous = temp;
temp = temp->next; } // previous node's next changed to nth node's next previous->next = temp->next; cout << "\nValue deleted: " << temp->data; free(temp); } void insert(Node** head, int data){ Node* newNode = new Node(); newNode->data = data; newNode->next = *head; // assigned head to newNode *head = newNode; } void display(Node* node){ cout << "\n"; //as linked list will end when Node is Null while(node!=NULL){ cout << node->data << " "; node = node->next; } cout << endl; } int main(){ Node* head = NULL; insert(&head,10); insert(&head,20); insert(&head,30); insert(&head,40); insert(&head,50); insert(&head,60); insert(&head,70); display(head); deleteStart(&head); display(head); deleteEnd(&head); display(head); // delete 4th node deletePos(&head,4); display(head); // delete the 1st node deletePos(&head,1); display(head); deletePos(&head,-2); // invalid pos deletePos(&head,10); // invalid pos return 0; }
#include<iostream>
using namespace std;

class Node
{
    public:
    int data;
    Node *next;
};

class LinkedList
{
    private:
        Node* head;
    public:
        LinkedList() { // constructor
        head = NULL;
    }
        int calcSize();
        void deleteStart();
        void deleteEnd();
        void deletePos(int pos);
        void display();
        void insert(int data);
};

void LinkedList::deleteStart(){
    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;
    }
    
    cout << "\nValue Deleted: " << temp->data;
    
    // move head to next node
    head = head->next;
    free(temp);
}

void LinkedList::deleteEnd(){
    Node* temp = head;
    Node* previous;
    
    // Can't delete from empty Linked List
    if(head == NULL){
        cout << ("Empty List, can't delete"); 
return;
}

// if Linked List has only 1 node
if(temp->next == NULL){ cout << "\nValue Deleted: " << head->data; 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; cout << "\nValue Deleted: " << temp->data; // delete the last node free(temp); // 2nd last now becomes the last node } void LinkedList::deletePos(int n) { Node* temp = head; Node* previous; int size = calcSize(); if(n < 1 || n > size){ cout << "\nEnter valid position\n";
return;
}

// if first node has to be deleted
if(n == 1) {
deleteStart();
return;
}

//traverse till the nth node
while (--n) {
// store previous link as we need to change its next val
previous = temp;
temp = temp->next; } // previous node's next changed to nth node's next previous->next = temp->next; cout << "\nValue deleted: " << temp->data; free(temp); } int LinkedList::calcSize(){ Node* node = new Node(); node = head; int size=0; while(node!=NULL){ node = node->next; size++; } return size; } void LinkedList::insert(int data){ Node* newNode = new Node(); newNode->data = data; newNode->next = head; // assigned head to newNode head = newNode; } void LinkedList::display(){ Node* node = new Node(); node = head; cout << "\n"; //as linked list will end when Node is Null while(node!=NULL){ cout << node->data << " "; node = node->next; } cout << endl;
}

int main(){

LinkedList* list = new LinkedList();
list->insert(10); list->insert(20); list->insert(30); list->insert(40); list->insert(50); list->insert(60); list->insert(70); list->display(); list->deleteStart(); list->display(); list->deleteEnd(); list->display(); // delete 4th node list->deletePos(4); list->display(); // delete the 1st node list->deletePos(1); list->display(); list->deletePos(-2); // invalid pos list->deletePos(10); // invalid pos }

Output

70 60 50 40 30 20 10

Value Deleted: 70
60 50 40 30 20 10

Value Deleted: 10
60 50 40 30 20

Value deleted: 30
60 50 40 20

Value Deleted: 60
50 40 20

Enter valid position
Enter valid position