Q) Modify the class Linked List below to make it a Doubly Linked List. Name your
ID: 3881314 • Letter: Q
Question
Q) Modify the class Linked List below to make it a Doubly Linked List. Name your class DoublyLinkedList. Add a method addEnd to add an integer at the end of the list and a method displayInReverse to print the list backwards.
void addEnd(int x): create this method to add x to the end of the list.
void displayInReverse(): create this method to display the list elements from the last item to the first one.
Create a main() function to test your DoublyLinkedList class.
LinkedList.cpp
/*******************************
* Week 2 lesson: *
* a simple LinkedList class *
*******************************/
#include <iostream>
#include "LinkedList.h"
using namespace std;
/*
* Initializes the list to empty creating a dummy header node.
*/
LinkedList::LinkedList()
{
first = new Node;
first->next = NULL;
}
/*
* Destructor. Deallocates all the nodes of the linked list,
* including the header node.
*/
LinkedList::~LinkedList()
{
Node *temp;
while (first != NULL)
{
temp=first;
first=first->next;
delete temp;
}
}
/*
* Determines whether the list is empty.
*
* Returns true if the list is empty, false otherwise.
*/
bool LinkedList::isEmpty()
{
return first->next == NULL;
}
/*
* Prints the list elements.
*/
void LinkedList::display()
{
Node * current = first->next;
while(current != NULL)
{
cout << current->info << " ";
current = current->next;
}
cout << endl;
}
/*
* Adds the element x to the beginning of the list.
*
* x: element to be added to the list.
*/
void LinkedList::add(int x)
{
Node *p = new Node;
p->info = x;
p->next = first->next;
first->next = p;
}
/*
* Removes the first occurrence of x from the list. If x is not found,
* the list remains unchanged.
*
* x: element to be removed from the list.
*/
void LinkedList::remove(int x)
{
Node * old = first->next,
* p = first;
//Finding the address of the node before the one to be deleted
bool found = false;
while (old != NULL && !found)
{
if (old->info == x) found = true;
else
{
p = old;
old = p->next;
}
}
//if x is in the list, remove it.
if (found)
{
p->next = old->next;
delete old;
}
}
main.cpp
/*******************************
* Week 2 lesson: *
* a simple LinkedList class *
*******************************/
#include <iostream>
#include "LinkedList.h"
using namespace std;
int main()
{
LinkedList myList;
int x;
//Add 5 random numbers to list
for (int i=0; i < 5; i++)
myList.add(rand()%20);
cout << "1 - Display the list elements" << endl;
cout << "2 - Is it empty?" << endl;
cout << "3 - Add element" << endl;
cout << "4 - Delete element" << endl;
cout << "5 - Exit" << endl;
int option;
//Loop to test the LinkedList class methods
do
{
cout << endl << "Enter your choice: ";
cin >> option;
switch(option)
{
case 1:
cout << "List elements: ";
myList.display();
break;
case 2:
if (myList.isEmpty()) cout << "List is empty"<< endl;
else cout << "List is not empty" << endl;
break;
case 3:
cout << "Enter an element to add at the beginning of the list: ";
cin >> x;
myList.add(x);
break;
case 4:
cout << "Enter an element to delete from the list: ";
cin >> x;
myList.remove(x);
break;
case 5:
cout << "All done!" << endl;
break;
default: cout << "Invalid choice!" << endl;
}
} while (option != 5);
return 0;
}
LinkedList.h
/*******************************
* Week 2 lesson: *
* a simple LinkedList class *
*******************************/
/*
* Linked list node.
*/
struct Node
{
int info; //element stored in this node
Node *next; //link to next node
};
/*
* Class implementing a linked list.
*/
class LinkedList
{
public:
LinkedList();
~LinkedList();
bool isEmpty();
void display();
void add(int);
void remove(int);
private:
Node *first; //pointer to header (dummy) node
};
Explanation / Answer
PLEASE REFER BELOW CODE
1) LinkedList.h
#include<iostream>
using namespace std;
//Node for doubly linked list
struct Node
{
int value;
Node *N,*P;
Node(int y)
{
value = y;
N=P=NULL;
}
};
//DoublyLinkedList class
class DoublyLinkedList
{
Node *front;
Node *back;
public:
DoublyLinkedList(); //constructor to initialize list
~DoublyLinkedList(); //destructor to delete list
void addEnd(int x);
void displayInReverse(); //display node in revesre
void destroyList(); //delete linked list
};
2) LInkedList.cpp
#include "LinkedList.h"
DoublyLinkedList::DoublyLinkedList()
{
//initialize both pointer to NULL
front = NULL;
back = NULL;
}
void DoublyLinkedList::addEnd(int x)
{
//creating node
Node *n = new Node(x);
//if back is NULL then update both front and back
if( back == NULL)
{
front = n;
back = n;
}
else //add at back
{
back->N = n;
n->P = back;
back = n;
}
}
void DoublyLinkedList::displayInReverse()
{
Node *temp = back; //initialize temp pointer to back
cout << " Nodes in reverse order :" << endl;
while(temp != NULL)
{
cout << temp->value << " " ;
temp = temp->P;
}
}
void DoublyLinkedList::destroyList()
{
Node *T = back; //delete from back
while(T != NULL)
{
Node *T2 = T;
T = T->P;
delete T2;
}
front = NULL;
back = NULL;
}
DoublyLinkedList::~DoublyLinkedList()
{
destroyList();
}
3) main.cpp
#include"LinkedList.h"
int main()
{
DoublyLinkedList myList;
int x;
cout << "1 - Display the list elements" << endl;
cout << "2 - Add element at end" << endl;
cout << "3 - Exit" << endl;
int option;
//Loop to test the DoublyLinkedList class methods
do
{
cout << endl << "Enter your choice: ";
cin >> option;
switch(option)
{
case 1:
myList.displayInReverse();
break;
case 2:
cout << "Enter an element to add at the beginning of the list: ";
cin >> x;
myList.addEnd(x);
break;
case 3:
cout << "All done!" << endl;
break;
default:
cout << "Invalid choice!" << endl;
}
}while (option != 3);
return 0;
}
PLEASE REFER BELOW OUTPUT
khushal@khushal-ubuntu:~/Desktop/Chegg/Doubly_linked_list$ g++ -o main main.cpp LinkedList.cpp
khushal@khushal-ubuntu:~/Desktop/Chegg/Doubly_linked_list$ ./main
1 - Display the list elements
2 - Add element at end
3 - Exit
Enter your choice: 2
Enter an element to add at the beginning of the list: 23
Enter your choice: 2
Enter an element to add at the beginning of the list: 45
Enter your choice: 2
Enter an element to add at the beginning of the list: 89
Enter your choice: 2
Enter an element to add at the beginning of the list: 78
Enter your choice: 1
Nodes in reverse order :
78 89 45 23
Enter your choice: 3
All done!
khushal@khushal-ubuntu:~/Desktop/Chegg/Doubly_linked_list$
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.