Doubly Linked List Insertion and Deletion Program in C++

November 1, 2023

Doubly Linked List Insertion and Deletion in C++

We will explore all the different methods to do insertion and deletion in a doubly-linked list in C++ using struct, classes and class functions. Let us go!

A doubly Linked list is sometimes used over the singly Linked list in C++ since they allow traversal in both forward and backward directions. While singly linked list allowed traversal in backward direction only.

Definition

A Doubly Linked list is a data structure that contains a chain of nodes connected to one another and where each node has a data value two pointers: next and previous where the next node contains the address to the next node in the linked list and the previous node contains the address to the previous node in the chained linked list.

A doubly linked has the following –

Data value
Next Pointer
Previous Pointer

Each unit of the above is called a node.

The start of Linked List is denoted by a special additional pointer called head.

Some versions of doubly-linked lists may also have trail pointer that denotes the end of the linked list.

Structure of a Node in Doubly Linked List

Using Struct

Using Class

Using Struct

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

Using Class

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

Insertion in doubly linked list

Insertion at beginning in doubly linked list

Insertion at n^th node in doubly linked list

Deletion in doubly linked list

Deletion from nth node in doubly linked list

Operations

We can do delete and insertion operations on the doubly linked list at various positions which are –

At beginning
At the end
In the middle

Let us now look at the programs for the same. First with insertion operations.

Doubly Linked List Insertion in C++

Method 1

Method 2

Method 1

This method uses class to create node structure but uses general functions with the requirement of the head being passed as a parameter in each of them

Run

#include<iostream>
using namespace std;

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

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

  Node *new_node = new Node ();

  new_node->data = data;
  new_node->next = *head;
  new_node->prev = NULL;

  // if DLL had already >=1 nodes
  if (*head != NULL)
    (*head)->prev = new_node;

  // changing head to this
  *head = new_node;
}

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

  Node *new_node = new Node ();

  // assign data
  // since this will be the last node its next will be NULL
  new_node->data = data;
  new_node->next = NULL;

  //if we are entering the first node
  if (*head == NULL)
    {
      *head = new_node;
      new_node->prev = NULL;
      return;
    }

  struct Node *last = *head;

  // traverse to the current last node
  while (last->next != NULL)
    last = last->next;

  // assign current last node's next to this new node
  // also assign new node's prev to this 'last' node
  last->next = new_node;
  new_node->prev = last;
  // new_node becomes the last node now
}

