Question

List.h
template
class List { // List class ADT
             public:
   virtual void clear() = 0;

// Inserts an item into the list at position index
   virtual bool insert(const ListItemType& newItem) = 0;

   // Append "it" at the end of the list
   // The client must ensure that the list's capacity is not exceeded
   virtual bool append(const ListItemType& newItem) = 0;

   // Deletes an item from the list at a given position
   virtual ListItemType remove() = 0;

   // Set the current position to the start of the list
   virtual void moveToStart() = 0;

   // Set the current position to the end of the list
   virtual void moveToEnd() = 0;

   // Move the current position one step left, no change if already at beginning
   virtual void prev() = 0;

   // Move the current position one step right, no change if already at end
   virtual void next() = 0;

   //Return the number of items stored in the list
   virtual int length() const = 0;

   // Return the position of the current element
   virtual int currPos() const = 0;

   // Set the current position to "pos"
   virtual bool moveToPos(int pos) = 0;

   // Return true if current position is at end of the list
   virtual bool isAtEnd() const = 0;

   // Return the current element
   virtual ListItemType getValue() const = 0;

   // Note: The fololwing methods assume that ListItemType is comparable: that is to say the relational operators such as == exist.

   //search for the first occurance in the list of an item. If found return true and set curr to the location.
   // if not found, return false and set curr to the end of the list.
   virtual bool find(const ListItemType& newItem) = 0;

   //search for the next occurance in the list of an item. Start with the next position after curr. If found return true and set curr to the location.
   // if not found, return false and set curr to the end of the list.
   virtual bool findNext(const ListItemType& newItem) = 0;

   // count the number of times a value is found in the list
   // curr should be set back to its current location after the count.
   virtual int count(const ListItemType& newItem) = 0;

};

LList.h

#include "list.h"

// Linked list implementation

template
class Node
{
public:
   ListItemType element;
   Node* next;

   Node()
   {
       next = nullptr;
   }

   Node(const ListItemType& e)
   {
       this->element = e;
       next = nullptr;
   }
};

template
class LList : public List {

private:
   Node* head;   
   Node* tail;   
   Node* curr;   
   int listSize;

public:
   // Constructor
   LList() {
       head = tail = curr = nullptr;
       listSize = 0;
   }

   //Destructor
   ~LList() {
       clear();
   }

   // Remove all elements
   void clear() {
       if (listSize > 0) {
           Node* temp;
           curr = head;
           do {
               temp = curr -> next;
               delete curr;
               curr = temp;
           } while (curr != nullptr);
       }
       curr = tail = head = nullptr;
       listSize = 0;
   }

  
   bool insert(const ListItemType& newItem) {
       if (listSize == 0) {
           head = new Node(newItem);
           tail = head;
           curr = head;
       }
       else if (curr == head) {
           Node* temp = new Node(newItem);
           temp->next = head;
           head = temp;
           curr = head;
       }
       else if (curr == nullptr) {
           return false;
       }
       else {
           Node* temp = head;
           while (temp->next != curr)
               temp = temp->next;
           temp->next = new Node(newItem);
           temp->next->next = curr;
           curr = temp->next;
       }
       listSize++;
       return true;
   }

   // Append "it" to list
   bool append(const ListItemType& newItem) {
      
       // hint: handle an empty list and a non-empty list separately
       cout << "***** complete this method ...\n";
       return false;
   }

   // Remove and return current element
   ListItemType remove() {
       ListItemType it = curr->element;
       if (curr == head) {
           head = head->next;
           delete curr;
           curr = head;
           listSize--;
           if (head == nullptr)
               tail = nullptr;
       }
       else if (curr == tail) {
           moveToPos(listSize - 2);
           delete curr->next;
           tail = curr;
           tail->next = nullptr;
           curr = nullptr;
           listSize--;
       }
       else {
           Node* temp = head;
           while (temp->next != curr)
               temp = temp->next;
           temp->next = curr->next;
           delete curr;
           curr = temp->next;
           listSize--;
       }
       return it;
   }

   void moveToStart() { curr = head; }
   void moveToEnd() { curr = nullptr; }

                                                  
   void prev() {
       if (head == curr) return;
       Node* temp = head;
      
       while (temp -> next != curr) temp = temp -> next;
       curr = temp;
   }

  
   void next() { if (curr != nullptr) curr = curr -> next; }

   int length() const { return listSize; }

                                             
   int currPos() const {
       if (curr == nullptr) return listSize;
       Node* temp = head;
       int i;
       for (i = 0; curr != temp; i++)
           temp = temp -> next;
       return i;
   }

   // Move down list to "pos" position
   bool moveToPos(int pos) {
       if ((pos < 0) || (pos > listSize)) return false;
       curr = head;
       for (int i = 0; i next;
       return true;
   }

   // Return true if current position is at end of the list
   bool isAtEnd() const { return curr == nullptr; }

   // Return current element value.
   ListItemType getValue() const { return curr -> element; }

   // Check if the list is empty
   bool isEmpty() const { return listSize == 0; }

   bool find(const ListItemType& it) {
       cout << "***** complete this method ...\n";
       // hint: if list is empty return false
       // set curr to head and traverse list until curr becomes nullptr or "it"is found
       return false;
   }

   //search for the next occurance in the list of an item. Start with the next position after curr. If found return true and set curr to the location.
   // if not found, return false and set curr to the end of the list.
   bool findNext(const ListItemType& it) {
       cout << "***** complete this method ..\n";
       // hint: if curr is nullptr return false
       // set curr to curr->next and traverse list until curr becomes nullptr or "it" is found

       return false;
   }
   // count the number of times a value is found in the list
   // curr should remain where it is
   int count(const ListItemType& it) {
       cout << "***** complete this method ...\n";
       // hint: do not use curr, but a temp pointer to traverse the list.
       // set temp to head, and traverse list until temp is nullptr counting elements that are equal
       int count = 0;

       return count;
   }

};
1- Complete the append method in LList.h( Bold )

2- Complete the find, findNext and count in LList.h(Bold)

Answer 1

Append Method

bool append(const ListItemType& newItem) {

// hint: handle an empty list and a non-empty list separately

if (listSize == 0) {

head = new Node(newItem);

tail = head;

curr = head;

} else {

Node* temp = head;

while (temp->next != nullptr)

temp = temp->next;

temp->next = new Node(newItem);

temp->next->next = nullptr;

tail = temp->next;

}

listSize++;

return true;

}

-------------------------------------------------------------------------------------------------

bool find(const ListItemType& it) {

if (listSize == 0) {

return false;

} else {

Node* temp = head;

while (temp!= nullptr){

if(temp->element == it)

return true;

temp = temp -> next;

}

}

return false;

}

----------------------------------------------------------------------------------------------------------------------------------------------------

bool findNext(const ListItemType& it) {

// hint: if curr is nullptr return false

// set curr to curr->next and traverse list until curr becomes nullptr or "it" is found

if(curr == nullptr)

return false;

Node* temp = curr->next;

while (temp!= nullptr){

if(temp->element == it)

return true;

temp = temp -> next;

}

return false;

}

----------------------------------------------------------------------------------------------------------------------------------------------

int count(const ListItemType& it) {

// hint: do not use curr, but a temp pointer to traverse the list.

// set temp to head, and traverse list until temp is nullptr counting elements that are equal

int count = 0;

if (listSize == 0) {

return count;

} else {

Node* temp = head;

while (temp!= nullptr){

++count;

temp = temp -> next;

}

}

return count;

}

--------------------------------------------------------------------------------

Thanks, PLEASE COMMENT if there is any concern.