IntList Recursion Assignment Specifications:
You will add some additional recursive functions to your IntList class as well as make sure the Big 3 are defined.
IntNode class
I am providing the IntNode class you are
required to use. Place this class definition
within the IntList.h file exactly as is. Make sure you place it
above the definition of your IntList class. Notice that you will
not code an implementation file for the IntNode class. The IntNode
constructor has been defined inline (within the class declaration).
Do not write any other functions for the IntNode class. Use as
is.
struct IntNode
{
int data;
IntNode *next;
IntNode( int data ) : data(data), next(0)
{}
};
IntList class
Encapsulated (Private) Data Fields
head: IntNode *
tail: IntNode *
Public Interface (Public Member Functions)
IntList()
IntList( const IntList &list)
~IntList()
void display() const
void push_front( int value )
void push_back( int value )
void pop_front()
void select_sort()
void insert_sorted( int value )
void remove_duplicates()
IntListIterator begin()
IntListIterator end()
int front() const
int back() const
int length() const;
int sum() const;
void reverseDisplay() const;
IntList & operator=( const IntList &list )
Constructor and Destructor
IntList() - the default constructor
Initialize an empty list.
IntList(const IntList &list) - the overloaded copy constructor
Initialize a new list with the contents of an existing list.
~IntList()
This function should deallocate all remaining dynamically allocated memory (all remaining IntNodes).
Accessors
void display() const
This function displays to a single line all of the int values stored in the list, each separated by a space. It should NOT output a newline or space at the end.
intListIterator begin()
This function returns an iterator at the beginning of the linked list. Returns an iterator pointing to head.
intListIterator end()
This function returns an iterator one element past the last element of the linked list. Returns an iterator pointing to NULL.
int front() const
This function returns the data in the head of the linked list.
int back() const
This function returns the data in the tail of the linked list.
int length() const
This function recursively determines the length of the list.
int sum() const
This function recursively determines the sum of all of the elements in the list.
void reverseDisplay() const
This function recursively displays the contents of the list in reverse order.
Mutators
void push_front( int value )
This function inserts a data value (within a new node) at the front end of the list.
void push_back( int value )
This function inserts a data value (within a new node) at the back end of the list.
void pop_front()
This function removes the value (actually removes the node that contains the value) at the front end of the list. Do nothing if the list is already empty. In other words, do not call the exit function in this function as we did with the IntVector's pop_front.
void select_sort( )
This function sorts the list into ascending order using the selection sort algorithm.
void insert_sorted( int value )
This function assumes the values in the list are in sorted (ascending) order and inserts the data into the appropriate position in the list (so that the values will still be in ascending order after insertion). DO NOT call select_sort within this function.
void remove_duplicates()
This function removes all values (actually removes the nodes that contain the value) that are duplicates of a value that already exists in the list. Always remove the later duplicate, not the first instance of the duplicate. DO NOT call select_sort within this function. This function does NOT assume the data is sorted.
IntList & operator=(const IntList &list)
This function copies over all of the nodes in an existing list to another already existing list.
IntListIterator class
Encapsulated (Private) Data Fields
current: IntNode *
Public Interface (Public Member Functions)
IntListIterator()
IntListIterator( IntNode *ptr)
int operator*()
intListIterator operator++()
bool operator==(const intListIterator& right) const;
bool operator!=(const intListIterator& right) const;
Constructors
IntListIterator() - the default constructor
Initialize the iterator. Basically just need to set the pointer to NULL.
IntListIterator(intNode *ptr) - the overloaded copy constructor
Initialize the iterator with parameter passed int. Need to set the pointer equal to whatever pointer is passed in.
Accessors
int operator*()
This function overloads the dereferencing operator*. It should return the info contained in the node.
intListIterator operator++()
This function overloads the pre-increment operator++. It should return an iterator that is pointing to the next node.
bool operator==(const intListIterator& right) const;
This function overloads the equality operator. Should return true if this iterator is equal to the iterator specified by right, otherwise it returns false.
bool operator!=(const intListIterator& right) const;
This function overloads the not equal to operator. Should return true if this iterator is not equal to the iterator specified by right, otherwise it returns false.
Private Helper Functions
You may define any private helper functions you deem useful, provided they do not affect the efficiency of the problem they are used to solve. Be careful making any function that must traverse the list to get to the node it will be working on. A private helper function that does this will almost always cause the function it is helping to become less efficient. You may lose points for that. For example, DO NOT make a function that returns the size of the list.
You MAY NOT define any other data fields, public or private, for this assignment.
What to Submit
In Canvas, submit the following files (case sensitive):
main.cpp (test harness)
IntNode.h
IntList.h
IntList.cpp
linkedListIterator.h
linkedListIterator.cpp
Code:
IntList.h
//Include libraries
#ifndef INTLIST_H
#define INTLIST_H
#include <iostream>
//Use namespace
using namespace std;
//Define structure
struct IntNode
{
//Define data
int data;
//Define next
IntNode *next;
//Initialize
IntNode(int data) : data(data), next(0) {}
};
//Define class
class IntList
{
//Define head
IntNode* head;
//Define tail
IntNode* tail;
//Define access speifier
public:
//Define constructor
IntList();
//Define destructor
~IntList();
//Define method
void display() const;
//Define method
void push_front(int value);
//Define method
void pop_front();
//Define method
bool empty() const;
//Define method
IntList(const IntList &cpy);
//Define method
IntList & operator=(const IntList &rhs);
//Define method
void push_back(int value);
//Define method
void clear();
//Define method
void selection_sort();
//Define method
void insert_ordered(int value);
//Define method
void remove_duplicates();
//Define method
friend ostream & operator<<(ostream &out, const IntList &rhs);
};
//End
#endif
IntList.cpp
//Include libraries
#include <iostream>
#include "IntList.h"
//Use namespace
using namespace std;
//Define method
IntList::IntList(): head(0), tail(0) {}
//Define destructor
IntList::~IntList()
{
while (!empty())
{
pop_front();
}
}
//Define method
void IntList::display() const
{
if(empty())
{
return;
}
else
{
IntNode* currentNode = head;
cout << currentNode->data;
while(currentNode->next != 0)
{
currentNode = currentNode->next;
cout << ' ' << currentNode->data;
}
}
}
//Define method
void IntList::push_front(int value)
{
IntNode* temp = new IntNode(value);
temp->next = head;
head = temp;
if(tail == 0)
{
tail = temp;
}
}
//Define method
void IntList::pop_front()
{
if(empty())
{
return;
}
else
{
IntNode* temp = head;
head = head->next;
delete temp;
}
if(head == 0)
{
tail = 0;
}
}
//Define method
bool IntList::empty() const
{
if(head == 0 && tail == 0)
{
return true;
}
return false;
}
//Define method
IntList::IntList(const IntList &cpy)
{
head = 0;
tail = 0;
if(!cpy.empty())
{
IntNode* curr = cpy.head;
while(curr != 0)
{
push_back(curr->data);
curr = curr->next;
}
}
}
//Define method
IntList & IntList::operator=(const IntList &rhs)
{
if (this == &rhs)
{
return *this;
}
else if(rhs.empty())
{
head = 0;
tail = 0;
}
else
{
clear();
IntNode* curr = rhs.head;
while(curr != 0)
{
push_back(curr->data);
curr = curr->next;
}
}
return *this;
}
//Define method
void IntList::push_back(int value)
{
IntNode* temp = new IntNode(value);
if (empty())
{
head = temp;
tail = temp;
}
else
{
tail->next = temp;
tail = temp;
}
}
//Define method
void IntList::clear()
{
while (!empty())
{
pop_front();
}
}
//Define method
void IntList::selection_sort()
{
if (empty())
{
return;
}
else
{
IntNode* min = head;
int temp = 0;
for (IntNode* i = head; i->next != 0; i = i->next)
{
min = i;
for(IntNode* j = i->next; j != 0; j = j->next)
{
if (min->data > j->data)
{
min = j;
}
}
temp = i->data;
i->data = min->data;
min->data = temp;
}
}
}
//Define method
void IntList::insert_ordered(int value)
{
if(empty())
{
push_front(value);
}
else if (value <= head->data)
{
push_front(value);
}
else if (value >= tail->data)
{
push_back(value);
}
else
{
IntNode* prev = head;
IntNode* curr = head->next;
IntNode* temp = new IntNode(value);
while(curr != 0)
{
if(value < curr->data)
{
prev->next = temp;
temp->next = curr;
return;
}
prev = prev->next;
curr = curr->next;
}
}
}
//Define method
void IntList::remove_duplicates()
{
if(empty() || head == tail)
{
return;
}
else
{
IntNode* prev = 0;
for(IntNode* i = head; i != 0; i = i->next)
{
prev = i;
for(IntNode* j = i->next; j != 0; j = prev->next)
{
if(i->data == j->data)
{
if (j == tail)
{
delete j;
tail = prev;
tail->next = 0;
if (head == tail)
{
return;
}
}
else
{
prev->next = j->next;
delete j;
}
}
else
{
prev = prev->next;
}
}
cout << "J LOOPed" << endl;
}
}
}
//Define method
ostream & operator<<(ostream &out, const IntList &rhs)
{
if(rhs.empty())
{
return out;
}
else
{
IntNode* currentNode = rhs.head;
out << currentNode->data;
while(currentNode->next != 0)
{
currentNode = currentNode->next;
out << ' ' << currentNode->data;
}
}
return out;
}
Main.cpp
//Include libraries
#include "IntList.h"
#include <iostream>
//Use namespace
using namespace std;
//Define main
int main()
{
//Display message
cout << "Enter a test number(1-5): ";
//Declare variable
int test;
//Store value
cin >> test;
//New line
cout << endl;
//If test is 1
if (test == 1)
{
cout << "\nlist1 constructor called";
IntList list1;
cout << "\npushfront 10";
list1.push_front( 10 );
cout << "\npushfront 20";
list1.push_front( 20 );
cout << "\npushfront 30";
list1.push_front( 30 );
cout << "\nlist1: ";
list1.display();
cout << "\npop";
list1.pop_front();
cout << "\nlist1: ";
list1.display();
cout << "\npop";
list1.pop_front();
cout << "\nlist1: ";
list1.display();
cout << "\npop";
list1.pop_front();
cout << "\nlist1: ";
list1.display();
cout << endl;
}
//If test is 1
if (test == 1)
{
cout << "list1 destructor called" << endl;
}
//If test is 2
if (test == 2)
{
cout << "\nlist2 constructor called";
IntList list2;
cout << "\npushback 10";
list2.push_back( 10 );
cout << "\npushback 20";
list2.push_back( 20 );
cout << "\npushback 30";
list2.push_back( 30 );
cout << "\nlist2: ";
list2.display();
cout << "\npop";
list2.pop_front();
cout << "\nlist2: ";
list2.display();
cout << "\npop";
list2.pop_front();
cout << "\nlist2: ";
list2.display();
cout << "\npop";
list2.pop_front();
cout << "\nlist2: ";
list2.display();
cout << endl;
}
//If test is 2
if (test == 2)
{
cout << "list2 destructor called" << endl;
}
//If test is 3
if (test == 3)
{
cout << "\nlist3 constructor called";
IntList list3;
cout << "\npushfront 1";
list3.push_front( 1 );
cout << "\npushfront 2";
list3.push_front( 2 );
cout << "\npushfront 3";
list3.push_front( 3 );
cout << "\nlist3: ";
list3.display();
cout << "\nselection_sort()";
list3.selection_sort();
cout << "\nlist3: ";
list3.display();
cout << "\npop";
list3.pop_front();
cout << "\npop";
list3.pop_front();
cout << "\npop";
list3.pop_front();
cout << "\nlist3: ";
list3.display();
cout << "\nselection_sort()";
list3.selection_sort();
cout << "\nlist3: ";
list3.display();
cout << "\npushfront 10";
list3.push_front( 10 );
cout << "\nselection_sort()";
list3.selection_sort();
cout << "\nlist3: ";
list3.display();
cout << "\npushfront 20";
list3.push_front( 20 );
cout << "\nlist3: ";
list3.display();
cout << "\nselection_sort()";
list3.selection_sort();
cout << "\nlist3: ";
list3.display();
cout << endl;
}
//If test is 3
if (test == 3)
{
cout << "list3 destructor called" << endl;
}
//If test is 4
if (test == 4)
{
cout << "\nlist4 constructor called";
IntList list4;
cout << "\ninsert 2";
list4.insert_ordered( 2 );
cout << "\ninsert 1";
list4.insert_ordered( 1 );
cout << "\ninsert 3";
list4.insert_ordered( 3 );
cout << "\nlist4: ";
list4.display();
cout << "\ninsert 5";
list4.insert_ordered( 5 );
cout << "\nlist4: ";
list4.display();
cout << "\ninsert 4";
list4.insert_ordered( 4 );
cout << "\nlist4: ";
list4.display();
cout << "\ninsert 6";
list4.insert_ordered( 6 );
cout << "\nlist4: ";
list4.display();
cout << "\ninsert 7";
list4.insert_ordered( 7 );
cout << "\nlist4: ";
list4.display();
cout << "\ninsert 11";
list4.insert_ordered( 11 );
cout << "\nlist4: ";
list4.display();
cout << "\ninsert 9";
list4.insert_ordered( 9 );
cout << "\nlist4: ";
list4.display();
cout << "\ninsert 15";
list4.insert_ordered( 15 );
cout << "\nlist4: ";
list4.display();
cout << "\ninsert 25";
list4.insert_ordered( 25 );
cout << "\nlist4: ";
list4.display();
cout << endl;
}
//If test is 4
if (test == 4)
{
cout << "list4 destructor called" << endl;
}
//If test is 5
if (test == 5)
{
cout << "\nlist5 constructor called";
IntList list5;
cout << "\npushfront 1";
list5.push_front( 1 );
cout << "\npushfront 2";
list5.push_front( 2 );
cout << "\npushfront 1";
list5.push_front( 1 );
cout << "\npushfront 3";
list5.push_front( 3 );
cout << "\nlist5: ";
list5.display();
cout << "\nremove_duplicates()";
list5.remove_duplicates();
cout << "\nlist5: ";
list5.display();
cout << "\npushfront 1";
list5.push_front( 1);
cout << "\nlist5: ";
list5.display();
cout << "\nremove_duplicates()";
list5.remove_duplicates();
cout << "\nlist5: ";
list5.display();
cout << "\npushfront 2";
list5.push_front( 2 );
cout << "\nlist5: ";
list5.display();
cout << "\nremove_duplicates()";
list5.remove_duplicates();
cout << "\nlist5: ";
list5.display();
cout << "\npushfront 2";
list5.push_front( 2);
cout << "\nlist5: ";
list5.display();
cout << "\nremove_duplicates()";
list5.remove_duplicates();
cout << "\nlist5: ";
list5.display();
cout << "\npushfront 2";
list5.push_front( 2 );
cout << "\npushfront 2";
list5.push_front( 2 );
cout << "\nlist5: ";
list5.display();
cout << "\nremove_duplicates()";
list5.remove_duplicates();
cout << "\nlist5: ";
list5.display();
cout << "\nremove_duplicates()";
list5.remove_duplicates();
cout << "\nlist5: ";
list5.display();
cout << "\npop";
list5.pop_front();
cout << "\npop";
list5.pop_front();
cout << "\npush_front(3)";
list5.push_front(3);
cout << "\nlist5: ";
list5.display();
cout << "\nremove_duplicates()" << flush;
list5.remove_duplicates();
cout << "\nlist5: " << flush;
list5.display();
cout << "\npush_front(3)";
list5.push_front(3);
cout << "\npush_front(3)";
list5.push_front(3);
cout << "\nlist5: ";
list5.display();
cout << "\nremove_duplicates()" << flush;
list5.remove_duplicates();
cout << "\nlist5: " << flush;
list5.display();
cout << "\nremove_duplicates()" << flush;
list5.remove_duplicates();
cout << "\nlist5: " << flush;
list5.display();
cout << "\npop";
list5.pop_front();
cout << "\nlist5: ";
list5.display();
cout << "\nremove_duplicates()" << flush;
list5.remove_duplicates();
cout << "\nlist5: " << flush;
list5.display();
cout << endl;
}
//If test is 5
if (test == 5)
{
cout << "list5 destructor called" << endl;
}
//Pause console window
system("pause");
//Return
return 0;
}
IntList Recursion Assignment Specifications: You will add some additional recursive functions to your IntList class as...
(C++) You are tasked with implementing a recursive function void distanceFrom(int key) on the IntList class (provided). The function will first search through the list for the provided key, and then, recursively, change all previous values in the list to instead be their distance from the node containing the key value. Do not update the node containing the key value or any nodes after it. If the key does not exist in the list, each node should contain its distance...
You are tasked with implementing a recursive function void distanceFrom(int key) on the IntList class (provided). The function will first search through the list for the provided key, and then, recursively, change all previous values in the list to instead be their distance from the node containing the key value. Do not update the node containing the key value or any nodes after it. If the key does not exist in the list, each node should contain its distance from...
C++ LinkedList I need the code for copy constructor and assignment operator #include <iostream> #include <string> using namespace std; typedef string ItemType; struct Node { ItemType value; Node *next; }; class LinkedList { private: Node *head; // You may add whatever private data members or private member functions you want to this class. void printReverseRecursiveHelper(Node *temp) const; public: // default constructor LinkedList() : head(nullptr) { } // copy constructor LinkedList(const LinkedList& rhs); // Destroys all the dynamically allocated memory //...
Java Write the function void insertAtTail (int v). Don’t add any class variables to the List class. Here are the class definitions of Node and List that implement a linked list. class Node {private Node next; private int key; Node (Node nxt, int keyValue);//constructor Node getNext(); int getKey(); void putNext(Node nxt);} class List {//assume the class does not use a dummy Node private Node head; List ();//constructor boolean exists (int ky);//returns true if v is in the list void insertAtHead(int...
Below is the given code of implementation: #include <string> #include <iostream> #include <list> #include <cassert> using namespace std; class List; class Iterator; class Node { public: /* Constructs a node with a given data value. @param s the data to store in this node */ Node(string s); /* Destructor */ ~Node() {} private: string data; Node* previous; Node* next; friend class List; friend class Iterator; }; class List { public: /** Constructs an empty list. */ List(); /* Destructor. Deletes...
C++ Implement a templated class list and listnode. You may add methods/functions as you see fit. Test these classes. I have left all of the implementation as an exercise for you. template< class NODETYPE > class List; // forward declaration template<class NODETYPE> class ListNode { friend class List< NODETYPE >; // make List a friend public: ListNode( const NODETYPE &newData); // copy constructor NODETYPE getData() const; // return data in the node private: NODETYPE data; // data ListNode< NODETYPE > *nextPtr; // next node...
1. void raw_push_front(const Object &x) { // insert x at the head of the list *without* using the iterator classes // Place your code here. } 2. void raw_push_back(const Object &x) { // insert x at the tail of the list *without* using the iterator classes // Place your code here. } #ifndef LIST_H #define LIST_H #include <algorithm> using namespace std; template<typename Object> class List { private: // The basic doubly linked list node. // Nested inside of List, can...
C++ Implement a class template for a LinkedList.(doubly linked). Also, your class will have a tailPtr in addition to a headPtr along with methods to get, set, insert and remove values at either end of the list. Call these getFirst, getLast, setFirst, setLast, insertFirst, insertLast, removeFirst, removeLast. Don't forget, you also need a copy constructor and destructor plus getLength, isEmpty and clear methods. Overload the stream insertion operator as a friend function which outputs the list in format { 1,...
Language: C++ Complete this function 1.Object &raw_front() { // Return the element at the front of the list *without* using the iterator classes // (You may assume the list is not empty) // Place your code here. Code: #ifndef LIST_H #define LIST_H #include using namespace std; template class List { private: // The basic doubly linked list node. // Nested inside of List, can be public // because the Node is itself private struct Node { Object data; Node *prev;...
I have the following c++ data structures assignment: Copy Constructors, Destructors, and Assignment Operators An understanding of how to implement copy constructors, destructors, and assignment operators is essential when working with data structures using dynamic memory allocation. Failure to implement these methods correctly can and probably will result in memory leaks. In this project, you are provided with a working implementation of a doubly-linked list in which the copy constructor, destructor, and assignment operator methods are not complete. To complete...