//INSTRUCTION:

//It helps to first create if-then-else structure to fill in later.

//- Make sure PURPOSE and PARAMETER comments are given in detail

// Add sufficient comments to your code body to describe what it does.

// - Make sure all if-then-else are commented describing which case it is

// - Make sure all local variables are described fully with their purposes

//Complete the TODO parts.

// ====================================================

//Complier: g++

//File type: linkedList.cpp implementation file

//=====================================================

#include

#include"linkedlist.h"

using namespace std;

//cunstructor that initializes an empty list

LinkedList::LinkedList() {

front = nullptr;

rear = nullptr;

count = 0;

}

/**

* @brief Destructor to destroy all nodes and release memory

*/

LinkedList::~LinkedList() {

Node *p, *q;

p = front;

while (p != nullptr) {

q = p->next;

delete p;

p = q;

}

}

/**

* @brief Purpose: Checks if the list is empty

* @return true if the list is empty, false otherwise

*/

bool LinkedList::isEmpty() const {

// TODO: Add code here

return count == 0;

}

/**

* @brief Get the number of nodes in the list

* @return int The number of nodes in the list

*/

int LinkedList::length() const{

return count;

}

/**

* @brief Convert the list to a string

*

*/

string LinkedList::toString() {

string str = "[";

Node *ptr = front;

if (ptr != nullptr) {

// Head node is not preceded by separator

str += to_string(ptr->val);

ptr = ptr->next;

}

while (ptr != nullptr) {

str += ", " + to_string(ptr->val);

ptr = ptr->next;

}

str += "]";

return str;

}

/**

* @brief Displays the contents of the list

*/

void LinkedList::displayAll() {

cout << toString() << endl;

}

//Add a node to the end of the list

void LinkedList::addRear(T val) {

Node *p = new Node;

p->val = val;

p->next = nullptr;

if (isEmpty()) {

front = p;

}

else {

rear->next = p;

}

rear = p;

count++;

// consider the two cases of whether the list was empty

}

//Add a node to the front of the list

void LinkedList::addFront(T val) {

Node *p = new Node;

p->val = val;

p->next = front;

if (isEmpty()) {

rear = p;

}

front = p;

count++;

// consider the two cases of whether the list was empty

}

//Delete the first node of the list

bool LinkedList::deleteFront(T &OldNum) {

if (isEmpty()) {

return false;

}

Node *p = front;

OldNum = p->val;

front = front->next;

if (front == nullptr) {

rear = nullptr;

}

delete p;

count--;

return true;

// consider if the list was empty and return false if the list is empty

// consider the special case of deleting the only node in the list

}

//Delete the last node of the list

bool LinkedList::deleteRear(T &OldNum) {

if (isEmpty()) {

return false;

}

Node *p = rear;

OldNum = p->val;

if (front == rear) {

front = rear = nullptr;

}

else {

Node *q = front;

while (q->next != rear) {

q = q->next;

}

rear = q;

q->next = nullptr;

}

delete p;

count--;

return true;

// consider if the list was empty and return false if the list is empty

// consider the special case of deleting the only node in the list

}

/* --- harder ones for test 2 and 3 -- */

/**

* @brief Delete a node at a given position from the list. The

* node at position pos is deleted and the value of the deleted node is returned in val.

* The valid range of pos is 1 to count. pos = 1 is the first node, and pos = count is the last node.

* @param pos: position of the node to be deleted

* @param val: it is set to the value of the node to be deleted

* @return true: if the node was deleted successfully

* @return false: if the node was not deleted successfully because the position was out of range

*/

bool LinkedList::deleteAt(int pos, T &val) {

//TODO: Add code here

// check if the pos is valid first, then move the ptr to the rigth positon

// consider the special case of deleting the first node and the last node

// Do not forget to set value.

}

/**

* @brief Insert a value at a specified position in the list. The valid pos is in the range of 1 to count+1.

* The value will be inserted before the node at the specified position. if pos = 1, the value will be inserted

* at the front of the list. if pos = count+1, the value will be inserted at the rear of the list.

* @param pos: position to insert the value at.

* @param val: value to insert.

* @return true: if the value was inserted.

* @return false: if the value was not inserted because pos is out of the range.

*/

bool LinkedList::insertAt(int pos, T val) {

//TODO: Add code here

// check if the pos is valid first, then move the ptr to the rigth positon

// consider the special case of inserting the first node and the last node

}

/**

* @brief Copy Constructor to allow pass by value and return by value of a LinkedList

* @param other LinkedList to be copied

*/

LinkedList::LinkedList(const LinkedList &other) {

// Start with an empty list

front = nullptr;

rear = nullptr;

count = 0;

// TODO: Add code here. Interate through the other list and add a new node to this list

// for each node in the other list. The new node should have the same value as the other node.

}

/**

* @brief Overloading of = (returns a reference to a LinkedList)

* @param other LinkedList to be copied

* @return reference to a LinkedList

*/

LinkedList &LinkedList::operator=(const LinkedList &other) {

if(this != &other) { // check if the same object

// Delete all nodes in this list

// TODO: Add code here

// Interate through the other list and add a new node to this list

// Be sure to set the front and rear pointers to the correct values

// Be sure to set the count to the correct value

// TODO: Add code here

}

return *this;

}