Monday, 11 September 2017

Implementation of doubly linked list in c++

In Singly Linked List (SLL), each node provides information  about where the next node is. It has no knowledge about where the previous node is. For example, if we are at the ith node in the linked list currently, then to access the (i-1)th node or (i-2)th node, we have to traverse the list right from the first node. In addition, it is not possible to delete the ith node given only a pointer to the ith node. It is also not possible to insert a node before the ith node given only a pointer to the ith node. For handling such difficulties, we can use Doubly Linked List (DLLs) where each node contains two links, one to its predecessor and other to its successor.
In a doubly linked list, each node has two links fields to store information about the one to the next and also about the one ahead of the node. Hence, each node has knowledge of its successor and also its predecessor. 
Each node of a Doubly Linked List has three fields in general but must have at least two linked list and one data part for storing information in it.
Doubly Linked List may either be linear or circular and it may or may not contain a header node. Doubly Linked List are also known as two-way linked list.   

Implementation of doubly linked list in c++:

// header files for the program implementation #include <iostream>
using namespace std;

// node structure of the Doubly Linked List with two link field and one data field

struct node
{
    int info;
    struct node *next;
    struct node *prev;
}*start;


The creation of the Doubly Linked List has the same procedure as that of the singly linked list, the only difference is that each node must be linked to both its predecessor and successor. Below is the Class declaration of Doubly Linked List with its different functions.

class double_llist
{
    public:
        void create_list(int value);
        void add_begin(int value);
        void add_after(int value, int position);
        void delete_element(int value);
        void display_dlist();
                double_llist()
        {
            start = NULL; 
        }
};




// definition of the create_list function of Doubly Linked List

void double_llist::create_list(int value)
{
    struct node *s, *temp;
    temp = new(struct node);
    temp->info = value;
    temp->next = NULL;
    if (start == NULL)
    {
        temp->prev = NULL;
        start = temp;
    }
    else
    {
        s = start;
        while (s->next != NULL)
            s = s->next;
        s->next = temp;
        temp->prev = s;
    }
}


Below is the definition of the function by which new node is inserted at head position of the Doubly Linked List.


void double_llist::add_begin(int value)
{
    if (start == NULL)
    {
        cout<<"First Create the list."<<endl;
        return;
    }
    struct node *temp;
    temp = new(struct node);
    temp->prev = NULL;
    temp->info = value;
    temp->next = start;
    start->prev = temp;
    start = temp;  
}


//definition of the function by which new node is inserted at specific position of the Doubly Linked List


void double_llist::add_after(int value, int pos)
{
    if (start == NULL)
    {
        cout<<"First Create the list."<<endl;
    }
    struct node *tmp, *q;
    int i;
    q = start;
    for (i = 0;i < pos - 1;i++)
    {
        q = q->next;
        if (q == NULL)
        {
            cout<<"There are less than ";
            cout<<pos<<" elements."<<endl;
        }
    }
    tmp = new(struct node);
    tmp->info = value;
    if (q->next == NULL)
    {
        q->next = tmp;
        tmp->next = NULL;
        tmp->prev = q;     
    }
    else
    {
        tmp->next = q->next;
        tmp->next->prev = tmp;
        q->next = tmp;
        tmp->prev = q;
    }
}



Deleting from the Doubly Linked List needs the deleted node's predecessor, if any, to be pointed to the deleted node's  successor. In addition, if any, should be set to point to the predecessor node. Below is the definition of the function by which node is deleted from Doubly Linked List.


void double_llist::delete_element(int value)
{
    
struct node *tmp, *q;

    if (start->info == value)
    {
        tmp = start;
        start = start->next;  
        start->prev = NULL;
        free(tmp);
    }
    q = start;
    while (q->next->next != NULL)
    {   
        if (q->next->info == value)  
        {
            tmp = q->next;
            q->next = tmp->next;
            tmp->next->prev = q;
            free(tmp);
        }
        q = q->next;
    }


// definition of the function by which node are displayed from Doubly Linked List

void double_llist::display_dlist()
{
    struct node *q;
    if (start == NULL)
    {
        cout<<"List empty,nothing to display"<<endl;
    }
    q = start;
    cout<<"The Doubly Link List is :"<<endl;
    while (q != NULL)
    {
        cout<<q->info<<"\t";
        q = q->next;
    }
    cout<<"NULL"<<endl;
}


// implementation of main function with different function calls.

int main() 

{
    int choice, element, position;
    double_llist dl;
    for(int i=0;i<5;i++)
          {
            cin>>element;
            dl.create_list(element);
            cout<<endl;
           }
            dl.display_dlist();
            cout<<endl;
            dl.add_begin(0);
            cout<<endl;
             dl.display_dlist();
            cout<<endl;
            dl.add_after(7, 3);
            cout<<endl;
             dl.display_dlist();
            cout<<endl;       
            dl.delete_element(3);
            cout<<endl;
             dl.display_dlist();
            cout<<endl;
            return 0;
}



Thanks
Mukesh Rajput

No comments:

Post a Comment

Thanks
Mukesh Rajput