Program for Doubly Linked Lists in C++ and Algorithm

A doubly Linked list is a special type of linked list where the nodes contain three fields i.e one data field and two link fields . The data Field contains the data element and the two link fields contains two pointers i.e prev and next . The pointer prev points to the previous node or points to a NULL value if it is the first node in the list . The pointer next points to the next node or points to a NULL value of it is the last node in the list .

Advantages of Doubly Linked List :

1. The Main advantage of using double linked list is that , the list can be traversed in forward as well as backward direction . 
2. Linked List can be easily reversed when compared to Single Linked List .
3. We can traverse to any node in a Doubly linked list But in Single Linkedlist previous node cannot be reached .

Also check : Program for Queue in C++

Disadvantages of Doubly Linked List :

1. It takes more space in Doubly Linked List than in Single Linked list because of an extra pointer .

Double Linked List can be Implemented in similar way as Single Linked List . Operations involved in Doubly Linked List are :
1. Insertion
2. Deletion 
3. Searching 

Insertion :

Insertion operation in a Double Linked List refers to Inserting an element  Following cases arise while performing Insertion in a Doubly Linked List .

• Inserting an element when Doubly Linked List is empty .
• Insertion at beginning of the Doubly Linked List .
• Insertion at the end of Double Linked List .
• Inserting an element in between the last and first nodes .

Deletion :

Deletion operation in a Doubly Linked List refers to Deleting an element permanently from the List . Following cases arise when deleting an element in Double linked list .

• If the List is empty - Underflow Exception
• Deleting a node which is at end of the Doubly Linked list 
• Deleting other nodes in between first node and Last of the Double Linked List .

Also check : Program for Heap sort

Program for Doubly Linked List in C++

#include<iostream>
using namespace std;
template <class T>
class doublylinkedlist
{
private :
    struct node
    {
        T data;
        node *prev;
        node *next;
    };
    node *head;
    node *tail;
public :
    doublylinkedlist()
    {
        head=tail=NULL;
    }
    void createlist(T[] , int);
    void insertfirst(T);
    void insertlast(T);
    void insertafter(T,T);
    void deletenode(T);
    void displayforward();
    void displaybackward();
};
//creating doubly linked list
template<class T>
void doublylinkedlist<T>::createlist(T x[], int n)
{
    node *q;
    node *p=new node;   //create first node
    p->data=x[0];
    p->next=NULL;
    p->prev=NULL;
    for(int i=1;i<n;i++)
    {
        q=p;
        p=p->next=new node;
        p->data=x[i];
        p->next=NULL;
        p->prev=q;
    }
    tail=p;
}
// Inserting new node at start of doubly linked list
template<class T>
void doublylinkedlist<T>::insertfirst(T item)
{
    node *p=new node;
    p->data=item;
    p->prev=NULL;
    head->prev=p;
}
//Inserting new node at last of Double Linkedlist
template<class T>
void doublylinkedlist<T>::insertlast(T item)
{
    node *p=new node;
    p->data=item;
    p->prev=tail;
    p->next=NULL;
    tail=p;
}
//Insert item after key
template<class T>
void doublylinkedlist<T>::insertafter(T item,T key)
{
    node *q=head;
    while(q!=NULL)
    {
        if(q->data==key)
            break;
        q=q->next;
    }
    if(q==NULL)
    {
        cout<<key<<"key  not found"<<endl;
        return;
    }
    node *p=new node;
    p->data=item;
    p->next=q->next;
    p->prev=q;
    q->next=p;
}
//deleting item from double linked lisr
template<class T>
void doublylinkedlist<T>::deletenode(T item)
{
    if(head==NULL)
    {
        cout<<"List is empty"<<endl;
        return;
    }
    if(head->data==item)
    {
        head=head->next;
        head->prev=NULL;
        return;
    }
    if(tail->data==item)
    {
        tail=tail->prev;
        tail->next=NULL;
        return;
    }
    node *p=head->next;
    while(p!=NULL)
    {
        if(p->data==item)
            break;
        p=p->next;
    }
    if(p==NULL)
    {
        cout<<item<<"not found "<<endl;
        return;
    }
    (p->prev)->next=p->next;
    (p->next)->prev=p->prev;
    return;
}
//diaplaying list elements in forward direction
template<class T>
void doublylinkedlist<T>::displayforward()
{
    node *p=head;
    cout<<"\n Doubly linked list (Forward)";
    while(p!=NULL)
    {
        cout<<p->data<<"";
        p=p->next;
    }
}
//displaying list elements in reverse direction
template<class T>
void doublylinkedlist<T>::displaybackward()
{
    node *p=tail;
    cout<<"\n Doubly linked list (Backward)";
    while(p!=NULL)
    {
        cout<<p->data<<"";
        p=p->prev;
    }
}
int main()
{
    int x[2]={33,44};
    doublylinkedlist<int> dlist;
    dlist.createlist(x,2);
    dlist.displayforward();
    dlist.displaybackward();
    dlist.insertfirst(22);
    dlist.displayforward();
    dlist.displaybackward();
    dlist.insertlast(55);
    dlist.displayforward();
    dlist.displaybackward();
    dlist.insertafter(66,33);
    dlist.displayforward();
    dlist.displaybackward();
    dlist.deletenode(22);
    dlist.displayforward();
    dlist.displaybackward();
    dlist.deletenode(55);
    dlist.displayforward();
    dlist.displaybackward();
    dlist.deletenode(66);
    dlist.displayforward();
    dlist.displaybackward();
    return 0;
}

Program for doubly Linked list is lengthy . Download source code for Doubly Linked list program .
Also check : Program for Binary search 

Final words :

If I have missed anything please get it to me through comments . Also share your code , logic through comments .