(C++)

#ifndef LIST_HPP #define LIST_HPP

template class List { protected: // the current number of elements in the list int length;

public: // default constructor List() { }

// destructor virtual ~List() { }

// add the argument to the end of the list virtual void append(const T&) = 0;

// remove all elements in the list virtual void clear() = 0;

// return the element at the given position (argument) virtual T getElement(int) const = 0;

// return the current length of the list virtual int getLength() const = 0;

// insert the given element (argument 2) at // the given position (argument 1) virtual void insert(int, const T&) = 0;

// determine if the list currently empty virtual bool isEmpty() const = 0;

// remove the element at the given position (argument) virtual void remove(int) = 0;

// replace the element at the given position (argument 1) with // the value given (argument 2) virtual void replace(int, const T&) = 0; };

#endif

#include "DoublyList.hpp"

int main() { // create a doubly linked list DoublyList myList;

myList.append("Heart"); myList.insert(0, "Your"); myList.insert(0, "May"); myList.replace(-3, "?"); // should display error myList.append("Citrus"); myList.insert(5, "kweh"); // should display error myList.remove(3);

cout

string word = myList.getElement(2); cout

DoublyList secondList = myList; secondList.append("Beat"); secondList.replace(2, "Drums");

cout

secondList.remove(4); // should display error

DoublyList thirdList; cout

cout

thirdList.append("Be A"); thirdList.append("Yellow"); thirdList.append("Banana");

cout

myList.clear();

if (myList.isEmpty()) { cout

// terminate return 0; }

#ifndef DOUBLY_LIST_HPP #define DOUBLY_LIST_HPP

#include "List.hpp" #include using namespace std;

template class DoublyList : public List { protected: // represents an element in the doubly linked list struct Node { T value; Node* next; Node* prev;

Node(T v, Node* n = nullptr, Node* p = nullptr) : value(v), next(n), prev(p) { } };

// a pointer to the front of the list Node* head;

public: // default constructor DoublyList();

// copy constructor DoublyList(const DoublyList&);

// overloaded assignment operator DoublyList& operator=(const DoublyList&);

// destructor virtual ~DoublyList();

// add the argument to the end of the list virtual void append(const T&) override;

// remove all elements in the list virtual void clear() override;

// return the element at the given position (argument) virtual T getElement(int) const override;

// return the current length of the list virtual int getLength() const override;

// insert the given element (argument 2) at // the given position (argument 1) virtual void insert(int, const T&) override;

// determine if the list currently empty virtual bool isEmpty() const override;

// remove the element at the given position (argument) virtual void remove(int) override;

// replace the element at the given position (argument 1) with // the value given (argument 2) virtual void replace(int, const T&) override;

// overloaded stream insertion operator /*********************************************************************** * Analyzing the number of output operations. * Input size n is the length of the list. * * Scenario #1, the if block executes: * T(n) = 1 * * Scenario #2, the else block executes: * T(n) = n + (n - 1) + 1 * = 2n * * Asymptotic analysis: * T(n) = O(n) ***********************************************************************/ friend ostream& operator& myObj) { if (myObj.isEmpty()) { outStream

while (curr != nullptr) { outStream value;

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

curr = curr->next; }

outStream

return outStream; } };

/******************************************************************************* * Analyzing the number of assignment operations. * Input size n is the length of the list. * * Asymptotic analysis: * T(n) = ? *******************************************************************************/ template DoublyList::DoublyList() { }

/******************************************************************************* * Analyzing the number of assignment operations. * Input size n is the length of the list. * * Asymptotic analysis: * T(n) = ? *******************************************************************************/ template DoublyList::DoublyList(const DoublyList& copyObj) { }

/******************************************************************************* * Analyzing the number of assignment operations. * Input size n is the length of the list. * * Asymptotic analysis: * T(n) = ? *******************************************************************************/ template DoublyList& DoublyList::operator=(const DoublyList& rightObj) { }

/******************************************************************************* * Analyzing the number of delete operations. * Input size n is the length of the list. * * Asymptotic analysis: * T(n) = ? *******************************************************************************/ template DoublyList::~DoublyList() { }

/******************************************************************************* * Analyzing the number of assignment operations. * Input size n is the length of the list. * * Asymptotic analysis: * T(n) = ? *******************************************************************************/ template void DoublyList::append(const T& elem) { }

/******************************************************************************* * Analyzing the number of assignment operations. * Input size n is the length of the list. * * Asymptotic analysis: * T(n) = ? *******************************************************************************/ template void DoublyList::clear() { }

/******************************************************************************* * Analyzing the number of links accessed. * Input size n is the length of the list. * * Asymptotic analysis: * T(n) = ? *******************************************************************************/ template T DoublyList::getElement(int position) const { }

/******************************************************************************* * Analyzing the number of accesses to class attributes. * Input size n is the length of the list. * * Asymptotic analysis: * T(n) = ? *******************************************************************************/ template int DoublyList::getLength() const { }

/******************************************************************************* * Analyzing the number of assignment operations. * Input size n is the length of the list. * * Asymptotic analysis: * T(n) = ? *******************************************************************************/ template void DoublyList::insert(int position, const T& elem) { }

/******************************************************************************* * Analyzing the number of comparison operations. * Input size n is the length of the list. * * Asymptotic analysis: * T(n) = ? *******************************************************************************/ template bool DoublyList::isEmpty() const { }

/******************************************************************************* * Analyzing the number of assignment operations. * Input size n is the length of the list. * * Asymptotic analysis: * T(n) = ? *******************************************************************************/ template void DoublyList::remove(int position) { }

/******************************************************************************* * Analyzing the number of assignment operations. * Input size n is the length of the list. * * Asymptotic analysis: * T(n) = ? *******************************************************************************/ template void DoublyList::replace(int position, const T& elem) { }

#endif

Implementing and Analyzing the Doubly Linked List For this lab, download the.zip file that contains the List ADT. The List class template is completely implemented. The DoublyList class template is not. That's your task in this lab. Additionally, for each method implemented, provide an asymptotic analysis. Make sure to add code for edge cases! For example, does your implementation work if the list is empty? Sample Run To test your implementation, just run my main file that was included in the .zip file. It contains code that tests each method. If you did this all correctly, you should see the following output: ERROR: position out of bounds ERROR: position out of bounds May Your Heart Element 2: Heart May Your Drums Beat ERROR: position out of bounds List is empty, no elements to display. thirdList length: 3 May Your Heart Be A Yellow Banana myList is empty! Submission You will be submitting one.zip file that contains your DoublyList class. Implementing and Analyzing the Doubly Linked List For this lab, download the.zip file that contains the List ADT. The List class template is completely implemented. The DoublyList class template is not. That's your task in this lab. Additionally, for each method implemented, provide an asymptotic analysis. Make sure to add code for edge cases! For example, does your implementation work if the list is empty? Sample Run To test your implementation, just run my main file that was included in the .zip file. It contains code that tests each method. If you did this all correctly, you should see the following output: ERROR: position out of bounds ERROR: position out of bounds May Your Heart Element 2: Heart May Your Drums Beat ERROR: position out of bounds List is empty, no elements to display. thirdList length: 3 May Your Heart Be A Yellow Banana myList is empty! Submission You will be submitting one.zip file that contains your DoublyList class