In C++ please Implement a class for doubly linked list. Your doubly linked list should have...

Question

Question

In C++ please Implement a class for doubly linked list. Your doubly linked list should have...

In C++ please

Implement a class for doubly linked list. Your doubly linked list should have following members:

- A head pointer

- A tail pointer

- Function: insert at head

-Function: insert at tail

- Function: delete a node

- Function: search a node

- Function: traverse

- Function: reverse traverse

Test your implementation by calling member functions inside main.

Engineering Computer-Science

0 0

Add a comment Transcribed image text

Answer 1

Answer #1

#include<iostream>
#include<cstdio>
#include<cstdlib>
/*
* Node Declaration
*/
using namespace std;
struct node
{
int info;
struct node *next;
struct node *prev;
}*head,*tail;//head and tail pointers

/*
Class Declaration
*/
class double_llist
{
public:
void create_list(int value);
void insert_At_head(int value);
void insert_At_tail(int value);
void delete_node(int value);
    int search_node(int value);
void traverse();
void reverse_traverse();;
double_llist()
{
head = tail=NULL;
}
};

/*
* Main: Conatins Menu
*/
int main()
{
int choice, element, position;
double_llist dl;
while (1)
{
cout<<endl<<"----------------------------"<<endl;
cout<<endl<<"Operations on Doubly linked list"<<endl;
cout<<endl<<"----------------------------"<<endl;
cout<<"1.Create Node"<<endl;
cout<<"2.Add at head"<<endl;
cout<<"3.Add at tail"<<endl;
cout<<"4.Delete"<<endl;
cout<<"5.Traverse"<<endl;
cout<<"6.Reverse_traverse"<<endl;
cout<<"7.Search"<<endl;
cout<<"8.Quit"<<endl;
cout<<"Enter your choice : ";
cin>>choice;
switch ( choice )
{
case 1:
cout<<"Enter the element: ";
cin>>element;
dl.create_list(element);
cout<<endl;
break;
case 2:
cout<<"Enter the element: ";
cin>>element;
dl.insert_At_head(element);
cout<<endl;
break;
case 3:
cout<<"Enter the element: ";
cin>>element;
dl.insert_At_tail(element);
cout<<endl;
break;
case 4:
if (head == NULL)
{
cout<<"List empty,nothing to delete"<<endl;
break;
}
cout<<"Enter the element for deletion: ";
cin>>element;
dl.delete_node(element);
cout<<endl;
break;
case 5:
dl.traverse();
cout<<endl;
break;
case 6:
dl.reverse_traverse();
break;
case 7:
           cout<<"Enter element to search:";
           cin>>element;
if( dl.search_node(element)==1)cout<<"Found\n";
else cout<<"Not Found\n";
cout<<endl;
break;
case 8:
exit(1);
default:
cout<<"Wrong choice"<<endl;
}
}
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;
temp->prev = NULL;
head = temp;

tail = head;
}

/*
* Insertion at the beginning
*/
void double_llist::insert_At_head(int value)
{
if (head == NULL)
{
cout<<"First Create the list."<<endl;
return;
}
struct node *temp;
temp = new(struct node);
temp->prev = NULL;
temp->info = value;
temp->next = head;
head->prev = temp;
head = temp;
cout<<"Element Inserted"<<endl;
}

/*
* Insertion of element at a tail
*/
void double_llist::insert_At_tail(int value)
{
if (head == NULL)
{
cout<<"First Create the list."<<endl;
return;
}
struct node *temp = new (struct node);
temp->prev=tail;
temp->next=NULL;
temp->info=value;
tail->next=temp;
tail=temp;
cout<<"Element Inserted"<<endl;
}

/*
* Deletion of element from the list
*/
void double_llist::delete_node(int value)
{
struct node *tmp, *q;
/*first element deletion*/
if (head->info == value)
{
tmp = head;
head = head->next;
head->prev = NULL;
cout<<"Element Deleted"<<endl;
free(tmp);
return;
}
//if tail node
if(tail->info==value)
{
       tmp=tail;
       tail=tail->prev;
       tail->next=NULL;
       cout<<"Element Deleted"<<endl;
       free(tmp);
       return ;
   }
q = head;
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::traverse()
{
struct node *q;
if (head == NULL)
{
cout<<"List empty,nothing to display"<<endl;
return;
}
q = head;
cout<<"The Doubly Link List is :"<<endl;
while (q != NULL)
{
cout<<q->info<<" <-> ";
q = q->next;
}
cout<<"NULL"<<endl;
}

/*
* Number of elements in Doubly Link List
*/
void double_llist::reverse_traverse()
{
struct node *q = tail;
int cnt = 0;
while (q != NULL)
{cout<<q->info<<" ";
q = q->prev;

}
cout<<endl;

}
int double_llist::search_node(int value)
{
   struct node *q = tail;

while (q != NULL)
{
       if(q->info==value)return 1;//if found
q = q->prev;

}
return 0;//if not found

}

output

----------------------------