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);

}

Answer 1

#include<iostream>
#include <cstddef> // for NULL
#include <cassert> // for assert()
using namespace std;

typedef int listItemType; // Assuming it to be int type for testing (can be any other)

class doublyLinkedList
{
typedef struct listnode
{
listItemType item;
   struct listnode* prev;
   struct listnode* next;
}listNode;

listNode* head;
listNode* tail;
int size;

public:
doublyLinkedList();
~doublyLinkedList();
bool isEmpty() const ;
int getLength() const;
doublyLinkedList(const doublyLinkedList&);
listNode* ptrTo(int) const;
bool retrieveElement(int position, listItemType& dataItem) const;
void insertElement(listItemType newItem);
void locateElement(listItemType key, int& position);
bool deleteElement(int position);
bool operator== (const doublyLinkedList& right);
bool operator!= (const doublyLinkedList& right);
void printFront(void) const;
void printBack(void) const;
void reverse(void);
};

doublyLinkedList::doublyLinkedList():size(0),head(NULL),tail(NULL)
{
}

doublyLinkedList::~doublyLinkedList()
{
bool success;
   while(!isEmpty())
   {
   success = deleteElement(1);
   }
}

bool doublyLinkedList::isEmpty() const
{
return (size == 0);
}

int doublyLinkedList::getLength() const
{
return size;
}

doublyLinkedList::doublyLinkedList(const doublyLinkedList& original)
:size(original.size)
{
if(original.head == NULL)
   head = tail = NULL;
   else{
  
       head = new listNode;
       assert(head != NULL); //Check allocation
       assert(tail != NULL); //Check allocation
       head->item = original.head->item;
  
  
      
listNode *newPtr = head; // new list pointer
     
   for (listNode *origPtr = original.head->next; origPtr != NULL; origPtr = origPtr->next)
{
newPtr->next = new listNode;
assert(newPtr->next != NULL);
       newPtr->next->prev = newPtr;
newPtr = newPtr->next;
newPtr->item = origPtr->item;
}
newPtr->next = NULL;
   tail = newPtr;
   }
}

doublyLinkedList::listNode *doublyLinkedList::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 doublyLinkedList::retrieveElement(int position, listItemType& dataItem) const
{
bool success = ((position >= 1) && (position <= getLength()));
if (success)
{
listNode *cur = ptrTo(position);
dataItem = cur->item;
}
return success;
}

void doublyLinkedList::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;
   head->prev = NULL;
  
   if(cur != NULL){
   cur->prev = newPtr;

if(cur->next == NULL)
   tail = cur;
   }
   else{
   tail = head;
   }
}
else{
prev->next = newPtr;
   newPtr->prev = prev;
   if(cur != NULL){
   cur->prev = newPtr;
         
       if(cur->next == NULL){
       tail = cur;
       }
   }
   else{
   tail = newPtr;
   }
}

size++;
}

void doublyLinkedList::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 doublyLinkedList::deleteElement(int position)
{
listNode *cur;
bool success = ((position >= 1) && (position <= getLength()));
if (success)
{
--size;
if (position == 1)
{
cur = head; // save pointer to node
head = head->next;
}
else
{
listNode *prev = ptrTo(position - 1);
cur = prev->next; // save pointer to node
prev->next = cur->next;
         
       if(cur->next != NULL)
       cur->next->prev = prev;
         
       if(cur == tail){
   tail = tail->prev;
   }
       cur->prev = NULL;
}

   cur->next = NULL;
delete cur;
cur = NULL;
}
return success;
}

bool doublyLinkedList::operator== (const doublyLinkedList& right)
{
if (&right == this)
return true;

if (getLength() != right.getLength())
return false;

listItemType mine;
listItemType theirs;

for (int i = 1; i <= getLength(); i++)
{
retrieveElement(i, mine);
right.retrieveElement(i, theirs);
if (mine != theirs)
return false;
}
/*if code gets here, all elements must be the same*/
return true;
}

bool doublyLinkedList::operator!= (const doublyLinkedList& right)
{
return !(*this == right);
}

void doublyLinkedList::printFront(void) const
{
if(head == NULL){
   cout<< "List empty !!" <<endl;
   }
   else{
   listNode* temp = head;
      
       while(temp != NULL){
       cout<< temp->item <<endl;
           temp = temp->next;
       }
   }
}

void doublyLinkedList::printBack(void) const
{
if(head == NULL){
   cout<< "List empty !!" <<endl;
   }
   else{
   listNode* temp = tail;
      
       while(temp != NULL){
       cout<< temp->item <<endl;
           temp = temp->prev;
       }
   }
}

void doublyLinkedList::reverse(void)
{
listNode* newHead = head, * newTail = tail;
  
if((head == NULL) || (getLength() == 0)){
   return;
   }
   else{
   listNode* temp = tail,* temp1 = NULL;
       while(temp != NULL){

       temp1 = temp->next;
       temp->next = temp->prev;
           temp->prev = temp1;
           temp = temp->next;
       }
      
       temp1 = head;
       head = tail;
       tail = temp1;
   }
}

int main()
{
doublyLinkedList list;

listItemType item = 10;

list.insertElement(item);
list.insertElement(20);
list.insertElement(18);
list.insertElement(5);
list.insertElement(50);

doublyLinkedList list2 = list;

list.printFront();
  
cout<<endl << "List2 : " <<endl;
list2.printFront();
/*
cout<<endl;
cout<<endl;
list.printBack();
  
cout<<endl;
cout<<endl;
list.reverse();
list.printFront();
cout<<endl;
list.printBack();
*/

cout<< endl << "COmparing" <<endl;
cout<< (list == list2) <<endl;
cout<< (list != list2) <<endl;

cout<<endl<<endl;
list.deleteElement(5);
//list.printFront();
//list.printBack();
cout<< endl << "COmparing" <<endl;
cout<< (list == list2) <<endl;
cout<< (list != list2) <<endl;

list.retrieveElement(2,item);
cout<<"Item: " << item <<endl;
return 0;
}