Modify the Program below to be a doubly linked list and add an additional member
ID: 3629364 • Letter: M
Question
Modify the Program below to be a doubly linked list and add an additional member function to the LinkedList class to print the list in reverse order.Modify the main function to do the following:
- Read the number of values to store in the list. (Make sure the number does not exceed 20.)
- Read the numbers and store the numbers in the list.
- Display the numbers in the list in the order that the numbers were inserted on the list.
- Display the numbers in the list in the reverse order that the numbers were inserted on the list.
- Read the number of values to delete from the list from the list.
- Read each number and delete the number if it is in the list.
- Display the remaining numbers on the list in the inserted order.
- Display the remaining numbers on the list in reverse order.
Sample display while running program:
Enter the number of numbers to store in the list: 5
Enter number: 10
Enter number: 12
Enter number: 34
Enter number: 55
Enter number: 46
Inserted order:
10 12 34 55 46
Reverse order:
46 55 34 12 10
Enter the number of numbers to delete from the list: 3
Enter number: 12
Enter number: 10
Enter number: 46
Inserted order:
34 55
Reverse order:
55 34
PROGRAM
1. LinkedList.h
typedef int ElementType;
struct node
{
ElementType data;
node * next;
};
class LinkedList
{
public:
LinkedList();
bool empty(); // return true if the list is empty, otherwise return false
void InsertAtEnd(ElementType x);//insert a value x at the end
void Delete(ElementType x); //if value x is in the list, remove x
void Display();// Display the data values in the linked list
private:
node * first;//pointer to the first node in the list
};
2. LinkedList.cpp
#include "LinkedList.h"
#include <iostream>
using namespace std;
//constructor
LinkedList::LinkedList(){
first = NULL;
}
//return true if the linkedlist is empty
//otherwise returns false
bool LinkedList::empty(){
return first == NULL;
}
//inserts element at the end of the linked list
void LinkedList::InsertAtEnd(ElementType x){
//if list is empty inserts at the first
if(LinkedList::empty()) {
first = new node();
first -> data = x;
first -> next = NULL;
}
else {//inserts at the end
node* cur = first;
while(cur->next != NULL)
cur = cur->next;
node* newNode = new node();
newNode->data = x;
newNode->next = NULL;
cur->next = newNode;
}
}
//deletes specified element from the linked list
void LinkedList::Delete(ElementType x){
if(!empty()){
if(first->data == x){
node *tmp = first;
first = first->next;
delete tmp;
}
else{
node *prev = first;
node *cur = first->next;
do{
if(cur->data == x){
prev->next = cur->next;
delete cur;
break;
}
else{
prev = cur;
cur = cur->next;
}
}while(cur->next != NULL);
}
}
}
//displays the elements in the linked list
void LinkedList::Display(){
if(!LinkedList::empty()){
node *cur = first;
while(1)
{
cout<<cur->data<<" ";
if(cur->next != NULL)
cur = cur->next;
else
break;
}
cout<<endl;
}
else
cout<<"list is empty"<<endl;
}
3. main.cpp
#include <iostream>
#include "LinkedList.h"
using namespace std;
//Main function
int main()
{
LinkedList list;
int size;
int number;
cout<<"Enter the number of numbers to store in the list: ";
cin >> size;
//Input validation
while(size>20)
{
cout << "Invalid Size: "<<size<<", Size shouldn't be exceed 20, Enter again: ";
cin >> size;
}//End of while
//Reading elements
for(int i=0;i<size;i++) {
cout<<"Enter number: ";
cin >>number;
list.InsertAtEnd(number);
list.Display();
}//End of for
cout << "Enter the number of numbers to delete from the list:";
cin >> size;
//Reading elements to remove
for(int i=0;i<size;i++) {
cout<<"Enter number: ";
cin >>number;
list.Delete(number);
list.Display();
}//End of for
system("pause");
return 0;
}//End of main
Explanation / Answer
1. LinkedList.h
typedef int ElementType;
struct node
{
ElementType data;
node * next;
};
class LinkedList
{
public:
LinkedList();
bool empty(); // return true if the list is empty, otherwise return false
void InsertAtEnd(ElementType x);//insert a value x at the end
void reverseprint();//display lis in reverse
void Delete(ElementType x); //if value x is in the list, remove x
void Display();// Display the data values in the linked list
private:
node * first;//pointer to the first node in the list
};
2. LinkedList.cpp
#include "LinkedList.h"
#include <iostream>
using namespace std;
////constructor
LinkedList::LinkedList(){
first = NULL;
}
//return true if the linkedlist is empty
//otherwise returns false
bool LinkedList::empty(){
return first == NULL;
}
//inserts element at the end of the linked list
void LinkedList::InsertAtEnd(ElementType x){
//if list is empty inserts at the first
if(LinkedList::empty()) {
first = new node();
first -> data = x;
first -> next = NULL;
}
else {//inserts at the end
node* cur = first;
while(cur->next != NULL)
cur = cur->next;
node* newNode = new node();
newNode->data = x;
newNode->next = NULL;
cur->next = newNode;
}
}
void LinkedList::reverseprint() const
{
nodeType<Type> *current;
current = lat;
while(current != NULL)
{
cout<<current->info<<" ";
current = current->back;
}
}
//deletes specified element from the linked list
void LinkedList::Delete(ElementType x){
if(!empty()){
if(first->data == x){
node *tmp = first;
first = first->next;
delete tmp;
}
else{
node *prev = first;
node *cur = first->next;
do{
if(cur->data == x){
prev->next = cur->next;
delete cur;
break;
}
else{
prev = cur;
cur = cur->next;
}
}while(cur->next != NULL);
}
}
}
//displays the elements in the linked list
void LinkedList::Display(){
if(!LinkedList::empty()){
node *cur = first;
while(1)
{
cout<<cur->data<<" ";
if(cur->next != NULL)
cur = cur->next;
else
break;
}
cout<<endl;
}
else
cout<<"list is empty"<<endl;
}
3. main.cpp
#include <iostream>
#include "LinkedList.h"
using namespace std;
////Main function
int main()
{
LinkedList list;
int size;
int number;
cout<<"Enter the number of numbers to store in the list: ";
cin >> size;
//Input validation
while(size>20)
{
cout << "Invalid Size: "<<size<<", Size shouldn't be exceed 20, Enter again: ";
cin >> size;
}//End of while
//Reading elements
for(int i=0;i<size;i++) {
cout<<"Enter number: ";
cin >>number;
list.InsertAtEnd(number);
list.reverseprint();
list.Display();
}//End of for
cout << "Enter the number of numbers to delete from the list:";
cin >> size;
//Reading elements to remove
for(int i=0;i<size;i++) {
cout<<"Enter number: ";
cin >>number;
list.Delete(number);
list.Display();
}//End of for
system("pause");
return 0;
}//End of main
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.