Implementing and Analyzing the Linked List (C++)

For this lab, I 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.

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!

Implementing and Analyzing the (Un)Sorted Linked List

In the second part of the lab, first go back to the UnsortedList ADT and finish the asymptotic analysis for each method. Next, finish implementing the methods for the SortedList ADT. Again, consider the edge cases! Then, provide an asymptotic analysis for each method.

The last thing to do is create a new main file. This file should test all the methods for the unsorted and sorted linked list.

Files:

LinkedList.hpp file from part 1.

UnsortedList.hpp, SortedList.hpp, and main.cpp files from part 2.

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

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

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