Doubly linked list in C++

In the previous post we have seen how to implement a singly linked list in C++. Let us implement doubly linked list today.

The difference between SLL and DLL is, DLL has two pointers in each node. One pointer points to next node and the other points to the previous node.

Also, we can have two external pointers - one pointer to first node of list - head and the other pointer pointing to last node of the list - tail.

So let us write structure node and class dlist.

struct node
{
    int val;
    struct node *next;
    struct node *prev;
};
class d_list
{
private:
  node * head;
  node *tail;
  
public:
   d_list(); 
   void append(int val); 
   void display();  
   void insert_beg(int n);
   node* find_node(int n); 
   bool delete_node(int n);
};

We have written a class with basic operations like append, display, find and delete etc. Two functions which are not needed when compared to linkedlist class are find_last() and find_previous(). Saves time.

Let us write constructor first. In the constructor we need to initialize two pointers - head and tail.

d_list::d_list()
{
   head = NULL;
   tail  = NULL;
}

Head and tail must be set to NULL. If we do not set, they have random values and we can not know whether the list is empty at all - empty list is recognized by head = tail = NULL.

Next let us write append function.

void d_list::append(int val)
{
    node *newnode = new node;
    newnode->val = val; 
    newnode->next = NULL;
    newnode->prev = NULL;

    if(head==NULL)
       head = newnode;
    else
    {
 tail->next = newnode;
        newnode->prev = tail;
    } 
    tail = newnode;
}

As usual we create a new node. Then we need to find last node and attach new node to last node. But that is not needed. Because we already have last node - tail.

We are linking tail to newnode. Also the newnode->prev link is set to tail. Then we set this new node as tail of the list.

What is the time complexity of append? Yes, it is O(1)!

One thing to take note here. If we add newnode to empty list(head == NULL), then the newnode will also be head of the list.

So that is the general idea. Any operation, we have to make sure we update both the links - prev and next.

Delete operation becomes easier in a doubly linked list. We need not traverse the list again for getting previous node.

Here is delete function. 

node *d_list::find_node(int num)
{
    node *temp = head;
    while(temp!=NULL && temp->val!=num)
 temp = temp->next;
    return temp;
}
 
bool d_list::delete_node(int num)
{
    node *delnd = find_node(num);
    if(delnd==NULL)
      return false;
    node *prevnode = delnd->prev;
    if(delnd==head)
    {
      /*head does not have previous node.we are deleting first node of list*/
      head = head->next;
      if(head==NULL)
 //list is empty
         head = tail = NULL;/****1****/
      else
  head->prev = NULL;       
      delete delnd;
    }else  
    { 
       prevnode->next = delnd->next;
       if(delnd==tail) 
    tail = prevnode;
       else
           delnd->next->prev=prevnode;
       delete delnd;
     }
    return true;
}

We are also taking care of updating pointers if we are deleting the head.

Also observe comment marked as 1. Here we are deleting first node and list had only one node. We delete it and list becomes empty, which means both head and tail must be set to NULL.

Here is the complete class and test program.

#include<iostream>
using namespace std;
struct node
{
    int val;
    struct node *next;
    struct node *prev;
};
class d_list
{
private:
  node * head;
  node *tail;
  
public:
   d_list(); 
   void append(int val); 
   void display();  
   void insert_beg(int n);
   node* find_node(int n); 
   bool delete_node(int n);
};
d_list::d_list()
{
   head = NULL;
   tail  = NULL;
} 
void d_list::append(int val)
{
    node *newnode = new node;
    newnode->val = val; 
    newnode->next = NULL;
    newnode->prev = NULL;

    if(head==NULL)
       head = newnode;
    else
    {
 node*last = tail;
 tail->next = newnode;
        newnode->prev = tail;
    } 
    tail = newnode;
}
node *d_list::find_node(int num)
{
    node *temp = head;
    while(temp!=NULL && temp->val!=num)
 temp = temp->next;
    return temp;
}
 
bool d_list::delete_node(int num)
{
    node *delnd = find_node(num);
    if(delnd==NULL)
      return false;
    node *prevnode = delnd->prev;
    if(delnd==head)
    {
      /*head does not have previous node.we are deleting first node of list*/
      head = head->next;
      if(head==NULL)
 //list is empty
         head = tail = NULL;
      else
  head->prev = NULL;       
      delete delnd;
    }else  
    { 
       prevnode->next = delnd->next;
       if(delnd==tail) 
    tail = prevnode;
       else
           delnd->next->prev=prevnode;
       delete delnd;
     }
    return true;
}

void d_list::insert_beg(int val)
{
    node *newnode = new node;
    newnode->val = val;
    newnode->next = NULL;
    newnode->prev = NULL;
   
    newnode->next = head;
    if(head)
 head->prev = newnode;
    else
 tail = newnode;
    head = newnode;    
}
void d_list::display( )
{
    if(head==NULL)
    {
 cout<<"list is empty\n";
        return;
    }
    cout<<"Your list is ";
    for(node*temp=head;temp!=NULL;temp = temp->next)
    {
 cout<<temp->val<<"  "; 
    }

    cout<<"Your reverse list is ";
    for(node*temp=tail;temp!=NULL;temp = temp->prev)
    {
 cout<<temp->val<<"  "; 
    }
    cout<<endl;
} 

int main()
{
   d_list l1;
   while(true)
   {
 int n;
        cout<<"Enter value (-1 to stop)";
        cin>>n;
 if(n==-1)
    break;
 l1.insert_beg(n);
   }
   l1.display();
   int n;
   cout<<"Enter a value to be added to the end of the list";
   cin>>n;
   l1.append(n);
   l1.display();
   while(true)
   {
 int n;
        cout<<"Enter value to be deleted (-1 to stop)";
        cin>>n;
        if(n==-1)
    break;
 if(l1.delete_node(n))
           cout<<"Node deleted successfully";
         else
           cout<<"Could not delete the node";
         l1.display();
    }       
}

You can download the above program from here.