In this assignment, you will implement three methods on a singly linked list: insert_front(), insert_back(), and isDuplicated().

A singly linked list is a linear collection of elements called nodes, each containing data and a next pointer. Insertion and removal of nodes in a linked list is efficient; only pointer reassignments are required unlike an array which may require shifting elements.

1. Without using a ListIterator, define and implement a new method called insert_back that inserts an item at the back of the list.

void List::insert_back( const T& t );

A brute force implementation of insert_back would traverse the list to find its end and then insert the item; therefore, it would run in linear time, O(n). Make insert_back run in constant time, O(1).

HINT: Your List class must maintain a pointer to the last node. Member functions must ensure that this pointer is always valid.

2. Without using a ListIterator, define and implement a new method called insert_front that inserts an item at the front of the list.

void List::insert_front( const T& t );

HINT: Your List class must maintain a pointer to the first node. Member functions must ensure that this pointer is always valid. Make insert_front run in constant time, O(1).

3. Without using a ListIterator, define and implement a method called isDuplicated that determines whether a list contains duplicates.

bool List::isDuplicated( const T& t ) const;

The starter files for this assignment are below. Do not alter the class definition in any way. Use the driver provided below. Programs that crash are subject to a 50% penalty. Please submit the class implementation file only (List.cpp). PLEASE NOTE: You may not use any Standard Template Library (STL) classes for this assignment. Use only code provided below.

Please compile the code from your answer and check for errors before submitting code that is not working.

List.h:

#ifndef LIST_H

#define LIST_H

#include

#include "ListNode.h"

#include "ListIterator.h"

namespace cs20a {

template

class List {

public:

List();

List(const List& rhs);

~List();

bool isEmpty() const;

void makeEmpty();

ListIterator zeroth() const;

ListIterator first() const;

void insert_front(const T& data, const ListIterator &iter);

//*** Implement these methods only. ***

void insert_front(const T& data);

void insert_back(const T& data);

bool List::isDuplicated(const T& data) const;

//*** *** *** *** *** *** *** *** ***

ListIterator findPrevious(const T& data) const;

void remove(const T& data);

const List& operator =(const List& rhs);

private:

ListNode *head, *tail;

};

}

#endif

List.cpp:

#ifndef LIST_CPP

#define LIST_CPP

#include "List.h"

namespace cs20a {

template

List::List() {

head = tail = new ListNode ();

}

template

List::List(const List& rhs) {

head = tail = new ListNode ;

*this = rhs;

}

template

List::~List() {

makeEmpty();

delete head;

}

template

bool List::isEmpty() const {

return head->next == nullptr;

}

template

void List::makeEmpty() {

while (!isEmpty()) {

remove(first().retrieve());

}

}

template

ListIterator List::zeroth() const {

return(ListIterator(head));

}

template

ListIterator List::first() const {

return(ListIterator(head->next));

}

template

void List::insert_front(const T& data, const ListIterator &iter) {

if (iter.isValid()) {

ListNode* newnode = new ListNode(data, iter.current->next);

if (head == tail) //*** Set tail for first node entered ***

tail = newnode;

iter.current->next = newnode;

}

}

template

void List::insert_front(const T& data) {

// *** Code goes here ***

}

template

void List::insert_back(const T& data)

{

// *** Code goes here ***

}

template

bool List::isDuplicated(const T& data) const

{

// *** Code goes here ***

return false;

}

template

ListIterator List::findPrevious(const T& data) const {

ListNode* node = head;

while (node->next != nullptr && node->next->element != data) {

node = node->next;

}

if (node->next == nullptr) {

node = nullptr;

}

return ListIterator(node);

}

template

void List::remove(const T& data) {

ListIterator iter = findPrevious(data);

if (iter.isValid()) {

ListNode* node = findPrevious(data).current;

if (node->next != nullptr) {

ListNode *oldNode = node->next;

node->next = (node->next->next); // Skip oldNode

if (tail == oldNode) // *** Reset tail node, when deleting tail

tail = node;

delete oldNode;

}

}

}

// Deep copy of linked list

template

const List& List::operator =(const List& rhs) {

if (this != &rhs) {

makeEmpty();

ListIterator rightiter = rhs.first();

ListIterator myiterator = zeroth();

while (rightiter.isValid()) {

insert_front(rightiter.retrieve(), myiterator);

rightiter.advance();

myiterator.advance();

}

}

return(*this);

}

}

//template

//T List::pop_back()

