Question
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
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
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started