cpp assignment
troook61
lab_9.zipLab 9/Lab9.docx
In this lab, you must create DoublyLinkedList and DoublyLinkedNode classes that extends itself from the supplied base classes. Note that the base classes will need to be modified in order to better support inheritance (i.e. declare a protected section) and polymorphism (i.e. make certain functions virtual). In addition to being children of LinkedList, your DoublyLinkedList needs to intelligently use its newfound pointer directions. For example, it might be helpful to have the getElementAt function start from the end in the event that the requested element is closer to the end of the list.
__MACOSX/Lab 9/._Lab9.docx
Lab 9/LinkedList.h
#ifndef LINKED_LIST_H #define LINKED_LIST_H #include "LinkedListNode.h" template <typename T> class LinkedList { private: LinkedListNode<T> *_front = nullptr; int _size = 0; public: //empty constructor that does nothing LinkedList() { } //Copy constructor. Allows for perfect duplication //of an existing linked list. (note: you're going //to do something similar for PA5) LinkedList(const LinkedList<T>& to_copy) { //Remember: goal is to make perfect copy. So //we start at the front LinkedListNode<T> *copy_node = to_copy._front; //it's possible that copy_node starts off null if(copy_node == nullptr) { _front = nullptr; _size = to_copy._size; return; } //make a copy of to_copy's front _front = new LinkedListNode<T>{*copy_node}; //used to move through our LL LinkedListNode<T> *cursor = _front; //make copies of each item copy_node = copy_node->getNext(); while(copy_node != nullptr) { //make copy of node LinkedListNode<T> *copy = new LinkedListNode<T>(*copy_node); //assign result to our cursor cursor->setNext(copy); //progress both cursor and copy_node forward cursor = cursor->getNext(); copy_node = copy_node->getNext(); } } //Move constructor: assume ownership of an existing LL LinkedList(LinkedList<T> &&to_move) { _size = to_move._size; _front = to_move._front; to_move._front = nullptr; } //destructor needs to delete all dynamically created //nodes virtual ~LinkedList() { LinkedListNode<T> *cursor = _front; while(cursor != nullptr) { LinkedListNode<T> *temp = cursor->getNext(); delete cursor; cursor = temp; } } //returns a value at a specific location inside LL T getElementAt(int index) const { //TODO: make sure index is within bounds LinkedListNode<T> *cursor = _front; int counter = 0; //move forward through our LL until we hit //either nullptr (somewhat unexpected) //or we arrive at the requested index while(cursor != nullptr && counter < index) { cursor = cursor->getNext(); counter++; } //At here: we've arrived at our index return cursor->getValue(); } int getSize() const { return _size; } void AddElementToEnd(T value) { addElementAt(value, _size); } T removeElementAt(int index) { _size--; //special case: remove first element if(index == 0) { LinkedListNode<T> *temp = _front->getNext(); T value = _front->getValue(); delete _front; _front = temp; return value; } int counter = 0; LinkedListNode<T> *current = _front; LinkedListNode<T> *previous = _front; while(current != nullptr && counter < index) { counter++; previous = current; current = current->getNext(); } //remove current from LL previous->setNext(current->getNext()); //delete current from memory T value = current->getValue(); delete current; return value; } void addElementAt(T value, int index) { //create a new linked list node LinkedListNode<T> *new_node = new LinkedListNode<T>{value}; //special case check: are we adding to the front? if(index == 0) { //attach current front to new_node new_node->setNext(_front); _front = new_node; _size++; return; } LinkedListNode<T> *current = _front; LinkedListNode<T> *previous = _front; int counter = 0; while(current != nullptr && counter < index) { counter++; previous = current; current = current->getNext(); } //At this point, we need to connect new_node //into our LL. Meaning, set previous' next to //new_node and new_node's next to current previous->setNext(new_node); new_node->setNext(current); _size++; } }; #endif // LINKED_LIST_H
__MACOSX/Lab 9/._LinkedList.h
Lab 9/LinkedListNode.h
#ifndef LINKED_LIST_NODE_H #define LINKED_LIST_NODE_H #include <string> using namespace std; template<typename T> class LinkedListNode { private: T _value; LinkedListNode *_next = nullptr; public: LinkedListNode(T value) { _value = value; } LinkedListNode(const LinkedListNode<T>& to_copy) { //copy value _value = to_copy.getValue(); //Note: we could recursively call the copy constructor //on to_copy's next, but this might be overstepping. _next = nullptr; } //Because we are templated, we don't know what the default //value for T data type should be, so we need a default, //empty constructor. LinkedListNode(){} T getValue() { return _value; } void setValue(T value) { _value = value; } LinkedListNode *getNext() { return _next; } void setNext(LinkedListNode *next) { _next = next; } }; #endif // LINKED_LIST_NODE_H
__MACOSX/Lab 9/._LinkedListNode.h
Lab 9/main (2).cpp
#include <iostream> #include "LinkedList.h" using namespace std; int main() { LinkedList<char> letters{}; for(int i = 'a'; i < 'z'; i++) { letters.addElementAt((char)i, i - 'a'); } for(int i = 0; i < letters.getSize(); i++) { cout << letters.getElementAt(i) << endl; } while(letters.getSize() > 0) { cout << letters.removeElementAt(0) << " "; } cout << endl; return 0; }