//{

// if (isEmpty())

// cout

// ListNode *oldNode = tail;

// T element = oldNode->element;

// ListNode* prevNode = findPrevious(tail->element).current;

// prevNode->next = oldNode->next;

// tail = prevNode;

// return element;

//}

//template

//T List::pop_front()

//{

// if (isEmpty())

// cout

// ListNode *oldNode = head->next;

// T element = oldNode->element;

// head->next = oldNode->next;

// if (tail == oldNode) // *** Reset tail node, when deleting tail

// tail = head;

// delete oldNode;

// return element;

//}

#endif

ListIterator.h:

#ifndef LISTITERATOR_H

#define LISTITERATOR_H

#include

#include "ListNode.h"

namespace cs20a {

template

class List; // forward declaration

template

class ListIterator {

public:

ListIterator();

bool isValid() const;

void advance();

const T& retrieve() const;

private:

ListNode * current;

ListIterator(ListNode *node);

// List exposes ListIterator instances via public methods

// no external access should be given to the current pointer

// friend access is required by List class to ensure this information hiding

friend class List;

};

}

#endif

ListIterator.cpp:

#ifndef LISTITERATOR_CPP

#define LISTITERATOR_CPP

#include "ListIterator.h"

namespace cs20a {

template

ListIterator::ListIterator() : current(NULL) {

// all assignments occurred above

}

template

ListIterator::ListIterator(ListNode *node) : current(node) {

// all assignments occurred above

}

template

bool ListIterator::isValid() const {

return((current != NULL));

}

template

void ListIterator::advance() {

if (isValid()) {

current = current->next;

}

}

template

const T& ListIterator::retrieve() const {

if (!(isValid())) throw std::logic_error("Invalid iterator.");

return(current->element);

}

}

#endif

ListNode.h:

#ifndef LISTNODE_H

#define LISTNODE_H

#include

namespace cs20a {

template

struct ListNode {

ListNode() {};

ListNode(const T& theElement, ListNode * node = nullptr) {

element = theElement;

next = node;

}

T element;

ListNode* next;

};

}

#endif

ListMenu.cpp:

// Menu.cpp : Defines the entry point for the console application.

//

#include

#include "List.h"

#include "List.cpp"

#include "ListIterator.h"

#include "ListIterator.cpp"

using namespace std;

using namespace cs20a;

enum CHOICE { MAKEEMPTY, REMOVE, ISEMPTY, FINDPREVIOUS, INSERTFRONT, INSERTBACK, DUPLICATED, QUIT, PRINT };

CHOICE menu();

void printList(const List& l);

int main(int argc, char* argv[]) {

int value;

List list;

ListIterator iter;

CHOICE choice;

do {

choice = menu();

switch (choice) {

case MAKEEMPTY:

list.makeEmpty();

break;

case ISEMPTY:

if (list.isEmpty()) {

cout

}

else {

cout

}

break;

case REMOVE:

cout

cin >> value;

list.remove(value);

break;

case INSERTBACK:

cout

cin >> value;

list.insert_back(value);

break;

case INSERTFRONT:

cout

cin >> value;

list.insert_front(value);

break;

case DUPLICATED:

cout

cin >> value;

if (list.isDuplicated(value))

cout

else

cout

break;

case FINDPREVIOUS:

cout

cin >> value;

iter = list.findPrevious(value);

if (iter.isValid()) {

cout

}

else {

cout

}

break;

case PRINT:

printList(list);

break;

}

} while (choice != QUIT);

return(0);

}

CHOICE menu() {

char choice;

CHOICE result;

cout

cin >> choice;

switch (choice) {

case 'M':

case 'm':

result = MAKEEMPTY;

break;

case 'E':

case 'e':

result = ISEMPTY;

break;

case 'F':

case 'f':

result = INSERTFRONT;

break;

case 'B':

case 'b':

result = INSERTBACK;

break;

case 'R':

case 'r':

result = REMOVE;

break;

case 'V':

case 'v':

result = FINDPREVIOUS;

break;

case 'P':

case 'p':

result = PRINT;

break;

case 'D':

case 'd':

result = DUPLICATED;

break;

case 'Q':

case 'q':

result = QUIT;

break;

}

return(result);

}

void printList(const List& l) {

if (l.isEmpty())

cout

else {

ListIterator iter = l.first();

while (iter.isValid()) {

cout ";

iter.advance();

}

cout

cout

}

}

12 99 37 12 99 37