Question

C++ 

Implement a class called DoublyLinkedList. In the main function, instantiate the DoublyLinkedList class and make sure that there is a user loop and a menu so that the user can access all the list operators. You should implement the following operators, and any others that you may deem best. DestroyList InitializeList GetFirst InsertFirst, InsertLast, Insert DeleteFirst, DeleteLast, Delete IsEmpty Length Print, ReversePrint

Answer 1

Hi,

Please find the code below.

Below program illustrates doubly linked list in c++ and differnet operations on the same.

#include
#include
#include
using namespace std;

struct Node
{
int element;
struct Node* next;
struct Node* prev;
};
struct Node* head;
struct Node* tail;

void initialisePointers()
{
head=NULL;
tail=NULL;
}

void insertToStartOfList(int input)
{
struct Node* newNode;
newNode=new Node;
if(head==NULL)
{
head=newNode;
newNode->prev=NULL;
newNode->element=input;
newNode->next=NULL;
tail=newNode;
}
else
{
newNode->next=head;
newNode->element=input;
newNode->prev=NULL;
head->prev=newNode;
head=newNode;
}
}

void insertToLastOfList(int input)
{
struct Node* newNode;
newNode=new Node;
newNode->element=input;
if(head==NULL)
{
head=newNode;
newNode->prev=NULL;
newNode->next=NULL;
tail=newNode;
}
else
{
newNode->prev=tail;
tail->next=newNode;
newNode->next=NULL;
tail=newNode;
}
}

void insertAfterGivenNumber(int old, int element)
{
struct Node* newNode;
newNode=new Node;
struct Node* temp;
temp=head;
if(head==NULL)
{
cout<<"could not insert"<<endl;
return;
}
if(head==tail)
{
if(head->element!=old)
{
cout<<"could not insert"<<endl;
return;
}
newNode->element=element;
head->next=newNode;
newNode->next=NULL;
head->prev=NULL;
newNode->prev=head;
tail=newNode;
return;
}
if(tail->element==element)
{
newNode->next=NULL;
newNode->prev=tail;
tail->next=newNode;
tail=newNode;
return;
}
while(temp->element!=old)
{
temp=temp->next;
if(temp==NULL)
{
cout<<"Could not insert"<<endl;
cout<<"element not found"<<endl;
return;
}
}

newNode->next=temp->next;
newNode->prev=temp;
newNode->element=element;
temp->next->prev=newNode;
temp->next=newNode;
}

void deleteAtFirstPosition()
{
if(head==NULL)
{
return;
}
if(head==tail)///one element in the list
{
struct Node* cur;
cur=head;
head=NULL;
tail=NULL;
delete cur;
return;
}
else
{
struct Node* cur;
cur=head;
head=head->next;
head->prev=NULL;
delete cur;
}
}

void deleteAtLastPosition()
{
if(head==NULL) return;
if(head==tail)
{
struct Node* cur;
cur=head;
head=NULL;
tail=NULL;
delete cur;
return;
}
else
{
struct Node* cur;
cur=tail;
tail=tail->prev;
tail->next=NULL;
delete cur;
}
}
void deleteGivenElement(int input)
{
struct Node* temp;
temp=head;
if(head==tail)
{
if(head->element!=input)
{
cout<<"could not delete"<<endl;
return;
}
head=NULL;
tail=NULL;
delete temp;
return;
}
if(head->element==input)
{
head=head->next;
head->prev=NULL;
delete temp;
return;
}
else if(tail->element==input)
{
temp=tail;
tail=tail->prev;
tail->next=NULL;
delete temp;
return;
}
while(temp->element!=input)
{
temp=temp->next;
if(temp==NULL)
{
cout<<"given integer not found"<<endl;
return;
}
}
temp->next->prev=temp->prev;
temp->prev->next=temp->next;
delete temp;
}

void isListEmpty()
{
struct Node* temp;
temp=head;
if(temp == NULL)
{
cout << "List is empty" << endl;
}
else
{
cout << "List is not empty" << endl;
}
}

void LengthOfList()
{
int length = 0;
struct Node* temp;
temp=head;
while(temp!=NULL)
{
length++;
temp=temp->next;
}
cout << " The length of the list is :" << length << endl;
}

void displayList()
{
struct Node* temp;
temp=head;
while(temp!=NULL)
{
printf("%d->",temp->element);
temp=temp->next;
}
puts("");
}

void printReverseOrder()
{
struct Node* temp;
temp=tail;
while(temp!=NULL)
{
cout<element<<"->";
temp=temp->prev;
}
cout<<endl;
}

int main()
{
initialisePointers();

int choiceFromUser;
while(1)
{
printf("1.InsertFirst 2. InsertLast 3. InsertAfter 4.DeleteFirst 5. DeleteLast\n");
printf("6. PrintCompleteList 7. ReversePrintList 8. deleteGivenElement \n");
printf("9. IsEmpty 10.LengthOfList 12. Exit \n");
cin>>choiceFromUser;
if(choiceFromUser==1)
{
int input;
cout<<"Enter Integer element to be inserted into DLL(at start) - ";
cin>>input;
insertToStartOfList(input);
displayList();
}
else if(choiceFromUser==2)
{
int input;
cout<<"Enter Integer element to be inserted into DLL(at last) -";
cin>>input;
insertToLastOfList(input);
displayList();
}
else if(choiceFromUser==3)
{
int oldNumber,newNumber;
cout<<"Enter Old number after which you would like to insert element - ";
cin>>oldNumber;
cout<<"Enter New number you want to insert -";
cin>>newNumber;
insertAfterGivenNumber(oldNumber,newNumber);
displayList();
}
else if(choiceFromUser==4)
{
deleteAtFirstPosition();
displayList();
}
else if(choiceFromUser==5)
{
deleteAtLastPosition();
displayList();
}
else if(choiceFromUser==6)
{
displayList();
}
else if(choiceFromUser==7)
{
printReverseOrder();
}
else if(choiceFromUser==8)
{
int element;
cin>>element;
deleteGivenElement(element);
displayList();
}
else if(choiceFromUser==9)
{
cout << "Checking if list is empty" << endl;
isListEmpty();
}
else if(choiceFromUser==10)
{
cout << "Printing length of the list" << endl;
LengthOfList();
}
else if(choiceFromUser==11)
{
break;
}
  
}
return 0;
}

Outputs attached: