Using C++ and the code below

Modify LList.h to implement the functions or operator overloading listed below. Most of the functions are stubbed out so you just need to add the proper logic.

You will be editing the LList.h file and compiling the sandbox file.

Here is a list of the required methods you must fill in:

LList.h

push_back(int) - Place the given value on the end of the linked-list.

reverse() const - Return a new linked-list which is the current one reversed.

size() - Returns the size (length) of the linked-list.

empty() - Return true if the list is empty otherwise return false.

pop_back() - Removes the last element of the linked-list. If the list is empty do nothing.

operator==(LList) - Return true if the current linked-list contains identical values to the passed one.

Overload the plus (+) operator to add two lists together.

Extra Credit: 10-Points Each

getAt(unsigned) - Return the value at the given position, or throw a logic error if the index is invalid. See the overloaded [] operator for hints on how to throw an exception.

setAt(int, unsigned) - Assign the given value to the given position (0-based). Throw a logic error if the index is invalid.

You can use list-sandbox.cpp to experiment with the linked-list classes. Compile list-sandbox.cpp to a list-sandbox executable. List-sandbox.cpp will not be graded.

Tip for Testing: Use the list-sandbox.cpp to create linked list objects and also test out your various list modifying functions. LList.h has a definition for overloaded << operator. This member function can let you print out the contents of the list and hence can be a helpful function to test your code in list-sandbox.cpp. Also, size() is called within this function so you will need to implement that one first.

list-sandbox.cpp

/* Fill me in */

#include #include

#include "LList.h"

using namespace std;

int main(){ LList a; for(int i = 0; i < 50; i++){ a.push_front(45); }

return 0; }

LList.h

#ifndef LLIST_H #define LLIST_H

/* Linked List class that store integers, with [] operator. Uses head pointer. Paul Talaga September 2015 */ #include #include

#define int int

using namespace std;

struct node_t { int data; node_t* next; };

// This implementation will use a head pointer, // allowing O(1) insertion on the front, // and O(n) on the end. class LList {

public: LList(){ head = NULL; }

~LList(){ clear(); }

LList(const LList& other){ // Do the same as the default constructor head = NULL; // Check if the other LList is empty if(other.head == NULL){ return; } // Not empty? Iterate through the other list // and push_back on myself. node_t* temp = other.head; while(temp){ push_back(temp->data); temp = temp->next; } }

// Similar to copy constructor, but check for self // assignment, if not, clear and copy all data. LList& operator= (const LList& other){ if(this == &other){ return *this; } clear(); if(other.head == NULL){ return *this; } node_t* temp = other.head; while(temp){ push_back(temp->data); temp = temp->next; } return *this; }

bool empty() const { // TODO: Fill me in }

unsigned int size() const { // TODO: Fill me in }

void push_back(int value){ // TODO: Fill me in }

void push_front(int value){ // Empty list? if(head == NULL){ head = new node_t; head->data = value; head->next = NULL; }else{ // Not empty node_t* temp = new node_t; temp->data = value; temp->next = head; head = temp; } }

void pop_front(){ if(head == NULL) return; node_t* temp = head; head = head->next; delete temp; }

void pop_back(){ // TODO: Fill me in }

// Overload [] operator // Return logic error if index out of bounds int& operator[](unsigned pos) const { node_t* temp = head; while(temp != NULL && pos > 0){ temp = temp->next; pos--; } // As long as I don't have a null pointer, assign. if(pos == 0 && temp != NULL){ return temp->data; } throw logic_error("Index invalid"); }

LList reverse() const { // TODO: Fill me in return LList(); // Remove me! }

bool operator==(const LList& other) const { }

bool operator!=(const LList& other) const { return !operator==(other); }

void clear(){ node_t* last = head; while(head){ head = head->next; delete last; last = head; } // Normaly you never want to change head or you'll orphan part // of the list, but in this case we are wiping the list, // so it is ok to so and saves us a variable. head = NULL; }

private: node_t* head;

};

// Note this function is O(n^2) because getAt is O(n) and we are // doing it n times.

ostream& operator<<(ostream& out, const LList &other){ out << "["; for(unsigned int i = 0; i < other.size(); i++){ out << other[i] << ", "; }

out << "]"; return out; }

#endifin