LList.h code Modify LList.h to implement the functions or operator overloading l
ID: 3704370 • Letter: L
Question
LList.h code
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.
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==(LListR) - Return true if the current linked-list contains identical values to the passed one.
Overload the plus (+) operator to add two lists together.
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.
#ifndef LLIST_H #define LLIST_H #include <ostream> #include <stdexcept> #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){ 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 = 1; i < other.size(); i++){ out << other.getAt(i-1) << ", "; } if(other.size() > 0){ out << other.getAt(other.size() - 1); } out << "]"; return out; } #endifExplanation / Answer
//Llist.h
#pragma once
#ifndef LLIST_H
#define LLIST_H
#include <ostream>
#include <stdexcept>
#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
if (head == NULL)
return true;
else
return false;
}
//Added by chegEA
unsigned int size() const {
// TODO: Fill me in
int count = 0;
node_t *cur = head;
while (cur != NULL)
{
count++;
cur = cur->next;
}
return count;
}
////Added by chegEA
void push_back(int value) {
// TODO: Fill me in
node_t *cur = head;
if (empty() == true)
{
head = new node_t;
head->data = value;
head->next = NULL;
}
else
{
while (cur->next != NULL)
{
cur = cur->next;
}
cur->next = new node_t;
cur->next->data = value;
cur->next->next = NULL;
}
}
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;
}
////Added by chegEA
void pop_back() {
// TODO: Fill me in
node_t *cur = head,*prev=head;
if (!empty()) //list not empty
{
while (cur->next != NULL)
{
prev = cur;
cur = cur->next;
}
prev->next = NULL;
delete cur;
}
}
// Overload [] operator
// Return logic error if index out of bounds
int& operator[](unsigned pos) {
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");
}
//Added by chegEA
LList reverse() const {
// TODO: Fill me in
struct node_t* prev = NULL;
struct node_t* cur = head;
struct node_t* next = NULL;
LList tmp;
tmp.head = head;
while (cur != NULL)
{
next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
//return LList(); // Remove me!
tmp.head = prev;
return tmp;
}
//Added by chegEA
LList operator+(const LList& other) const
{
node_t *cur=head;
LList tmp;
//push first list ,then second list into new list
while (cur != NULL)
{
tmp.push_back(cur->data);
cur = cur->next;
}
cur = other.head;
while (cur != NULL)
{
tmp.push_back(cur->data);
cur = cur->next;
}
return tmp;
}
//Added by chegEA
bool operator==(const LList& other) const {
bool status = true;
if (other.size() == size()) //if two list have same size then check each element
{
node_t *cur1 = head, *cur2 = other.head;
while (cur1->next != NULL && cur2->next != NULL)
{
if (cur1->data != cur2->data)
{
status = false;;
break;
}
else
{
cur1 = cur1->next;
}
}
}
return status;
}
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;
}
//Added by chegEA
int getAt(unsigned int index) const
{
int count = 0;
node_t *cur = head;
while (cur != NULL)
{
if (index == count)
return cur->data;
count++;
cur = cur->next;
}
if(index >= count)
throw logic_error("Index invalid");
}
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 = 1; i < other.size(); i++) {
out << other.getAt(i - 1) << ", ";
}
if (other.size() > 0) {
out << other.getAt(other.size() - 1);
}
out << "]";
return out;
}
#endif
--------------------------------------------
//main.cpp
#include"Llist.h"
#include<iostream>
using namespace std;
int main()
{
LList list1, list2;
list1.push_front(1);
list1.push_front(2);
list1.push_front(3);
list1.push_front(4);
//display list1
cout << "list1: "<<list1 << endl;
//check push back function
list2.push_back(1);
list2.push_back(2);
list2.push_back(3);
list2.push_back(4);
cout << "list2: "<<list2 << endl;
//check getat function
cout << "At index 3 of list1: "<<list1.getAt(3) << endl;
cout << "At index 2 of list2: "<<list2.getAt(2) << endl;
//check pop functions
list1.pop_back() ;
list1.pop_back();
//print list1
cout << "list1: "<<list1 << endl;
list2.pop_front();
list2.pop_front();
cout << "list2: "<<list2 << endl;
//test + operator to add two lists
LList list3;
list3 = list1 + list2;
cout << "List3: " << list3 << endl;
//test for == and != operator
LList list4;
list4.push_back(4);
list4.push_back(3);
if (list1 == list4)
{
cout << "list1: " << list1 << " equals to " << "list4: " << list4 << endl;
}
else
{
cout << "two lists are not equal" << endl;
}
if (list1 != list2)
{
cout << "two lists are not equal" << endl;
}
//test reverse list
list2.push_back(7);
list2.push_back(8);
cout << "list2 after push back of two items 7,8 : " << list2 << endl;
cout << "reverse of list2: " <<list2.reverse() << endl;
//check for invalid index, this gives logic error remove that
cout << "At index 4 of list1: " << list1.getAt(4) << endl;
}
/*output
list1: [4, 3, 2, 1]
list2: [1, 2, 3, 4]
At index 3 of list1: 1
At index 2 of list2: 3
list1: [4, 3]
list2: [3, 4]
List3: [4, 3, 3, 4]
list1: [4, 3] equals to list4: [4, 3]
two lists are not equal
list2 after push back of two items 7,8 : [3, 4, 7, 8]
reverse of list2: [8, 7, 4, 3]
*/
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.