In this assignment, you will implement three methods on a singly linked list: in
ID: 3804511 • Letter: I
Question
In this assignment, you will implement three methods on a singly linked list: insert_front(), insert_back(), and isDuplicated().
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<T>::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<T>::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<T>::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 <iostream>
#include "ListNode.h"
#include "ListIterator.h"
namespace cs20a {
template <class T>
class List {
public:
List();
List(const List& rhs);
~List();
bool isEmpty() const;
void makeEmpty();
ListIterator<T> zeroth() const;
ListIterator<T> first() const;
void insert_front(const T& data, const ListIterator<T> &iter);
//*** Implement these methods only. ***
void insert_front(const T& data);
void insert_back(const T& data);
bool List<T>::isDuplicated(const T& data) const;
//*** *** *** *** *** *** *** *** ***
ListIterator<T> findPrevious(const T& data) const;
void remove(const T& data);
const List& operator =(const List& rhs);
private:
ListNode<T> *head, *tail;
};
}
#endif
List.cpp:
#ifndef LIST_CPP
#define LIST_CPP
#include "List.h"
namespace cs20a {
template <class T>
List<T>::List() {
head = tail = new ListNode < T >();
}
template <class T>
List<T>::List(const List<T>& rhs) {
head = tail = new ListNode < T >;
*this = rhs;
}
template <class T>
List<T>::~List() {
makeEmpty();
delete head;
}
template <class T>
bool List<T>::isEmpty() const {
return head->next == nullptr;
}
template <class T>
void List<T>::makeEmpty() {
while (!isEmpty()) {
remove(first().retrieve());
}
}
template <class T>
ListIterator<T> List<T>::zeroth() const {
return(ListIterator<T>(head));
}
template <class T>
ListIterator<T> List<T>::first() const {
return(ListIterator<T>(head->next));
}
template <class T>
void List<T>::insert_front(const T& data, const ListIterator<T> &iter) {
if (iter.isValid()) {
ListNode<T>* newnode = new ListNode<T>(data, iter.current->next);
if (head == tail) //*** Set tail for first node entered ***
tail = newnode;
iter.current->next = newnode;
}
}
template <class T>
void List<T>::insert_front(const T& data) {
// *** Code goes here ***
}
template <class T>
void List<T>::insert_back(const T& data)
{
// *** Code goes here ***
}
template <class T>
bool List<T>::isDuplicated(const T& data) const
{
// *** Code goes here ***
return false;
}
template <class T>
ListIterator<T> List<T>::findPrevious(const T& data) const {
ListNode<T>* node = head;
while (node->next != nullptr && node->next->element != data) {
node = node->next;
}
if (node->next == nullptr) {
node = nullptr;
}
return ListIterator<T>(node);
}
template <class T>
void List<T>::remove(const T& data) {
ListIterator<T> iter = findPrevious(data);
if (iter.isValid()) {
ListNode<T>* node = findPrevious(data).current;
if (node->next != nullptr) {
ListNode<T> *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 <class T>
const List<T>& List<T>::operator =(const List<T>& rhs) {
if (this != &rhs) {
makeEmpty();
ListIterator<T> rightiter = rhs.first();
ListIterator<T> myiterator = zeroth();
while (rightiter.isValid()) {
insert_front(rightiter.retrieve(), myiterator);
rightiter.advance();
myiterator.advance();
}
}
return(*this);
}
}
//template<class T>
//T List<T>::pop_back()
//{
// if (isEmpty())
// cout << "Empty List" << endl;
// ListNode<T> *oldNode = tail;
// T element = oldNode->element;
// ListNode<T>* prevNode = findPrevious(tail->element).current;
// prevNode->next = oldNode->next;
// tail = prevNode;
// return element;
//}
//template<class T>
//T List<T>::pop_front()
//{
// if (isEmpty())
// cout << "Empty List" << endl;
// ListNode<T> *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 <iostream>
#include "ListNode.h"
namespace cs20a {
template <class T>
class List; // forward declaration
template <class T>
class ListIterator {
public:
ListIterator();
bool isValid() const;
void advance();
const T& retrieve() const;
private:
ListNode<T> * current;
ListIterator(ListNode<T> *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<T>;
};
}
#endif
ListIterator.cpp:
#ifndef LISTITERATOR_CPP
#define LISTITERATOR_CPP
#include "ListIterator.h"
namespace cs20a {
template <class T>
ListIterator<T>::ListIterator() : current(NULL) {
// all assignments occurred above
}
template <class T>
ListIterator<T>::ListIterator(ListNode<T> *node) : current(node) {
// all assignments occurred above
}
template <class T>
bool ListIterator<T>::isValid() const {
return((current != NULL));
}
template <class T>
void ListIterator<T>::advance() {
if (isValid()) {
current = current->next;
}
}
template <class T>
const T& ListIterator<T>::retrieve() const {
if (!(isValid())) throw std::logic_error("Invalid iterator.");
return(current->element);
}
}
#endif
ListNode.h:
#ifndef LISTNODE_H
#define LISTNODE_H
#include <iostream>
namespace cs20a {
template <class T>
struct ListNode {
ListNode() {};
ListNode(const T& theElement, ListNode<T> * node = nullptr) {
element = theElement;
next = node;
}
T element;
ListNode* next;
};
}
#endif
ListMenu.cpp:
// Menu.cpp : Defines the entry point for the console application.
//
#include <iostream>
#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<int>& l);
int main(int argc, char* argv[]) {
int value;
List<int> list;
ListIterator<int> iter;
CHOICE choice;
do {
choice = menu();
switch (choice) {
case MAKEEMPTY:
list.makeEmpty();
break;
case ISEMPTY:
if (list.isEmpty()) {
cout << "list is empty" << endl;
}
else {
cout << "list is not empty" << endl;
}
break;
case REMOVE:
cout << "Please provide int to remove: ";
cin >> value;
list.remove(value);
break;
case INSERTBACK:
cout << "Please provide int to insert in back: ";
cin >> value;
list.insert_back(value);
break;
case INSERTFRONT:
cout << "Please provide int to insert in front: ";
cin >> value;
list.insert_front(value);
break;
case DUPLICATED:
cout << "Please provide int to check for duplicates: ";
cin >> value;
if (list.isDuplicated(value))
cout << "Duplicates found." << endl;
else
cout << "No duplicates found." << endl;
break;
case FINDPREVIOUS:
cout << "Please provide int to find: ";
cin >> value;
iter = list.findPrevious(value);
if (iter.isValid()) {
cout << "previous element = " << iter.retrieve() << endl;
}
else {
cout << "data element was not found!" << endl;
}
break;
case PRINT:
printList(list);
break;
}
} while (choice != QUIT);
return(0);
}
CHOICE menu() {
char choice;
CHOICE result;
cout << "(M)akeEmpty Is(E)mpty Insert(F)ront Insert(B)ack (R)emove FindPre(v)ious (P)rint Is(D)uplicate (Q)uit: " << endl;
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<int>& l) {
if (l.isEmpty())
cout << "Empty list" << endl;
else {
ListIterator<int> iter = l.first();
while (iter.isValid()) {
cout << iter.retrieve() << " -> ";
iter.advance();
}
cout << "NULL";
cout << endl;
}
}
Explanation / Answer
Answer:
Here are the implemented functions:
1. insert_front :
template class<T>
void List<T>::insert_front(const T& data){
ListNode<T>* newNode = new ListNode<T>(data, nullptr);
//If list is not empty
if(head != nullptr){
newNode->next = head->next;
head = newNode;
}
//List is empty
else{
head = newNode;
}
}
2. insert_back :
template class<T>
void List<T>::insert_back(const T& data){
ListNode<T>* newNode = new ListNode<T>(data, nullptr);
//Implies the list is not empty
if(tail != null){
tail->next = newNode;
tail = newNode;
}
//List is empty
else{
tail = newNode;
}
}
3. isDuplicated :
template <class T>
bool List<T>::isDuplicated(const T& data) const
{
ListNode<T>* node = head;
//Traverse till the end of the list
while(node != nullptr){
if(node->element == data){
return true;
}
node = node->next;
}
return false;
}