Write a program to test various operations of the class doublyLinkedList. Just n
ID: 3720027 • Letter: W
Question
Write a program to test various operations of the class doublyLinkedList.
Just need the main.cpp coded
please do not add more to the tabs/classes
c++
output must match results on the bottom right.
is already written and will be after the picture.
doublyLinkedList.h
#ifndef H_doublyLinkedList
#define H_doublyLinkedList
#include <iostream>
#include <cassert>
using namespace std;
//Definition of the node
template <class Type>
struct nodeType
{
Type info;
nodeType<Type> *next;
nodeType<Type> *back;
};
template <class Type>
class doublyLinkedList
{
public:
const doublyLinkedList<Type>& operator=
(const doublyLinkedList<Type> &);
//Overload the assignment operator.
void initializeList();
//Function to initialize the list to an empty state.
//Postcondition: first = nullptr; last = nullptr; count = 0;
bool isEmptyList() const;
//Function to determine whether the list is empty.
//Postcondition: Returns true if the list is empty,
// otherwise returns false.
void destroy();
//Function to delete all the nodes from the list.
//Postcondition: first = nullptr; last = nullptr; count = 0;
void print() const;
//Function to output the info contained in each node.
void reversePrint() const;
//Function to output the info contained in each node
//in reverse order.
int length() const;
//Function to return the number of nodes in the list.
//Postcondition: The value of count is returned.
Type front() const;
//Function to return the first element of the list.
//Precondition: The list must exist and must not be empty.
//Postcondition: If the list is empty, the program
// terminates; otherwise, the first
// element of the list is returned.
Type back() const;
//Function to return the last element of the list.
//Precondition: The list must exist and must not be empty.
//Postcondition: If the list is empty, the program
// terminates; otherwise, the last
// element of the list is returned.
bool search(const Type& searchItem) const;
//Function to determine whether searchItem is in the list.
//Postcondition: Returns true if searchItem is found in
// the list, otherwise returns false.
void insert(const Type& insertItem);
//Function to insert insertItem in the list.
//Precondition: If the list is nonempty, it must be in
// order.
//Postcondition: insertItem is inserted at the proper place
// in the list, first points to the first
// node, last points to the last node of the
// new list, and count is incremented by 1.
void deleteNode(const Type& deleteItem);
//Function to delete deleteItem from the list.
//Postcondition: If found, the node containing deleteItem
// is deleted from the list; first points
// to the first node of the new list, last
// points to the last node of the new list,
// and count is decremented by 1; otherwise,
// an appropriate message is printed.
doublyLinkedList();
//default constructor
//Initializes the list to an empty state.
//Postcondition: first = nullptr; last = nullptr; count = 0;
doublyLinkedList(const doublyLinkedList<Type>& otherList);
//copy constructor
~doublyLinkedList();
//destructor
//Postcondition: The list object is destroyed.
protected:
int count;
nodeType<Type> *first; //pointer to the first node
nodeType<Type> *last; //pointer to the last node
private:
void copyList(const doublyLinkedList<Type>& otherList);
//Function to make a copy of otherList.
//Postcondition: A copy of otherList is created and
// assigned to this list.
};
template <class Type>
doublyLinkedList<Type>::doublyLinkedList()
{
first= nullptr;
last = nullptr;
count = 0;
}
template <class Type>
bool doublyLinkedList<Type>::isEmptyList() const
{
return (first == nullptr);
}
template <class Type>
void doublyLinkedList<Type>::destroy()
{
nodeType<Type> *temp; //pointer to delete the node
while (first != nullptr)
{
temp = first;
first = first->next;
delete temp;
}
last = nullptr;
count = 0;
}
template <class Type>
void doublyLinkedList<Type>::initializeList()
{
destroy();
}
template <class Type>
int doublyLinkedList<Type>::length() const
{
return count;
}
template <class Type>
void doublyLinkedList<Type>::print() const
{
nodeType<Type> *current; //pointer to traverse the list
current = first; //set current to point to the first node
while (current != nullptr)
{
cout << current->info << " "; //output info
current = current->next;
}//end while
}//end print
template <class Type>
void doublyLinkedList<Type>::reversePrint() const
{
nodeType<Type> *current; //pointer to traverse
//the list
current = last; //set current to point to the
//last node
while (current != nullptr)
{
cout << current->info << " ";
current = current->back;
}//end while
}//end reversePrint
template <class Type>
bool doublyLinkedList<Type>::
search(const Type& searchItem) const
{
bool found = false;
nodeType<Type> *current; //pointer to traverse the list
current = first;
while (current != nullptr && !found)
if (current->info >= searchItem)
found = true;
else
current = current->next;
if (found)
found = (current->info == searchItem); //test for
//equality
return found;
}//end search
template <class Type>
Type doublyLinkedList<Type>::front() const
{
assert(first != nullptr);
return first->info;
}
template <class Type>
Type doublyLinkedList<Type>::back() const
{
assert(last != nullptr);
return last->info;
}
template <class Type>
void doublyLinkedList<Type>::insert(const Type& insertItem)
{
nodeType<Type> *current; //pointer to traverse the list
nodeType<Type> *trailCurrent = nullptr; //pointer just before current
nodeType<Type> *newNode; //pointer to create a node
bool found;
newNode = new nodeType<Type>; //create the node
newNode->info = insertItem; //store the new item in the node
newNode->next = nullptr;
newNode->back = nullptr;
if(first == nullptr) //if the list is empty, newNode is
//the only node
{
first = newNode;
last = newNode;
count++;
}
else
{
found = false;
current = first;
while (current != nullptr && !found) //search the list
if (current->info >= insertItem)
found = true;
else
{
trailCurrent = current;
current = current->next;
}
if (current == first) //insert newNode before first
{
first->back = newNode;
newNode->next = first;
first = newNode;
count++;
}
else
{
//insert newNode between trailCurrent and current
if (current != nullptr)
{
trailCurrent->next = newNode;
newNode->back = trailCurrent;
newNode->next = current;
current->back = newNode;
}
else
{
trailCurrent->next = newNode;
newNode->back = trailCurrent;
last = newNode;
}
count++;
}//end else
}//end else
}//end insert
template <class Type>
void doublyLinkedList<Type>::deleteNode(const Type& deleteItem)
{
nodeType<Type> *current; //pointer to traverse the list
nodeType<Type> *trailCurrent; //pointer just before current
bool found;
if (first == nullptr)
cout << "Cannot delete from an empty list." << endl;
else if (first->info == deleteItem) //node to be deleted is
//the first node
{
current = first;
first = first->next;
if (first != nullptr)
first->back = nullptr;
else
last = nullptr;
count--;
delete current;
}
else
{
found = false;
current = first;
while (current != nullptr && !found) //search the list
if (current->info >= deleteItem)
found = true;
else
current = current->next;
if (current == nullptr)
cout << "The item to be deleted is not in "
<< "the list." << endl;
else if (current->info == deleteItem) //check for
//equality
{
trailCurrent = current->back;
trailCurrent->next = current->next;
if (current->next != nullptr)
current->next->back = trailCurrent;
if (current == last)
last = trailCurrent;
count--;
delete current;
}
else
cout << "The item to be deleted is not in list."
<< endl;
}//end else
}//end deleteNode
template<class Type>
void doublyLinkedList<Type>::copyList(const doublyLinkedList<Type>& otherList)
{
nodeType<Type> *newNode; //pointer to create a node
nodeType<Type> *current; //pointer to traverse the list
if(first != nullptr) //if the list is nonempty, make it empty
destroy();
if(otherList.first == nullptr) //otherList is empty
{
first = nullptr;
last = nullptr;
count = 0;
}
else
{
current = otherList.first; //current points to the
//list to be copied.
count = otherList.count;
//copy the first node
first = new nodeType<Type>; //create the node
first->info = current->info; //copy the info
first->next = nullptr;
first->back = nullptr;
last = first;
current = current->next;
//copy the remaining list
while (current != nullptr)
{
newNode = new nodeType<Type>; //create the node
newNode->info = current->info;
newNode->next = nullptr;
newNode->back = last;
last->next = newNode;
last = newNode;
current = current->next;
}//end while
}//end else
}//end copyList
template<class Type>
doublyLinkedList<Type>::doublyLinkedList(const doublyLinkedList<Type>& otherList)
{
first = nullptr;
copyList(otherList);
}
template<class Type>
const doublyLinkedList<Type>& doublyLinkedList<Type>::operator=
(const doublyLinkedList<Type>& otherList)
{
if (this != &otherList) //avoid self-copy
{
copyList(otherList);
}//end else
return *this;
}
template<class Type>
doublyLinkedList<Type>::~doublyLinkedList()
{
destroy();
}
#endif
Due Today at 11:59 PM HST doublyLinkedList.hmain.cpp 0/2 passed Testing the doublyLinkedList.h 1 Winclude ostream 6 Information Build Failed 3 using nanespace std: Review Mode Project Help Download Share Instructions Some test are not run unless your program builds successfully Write a program to test various operations of the class doublyLinkedL1st S int matn) 6 IINrite your main here 7 return ? Build Output Theme Light nain.cpp :3 : 9: errar: #include expects "FILENAME" or -FILENAME nain.cpp: In Tunction int nain()*: natn.cpp:16:18: error: missing tenplate argunents before List Grading As you complete the steps above, you can use the Test button to check if the lab tests are passing. Once you are satisfied with the results, use the Grade button to save your score. Keymap Default doublylinkedl1st list ADanger Area nain.cpp:29:1: errar: ist was not declared in this scope Reset Project List.inser t (58); Test Case FAILED: Input / output test 1 INPUT 11 56 89 84 1 23 32 -999 23 32 OUTPUT RESULTS List in ascanding order: 1 11 23 32 56 84 89 List in descending order: 89 84 56 32 23 11 1 List after deleting 231 11 32 36 34 8s 2 found in the list Show DetailsExplanation / Answer
Below I had implemented double linked list using c++.
Hope this helps.
Thankyou..... :)
/*
* C++ Program to Implement Doubly Linked List
*/
#include<iostream>
#include<cstdio>
#include<cstdlib>
/*
* Node Declaration
*/
using namespace std;
struct node
{
int info;
struct node *next;
struct node *prev;
}*start;
/*
Class Declaration
*/
class double_llist
{
public:
void create_list(int value);
void add_begin(int value);
void add_after(int value, int position);
void delete_element(int value);
void search_element(int value);
void display_dlist();
void count();
void reverse();
double_llist()
{
start = 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 begining"<<endl;
cout<<"3.Add after position"<<endl;
cout<<"4.Delete"<<endl;
cout<<"5.Display"<<endl;
cout<<"6.Count"<<endl;
cout<<"7.Reverse"<<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.add_begin(element);
cout<<endl;
break;
case 3:
cout<<"Enter the element: ";
cin>>element;
cout<<"Insert Element after postion: ";
cin>>position;
dl.add_after(element, position);
cout<<endl;
break;
case 4:
if (start == NULL)
{
cout<<"List empty,nothing to delete"<<endl;
break;
}
cout<<"Enter the element for deletion: ";
cin>>element;
dl.delete_element(element);
cout<<endl;
break;
case 5:
dl.display_dlist();
cout<<endl;
break;
case 6:
dl.count();
break;
case 7:
if (start == NULL)
{
cout<<"List empty,nothing to reverse"<<endl;
break;
}
dl.reverse();
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;
if (start == NULL)
{
temp->prev = NULL;
start = temp;
}
else
{
s = start;
while (s->next != NULL)
s = s->next;
s->next = temp;
temp->prev = s;
}
}
/*
* Insertion at the beginning
*/
void double_llist::add_begin(int value)
{
if (start == NULL)
{
cout<<"First Create the list."<<endl;
return;
}
struct node *temp;
temp = new(struct node);
temp->prev = NULL;
temp->info = value;
temp->next = start;
start->prev = temp;
start = temp;
cout<<"Element Inserted"<<endl;
}
/*
* Insertion of element at a particular position
*/
void double_llist::add_after(int value, int pos)
{
if (start == NULL)
{
cout<<"First Create the list."<<endl;
return;
}
struct node *tmp, *q;
int i;
q = start;
for (i = 0;i < pos - 1;i++)
{
q = q->next;
if (q == NULL)
{
cout<<"There are less than ";
cout<<pos<<" elements."<<endl;
return;
}
}
tmp = new(struct node);
tmp->info = value;
if (q->next == NULL)
{
q->next = tmp;
tmp->next = NULL;
tmp->prev = q;
}
else
{
tmp->next = q->next;
tmp->next->prev = tmp;
q->next = tmp;
tmp->prev = q;
}
cout<<"Element Inserted"<<endl;
}
/*
* Deletion of element from the list
*/
void double_llist::delete_element(int value)
{
struct node *tmp, *q;
/*first element deletion*/
if (start->info == value)
{
tmp = start;
start = start->next;
start->prev = NULL;
cout<<"Element Deleted"<<endl;
free(tmp);
return;
}
q = start;
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::display_dlist()
{
struct node *q;
if (start == NULL)
{
cout<<"List empty,nothing to display"<<endl;
return;
}
q = start;
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::count()
{
struct node *q = start;
int cnt = 0;
while (q != NULL)
{
q = q->next;
cnt++;
}
cout<<"Number of elements are: "<<cnt<<endl;
}
/*
* Reverse Doubly Link List
*/
void double_llist::reverse()
{
struct node *p1, *p2;
p1 = start;
p2 = p1->next;
p1->next = NULL;
p1->prev = p2;
while (p2 != NULL)
{
p2->prev = p2->next;
p2->next = p1;
p1 = p2;
p2 = p2->prev;
}
start = p1;
cout<<"List Reversed"<<endl;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.