Linked List Insertion and Deletion Program

February 8, 2023

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.

Structure of the Linked List

struct Node{
    int data;
    struct Node *next;
};
class Node{
    public:
    int data;
    Node *next;
};
DSA desktop gif
DSA mobile gif

Deletion from nth position in singly Linked List

Deletion from end in singly Linked List

Reverse a linked list without changing links between nodes

Reverse a linked list by changing links between nodes

Linked List insertion in the middle

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

Prime Course Trailer

Related Banners

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

Get Prime

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

Get Prime
Course List
Course List

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout
Checkout

Singly Linked List

  • Introduction to Linked List in Data Structure
    Click Here
  • 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
  • Linked List Insertion and Deletion –
    C | C++ | Java
  • Reverse a linked list without changing links between nodes (Data reverse only) –
    C | C++ | Java
  • Reverse a linked list by changing links between nodes –
    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

Singly Linked List

  • 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