int countItems (Node * node)
{
  int count = 0;

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

void insertAfter (int n, int data, Node ** head)
{
  int len = countItems (*head);

  // if insertion position is 0 means entering at start
  if (n == 0)
    {
      insertStart (head, data);
      return;
    }
  // means inserting after last item
  if (n == len)
    {
      insertLast (head, data);
      return;
    }

  // else insertion will happen somewhere in the middle


  if (n < 1 || len < n)
    cout << "Invalid position" << endl; else { Node *new_node = new Node (); new_node->data = data;
      new_node->next = NULL;
      new_node->prev = NULL;

      // nthNode used to traverse the Linked List
      struct Node *nthNode = *head;

      // traverse till the nth node
      while (--n)
	{
	  nthNode = nthNode->next;
	}

      struct Node *nextNode = nthNode->next;	// (n+1)th node

      // assigning (n+1)th node's previous to this new node
      nextNode->prev = new_node;

      // new_node's next assigned to (n+1)th node
      new_node->next = nextNode;
      // new_node's previous assigned to nth node
      new_node->prev = nthNode;

      // assign nth node's next to new_node
      nthNode->next = new_node;
    }
}

void display (Node * node)
{
  Node *end = NULL;

  cout << "Reading DLL Forward: ";
  while (node != NULL)
    {
      cout << node->data << " "; end = node; node = node->next;
    }

  cout << "\nReading DLL Backward: ";

  while (end != NULL)
    {
      cout << end->data << " "; end = end->prev;
    }
  cout << "\n\n";
}

int main ()
{

  Node *head = NULL;

  insertStart (&head, 6);
  insertStart (&head, 4);
  insertStart (&head, 2);

  display (head);

  insertLast (&head, 8);
  insertLast (&head, 12);
  insertLast (&head, 14);

  display (head);

  //Inserts after 4th position
  insertAfter (4, 10, &head);

  display (head);
  return 0;
}

Output

Reading DLL Forward: 2 4 6 
Reading DLL Backward: 6 4 2 

Reading DLL Forward: 2 4 6 8 12 14 
Reading DLL Backward: 14 12 8 6 4 2 

Reading DLL Forward: 2 4 6 8 10 12 14 
Reading DLL Backward: 14 12 10 8 6 4 2

Method 2

This method uses class and its functions to do operations doubly linked list, we do not need to pass head explicitly every time. Since its a member of the class and is initialised at object creation.

Run

#include<iostream>
using namespace std;

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

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

void DoublyLinkedList::insertStart (int data)
{
  Node *new_node = new Node ();

  new_node->data = data;
  new_node->next = head;
  new_node->prev = NULL;

  // if DLL had already >=1 nodes
  if (head != NULL)
    head->prev = new_node;

  // changing head to this
  head = new_node;
}

void DoublyLinkedList::insertLast (int data)
{
  Node *new_node = new Node ();

  // assign data
  // since this will be the last node its next will be NULL
  new_node->data = data;
  new_node->next = NULL;

  //if we are entering the first node
  if (head == NULL)
    {
      head = new_node;
      new_node->prev = NULL;
      return;
    }

  Node *last = head;

  // traverse to the current last node
  while (last->next != NULL)
    last = last->next;

  // assign current last node's next to this new node
  last->next = new_node;
  new_node->prev = last;

  // new_node becomes the last node now
}

void DoublyLinkedList::insertAfter (int n, int data)
{
  int len = countItems ();

  // if insertion position is 0 means entering at start
  if (n == 0)
    {
      insertStart (data);
      return;
    }
  // means inserting after last item
  if (n == len)
    {
      insertLast (data);
      return;
    }

  // else insertion will happen somewhere in the middle


  if (n < 1 || len < n)
    cout << "Invalid position" << endl; else { Node *new_node = new Node (); new_node->data = data;
      new_node->next = NULL;
      new_node->prev = NULL;

      // nthNode used to traverse the Linked List
      Node *nthNode = head;

      // traverse till the nth node
      while (--n)
	{
	  nthNode = nthNode->next;
	}

      Node *nextNode = nthNode->next;	// (n+1)th node

      // assigning (n+1)th node's previous to this new node
      nextNode->prev = new_node;

      // new_node's next assigned to (n+1)th node
      new_node->next = nextNode;
      // new_node's previous assigned to nth node
      new_node->prev = nthNode;

      // assign nth node's next to new_node
      nthNode->next = new_node;
    }
}

int DoublyLinkedList::countItems ()
{

  Node *node = new Node ();
  node = head;

  int items = 0;

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

void DoublyLinkedList::display ()
{
  Node *node = head;
  Node *end = NULL;

  cout << "Reading DLL Forward: ";
  while (node != NULL)
    {
      cout << node->data << " "; end = node; node = node->next;
    }

  cout << "\nReading DLL Backward: ";

  while (end != NULL)
    {
      cout << end->data << " "; end = end->prev;
    }
  cout << "\n\n"; } int main () { DoublyLinkedList *dll = new DoublyLinkedList (); dll->insertStart (6);
  dll->insertStart (4);
  dll->insertStart (2);

  dll->display ();

  dll->insertLast (8);
  dll->insertLast (12);
  dll->insertLast (14);
  dll->display ();


  // delete 3rd node
  dll->insertAfter (3, 10);
  dll->display ();

  return 0;
}

Output

Reading DLL Forward: 2 4 6 
Reading DLL Backward: 6 4 2

Reading DLL Forward: 2 4 6 8 12 14
Reading DLL Backward: 14 12 8 6 4 2

Reading DLL Forward: 2 4 6 10 8 12 14
Reading DLL Backward: 14 12 8 10 6 4 2

Doubly Linked List deletion in C++

Let us look at all variations of the program for the same –

Method 1

Method 2

Method 1

This method uses a class to create node structure but uses general functions with the requirement of the head being passed as a parameter in each of them.

Run

#include<iostream>
#include<stdlib.h>
using namespace std;

struct Node
{
  int data;
  struct Node *next;
  struct Node *prev;
};
int countItems (struct Node *node);

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

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

  new_node->data = data;
  new_node->next = *head;
  new_node->prev = NULL;

  // If the linked list already had atleast 1 node
  if (*head != NULL)
    (*head)->prev = new_node;

  // new_node will become head
  *head = new_node;
}

void deleteStart (struct Node **head)
{
  struct Node *temp = *head;

  // if DLL is empty
  if (*head == NULL)
    {
      cout << "Linked List Empty, nothing to delete\n";
      return;
    }

  // if Linked List has only 1 node 
  if (temp->next == NULL)
    {
      cout << temp->data << " deleted\n";
      *head = NULL;
      return;
    }

  // move head to next node 
  *head = (*head)->next;
  // assign head node's previous to NULL
  (*head)->prev = NULL;

  cout << temp->data << " deleted\n";
  free (temp);
}

void deleteLast (struct Node **head)
{
  struct Node *temp = *head;

  // if DLL is empty
  if (*head == NULL)
    {
      cout << ("DLL empty can't delete\n");
      return;
    }

  // if Linked List has only 1 node 
  if (temp->next == NULL)
    {
      cout << temp->data << " deleted\n";
      *head = NULL;
      return;
    }

  // else traverse to the last node 
  while (temp->next != NULL)
    temp = temp->next;

  struct Node *secondLast = temp->prev;

  // Curr assign 2nd last node's next to Null
  secondLast->next = NULL;

  cout << temp->data << " deleted\n";
  free (temp);
}

void deleteNthNode (struct Node **head, int n)
{
  //if the head node itself needs to be deleted
  int len = countItems (*head);

  // not valid
  if (n < 1 || n > len)
    {
      cout << "Not a valid position\n";
      return;
    }

  // delete the first node 
  if (n == 1)
    {
      deleteStart (head);
      return;
    }

  if (n == len)
    {
      deleteLast (head);
      return;
    }

  struct Node *temp = *head;

  // traverse to the nth node 
  while (--n)
    {
      temp = temp->next;
    }

  struct Node *previousNode = temp->prev;	// (n-1)th node
  struct Node *nextNode = temp->next;	// (n+1)th node

  // assigning (n-1)th node's next pointer to (n+1)th node
  previousNode->next = temp->next;

  // assigning (n+1)th node's previous pointer to (n-1)th node
  nextNode->prev = temp->prev;

  // deleting nth node
  cout << temp->data << " deleted\n";
  free (temp);
}

// required for deleteNthNode 
int countItems (struct Node *node)
{

  int items = 0;
  while (node != NULL)
    {
      node = node->next;
      items++;
    }

  return items;
}

//function to print the doubly linked list
void display (struct Node *node)
{
  struct Node *end = NULL;

  cout << "Reading DLL Forward: ";
  while (node != NULL)
    {
      cout << node->data << " ";
      end = node;
      node = node->next;
    }

  cout << "\nReading DLL Backward: ";

  while (end != NULL)
    {
      cout << end->data << " ";
      end = end->prev;
    }
  cout << "\n\n";
}

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

  insert (&head, 2);
  insert (&head, 4);
  insert (&head, 8);
  insert (&head, 10);
  insert (&head, 12);
  insert (&head, 14);

  display (head);

  deleteStart (&head);
  display (head);

  deleteLast (&head);
  display (head);

  // delete 3rd node
  deleteNthNode (&head, 3);
  display (head);

  // delete 1st node
  deleteNthNode (&head, 1);
  display (head);

  // delete 1st node
  deleteLast (&head);
  display (head);

  // delete 1st node
  deleteStart (&head);
  display (head);

  return 0;
}

