C++ Create a class that implements a sorted, doubly-linked list: Start with a co
ID: 3815324 • Letter: C
Question
C++
Create a class that implements a sorted, doubly-linked list:
Start with a copy of the sortedList class. Call your new class doublyLinkedList. Convert the baseline code into a doubly linkedlist, and thoroughly test all existing operations (make sure to check all edge conditions), and then implement the new operations below.
The class should have the following additional class methods:
• A reverse method: this method will reverse the order of the doubly linked list. This method takes no parameters, and returns nothing.
• A printFront method: this method prints the list from front to back, one element per line.The method is void, takes no parameters, and should not be able to modify private classmembers.
• A printBack method: this method prints the list from back to front, one element per line.The method is void, takes no parameters, and should not be able to modify private classmembers.o Additional requirement: start at the tail pointer and traverse the list using pointersin order to print the list. In other words, cannot use retrieveElement or ptrTo!
P.S this is a “by-position” doubly-linked list!
Below is the sortedList class copy. Please help!
// Implementation file for sortedList, a pointer-based by-position list of type
// specified in header.
#include "sortedList.h" // header file
#include <cstddef> // for NULL
#include <cassert> // for assert()
sortedList::sortedList() // Default Constructor
: size(0), head(NULL)
{
}
sortedList::~sortedList() // Destructor
{
bool success;
while (!isEmpty())
{
success = deleteElement(1); // Repeatedly delete item 1
}
}
bool sortedList::isEmpty() const
{
return (size == 0);
}
int sortedList::getLength() const
{
return size;
}
// Copy Constructor
sortedList::sortedList(const sortedList& original)
: size(original.size)
{
if (original.head == NULL)
head = NULL; // original list is empty
else
{
// copy first node
head = new listNode;
assert(head != NULL); // check allocation
head->item = original.head->item;
// copy rest of list
listNode *newPtr = head; // new list pointer
// newPtr points to last node in new list
// origPtr points to nodes in original list
for (listNode *origPtr = original.head->next; origPtr != NULL; origPtr = origPtr->next)
{
newPtr->next = new listNode;
assert(newPtr->next != NULL);
newPtr = newPtr->next;
newPtr->item = origPtr->item;
}
newPtr->next = NULL;
}
}
// Locates a specified node in a linked list
// Parameters: the number of the desired node (starting at 1, an int)
// Returns: Returns a pointer to the desired node, or NULL if position out of range.
sortedList::listNode *sortedList::ptrTo(int position) const
{
if ((position < 1) || (position > getLength()))
return NULL;
else // count from the beginning of the list
{
listNode *cur = head;
for (int skip = 1; skip < position; ++skip)
cur = cur->next;
return cur;
}
}
bool sortedList::retrieveElement(int position, listItemType& dataItem) const
{
bool success = ((position >= 1) && (position <= getLength()));
if (success)
{
// get pointer to node, then data in node
listNode *cur = ptrTo(position);
dataItem = cur->item;
}
return success;
}
// Iterative SortedList Insert
void sortedList::insertElement(listItemType newItem)
{
listNode *prev = NULL;
listNode *cur = head;
while ((cur != NULL) && (newItem > cur->item))
{
prev = cur;
cur = cur->next;
}
listNode *newPtr = new listNode;
newPtr->item = newItem;
newPtr->next = cur;
if (prev == NULL)
head = newPtr;
else
prev->next = newPtr;
size++;
}
void sortedList::locateElement(listItemType key, int& position)
{
listNode *cur = head;
position = 1;
while (cur != NULL && cur->item != key)
{
cur = cur->next;
position++;
}
if (cur == NULL)
position = -1;
}
bool sortedList::deleteElement(int position)
{
listNode *cur;
bool success = ((position >= 1) && (position <= getLength()));
if (success)
{
--size;
if (position == 1)
{
// delete the first node from the list
cur = head; // save pointer to node
head = head->next;
}
else
{
listNode *prev = ptrTo(position - 1);
// delete the node after the node
// to which Prev points
cur = prev->next; // save pointer to node
prev->next = cur->next;
}
// return node to system
cur->next = NULL;
delete cur;
cur = NULL;
}
return success;
}
bool sortedList::operator== (const sortedList& right)
{
//shortcut in case comparing same two sortedLists
if (&right == this)
return true;
//check sizes are the same
if (getLength() != right.getLength())
return false;
//temporary variables for comparison
listItemType mine;
listItemType theirs;
//compare each element
for (int i = 1; i <= getLength(); i++)
{
//use public methods to get each element
retrieveElement(i, mine);
right.retrieveElement(i, theirs);
//return false after any mismatch
if (mine != theirs)
return false;
}
//if code gets here, all elements must be the same
return true;
}
bool sortedList::operator!= (const sortedList& right)
{
return !(*this == right);
}
Explanation / Answer
THIS IS TO DEMONSTRATE HOW DOUBLE LINKED LIST OPERATES IN C++ PROGRAM /* * C++ Program to Implement Doubly Linked List */ #include #include #include /* * 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) { coutRelated Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.