Question

Using the singly linked list code as a base, create a class that implements a doubly linked list. A doubly linked list has a Previous link so you can move backwards in the list. Be sure the class is a template class so the user can create a list with any data type. Be sure to test all the member functions in your test program. c++

Answer 1

#include<iostream>
#include<cstdio>
#include<cstdlib>
/*
 * Node Declaration
 */
using namespace std;
struct node
{
    int info;
    struct node *next;
    struct node *prev;
}*start;
 
/*
 Class Declaration 
 */
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 search_element(int value);
        void display_dlist();
        double_llist()
        {
            start = NULL;  
        }
};
 
/*
 * Main: 
 */
int main()
{
    int choice, element,element2,elemDelete, position;
    double_llist dl;
    cout<<endl<<"---------------Doubly Linked List-------------"<<endl;
    cout<<"Enter the element to be inserted: ";
    cin>>element;
    dl.create_list(element);
        dl.display_dlist();
    dl.add_begin(element);
        dl.display_dlist();
    
    cout<<"Enter the element to be inserted after a position: ";
    cin>>element2;
    cout<<"Insert Element after position: ";
    cin>>position;
    dl.add_after(element2, position);
    cout<<"Enter the element to be deleted: ";
    cin>>elemDelete;
    dl.delete_element(elemDelete);
    dl.display_dlist();

    return 0;
}
 
/*
 * Create Double Link 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;
    }
}
 
/*
 * Insertion at the beginning
 */
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;
    cout<<"Element Inserted"<<endl;
}
 
/*
 * Insertion of element at a particular position
 */
void double_llist::add_after(int value, int pos)
{
    if (start == NULL)
    {
        cout<<"First Create the list."<<endl;
        return;
    }
    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;
            return;
        }
    }
    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;
    }
    cout<<"Element Inserted"<<endl;
}
 
/*
 * Deletion of element from the list
 */
void double_llist::delete_element(int value)
{
    struct node *tmp, *q;
     /*first element deletion*/
    if (start->info == value)
    {
        tmp = start;
        start = start->next;  
        start->prev = NULL;
        cout<<"Element Deleted"<<endl;
        free(tmp);
        return;
    }
    q = start;
    while (q->next->next != NULL)
    {   
        /*Element deleted in between*/
        if (q->next->info == value)  
        {
            tmp = q->next;
            q->next = tmp->next;
            tmp->next->prev = q;
            cout<<"Element Deleted"<<endl;
            free(tmp);
            return;
        }
        q = q->next;
    }
     /*last element deleted*/
    if (q->next->info == value)    
    {   
        tmp = q->next;
        free(tmp);
        q->next = NULL;
        cout<<"Element Deleted"<<endl;
        return;
    }
    cout<<"Element "<<value<<" not found"<<endl;
}
 
/*
 * Display elements of Doubly Link List
 */
void double_llist::display_dlist()
{
    struct node *q;
    if (start == NULL)
    {
        cout<<"List empty,nothing to display"<<endl;
        return;
    }
    q = start;
    cout<<"The Doubly Link List is :"<<endl;
    while (q != NULL)
    {
        cout<<q->info<<" <-> ";
        q = q->next;
    }
    cout<<"NULL"<<endl;
}

In the above program, the structure node forms the doubly linked list node. It contains the info(data) and a pointer to the next and previous linked list node. This is given as follows.

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

The function create_list() inserts the data into the doubly linked list. It creates a newnode and inserts the number in the data field of the newnode. Then the prev pointer in newnode points to NULL as it is entered at the beginning and the next pointer points to the head. If the head is not NULL then prev pointer of head points to newnode.

The function add_begin() inserts the data into the beginning of the doubly linked list. It creates a newnode and inserts the number in the data field of the newnode. Then the prev pointer in newnode points to NULL as it is entered at the beginning and the next pointer points to the head. If the head is not NULL then prev pointer of head points to newnode.

The function add_after() inserts the data at the specified position of the doubly linked list.

The function delete_element() deletes the data from doubly linked list.

The function display_dlist() display the data of the doubly linked list.

OUTPUT :

*******************PLEASE UPVOTE*******************