Output

Reading DLL Forward: 14 12 10 8 4 2 
Reading DLL Backward: 2 4 8 10 12 14 

14 deleted
Reading DLL Forward: 12 10 8 4 2 
Reading DLL Backward: 2 4 8 10 12 

2 deleted
Reading DLL Forward: 12 10 8 4 
Reading DLL Backward: 4 8 10 12 

8 deleted
Reading DLL Forward: 12 10 4 
Reading DLL Backward: 4 10 12 

12 deleted
Reading DLL Forward: 10 4 
Reading DLL Backward: 4 10 

4 deleted
Reading DLL Forward: 10 
Reading DLL Backward: 10 

10 deleted
Reading DLL Forward: 
Reading DLL Backward:

Method 2

This method uses class and its functions to do operations doubly linked list, we do not need to pass head explicitly every time. Since its member of the class and is initialised at object creation.

Run

#include<iostream>
using namespace std;

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

class DoublyLinkedList
{
private:
  Node * head;
public:
  DoublyLinkedList ()
  {				// constructor
    head = NULL;
  }
  int countItems ();
  void insert (int data);
  void deleteStart ();
  void deleteLast ();
  void deleteNthNode (int pos);
  void display ();
};

void DoublyLinkedList::insert (int data)
{
  Node *new_node = new Node ();

  new_node->data = data;
  new_node->next = head;
  new_node->prev = NULL;

  // if DLL had already >=1 nodes
  if (head != NULL)
    head->prev = new_node;

  // changing head to this
  head = new_node;
}

