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

};

Answer 1

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 << "\n\nNodes 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$