Implementing and Analyzing the Linked List (C++)

For this lab, I want you to download the .zip file that contains the List ADT and the LinkedList ADT. The List class template is completely implemented. The LinkedList class template is not. That's your task in this lab. Additionally, for each method implemented, provide an asymptotic analysis.

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!

MAIN.cpp

#include "LinkedList.hpp" #include

int main() { LinkedList 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 << myList;

string word = myList.getElement(2); cout << "Element 2: " << word << endl;

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

cout << secondList;

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

LinkedList thirdList; cout << thirdList; thirdList = myList;

cout << "thirdList length: " << thirdList.getLength() << endl;

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

cout << thirdList;

myList.clear();

if (myList.isEmpty()) { cout << "myList is empty! "; }

return 0; } List.hpp

#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

LinkedList.hpp

#ifndef LINKED_LIST_HPP #define LINKED_LIST_HPP

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

template class LinkedList : public List { protected:

private:

public: // default constructor LinkedList();

// copy constructor LinkedList(const LinkedList&);

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

// destructor virtual ~LinkedList();

// 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. * * Asymptotic analysis: * T(n) = ? ***********************************************************************/ friend ostream& operator<<(ostream& outStream, const LinkedList& myObj) { } };

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

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

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

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

/******************************************************************************* * Analyzing the number of assignment operations. * Input size n is the length of the list. * * Asymptotic analysis: * T(n) = ? *******************************************************************************/ template void LinkedList::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 LinkedList::clear() { }

/******************************************************************************* * Analyzing the number of links accessed. * Input size n is the length of the list. * * Asymptotic analysis: * T(n) = ? *******************************************************************************/ template T LinkedList::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 LinkedList::getLength() const { }

/******************************************************************************* * Analyzing the number of assignment operations. * Input size n is the length of the list. * * Asymptotic analysis: * T(n) = ? *******************************************************************************/ template void LinkedList::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 LinkedList::isEmpty() const { }

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

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

#endif