void DoublyLinkedList::deleteStart ()
{

  Node *temp = head;

  // if DLL is empty
  if (head == NULL)
    {
      cout << "Linked List Empty, nothing to delete\n";
      return;
    }

  // if Linked List has only 1 node 
  if (temp->next == NULL)
    {
      cout << temp->data << " deleted\n";
      head = NULL;
      return;
    }

  // move head to next node 
  head = head->next;
  // assign head node's previous to NULL
  head->prev = NULL;

  cout << temp->data << " deleted\n";
  free (temp);
}

void DoublyLinkedList::deleteLast ()
{

  Node *temp = head;

  // if DLL is empty
  if (head == NULL)
    {
      cout << ("DLL empty can't delete\n");
      return;
    }

  // if Linked List has only 1 node 
  if (temp->next == NULL)
    {
      cout << temp->data << " deleted\n";
      head = NULL;
      return;
    }				// else traverse to the last node 

  while (temp->next != NULL)
    temp = temp->next;

  Node *secondLast = temp->prev;

  // Curr assign 2nd last node's next to Null
  secondLast->next = NULL;

  cout << temp->data << " deleted\n";
  free (temp);
}

void DoublyLinkedList::deleteNthNode (int n)
{
  //if the head node itself needs to be deleted
  int len = countItems ();

  // not valid
  if (n < 1 || n > len)
    {
      cout << "Not a valid position\n";
      return;
    }

  // delete the first node 
  if (n == 1)
    {
      deleteStart ();
      return;
    }

  if (n == len)
    {
      deleteLast ();
      return;
    }

  Node *temp = head;

  // traverse to the nth node 
  while (--n)
    {
      temp = temp->next;
    }

  Node *previousNode = temp->prev;	// (n-1)th node
  Node *nextNode = temp->next;	// (n+1)th node

  // assigning (n-1)th node's next pointer to (n+1)th node
  previousNode->next = temp->next;

  // assigning (n+1)th node's previous pointer to (n-1)th node
  nextNode->prev = temp->prev;

  // deleting nth node
  cout << temp->data << " deleted\n";
  free (temp);
}

int DoublyLinkedList::countItems ()
{

  Node *node = new Node ();
  node = head;
  int items = 0;

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

void DoublyLinkedList::display ()
{

  Node *node = head;
  Node *end = NULL;

  cout << "Reading DLL Forward: ";
  while (node != NULL)
    {
      cout << node->data << " ";
      end = node;
      node = node->next;
    }

  cout << "\nReading DLL Backward: ";

  while (end != NULL)
    {
      cout << end->data << " ";
      end = end->prev;
    }
  cout << "\n\n";
}

int main ()
{
  DoublyLinkedList *dll = new DoublyLinkedList ();
  dll->insert (2);
  dll->insert (4);
  dll->insert (8);
  dll->insert (10);
  dll->insert (12);
  dll->insert (14);

  dll->display ();

  dll->deleteStart ();
  dll->display ();

  dll->deleteLast ();
  dll->display ();

  // delete 3rd node
  dll->deleteNthNode (3);
  dll->display ();

  // delete 1st node
  dll->deleteNthNode (1);
  dll->display ();

  // delete 1st node
  dll->deleteLast ();
  dll->display ();

  // delete 1st node
  dll->deleteStart ();
  dll->display ();

  return 0;
}

Output

Reading DLL Forward: 14 12 10 8 4 2 
Reading DLL Backward: 2 4 8 10 12 14 

14 deleted
Reading DLL Forward: 12 10 8 4 2 
Reading DLL Backward: 2 4 8 10 12 

2 deleted
Reading DLL Forward: 12 10 8 4 
Reading DLL Backward: 4 8 10 12 

8 deleted
Reading DLL Forward: 12 10 4 
Reading DLL Backward: 4 10 12 

12 deleted
Reading DLL Forward: 10 4 
Reading DLL Backward: 4 10 

4 deleted
Reading DLL Forward: 10 
Reading DLL Backward: 10 

10 deleted
Reading DLL Forward: 
Reading DLL Backward:

Prime Course Trailer

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