1) Based on the classes that we created in lecture named Node and LinkedList (wh

Question

1) Based on the classes that we created in lecture named Node and LinkedList (which we used to make a one-directional linked list) create a method called find which will return the 1st node object whose data value matches the parameter passed to the method

2) Also in class LinkedList, create a method called replace which will:

a) find a node whose value matches the first value passed as a parameter

b) remove that node

c) create a new node, with the second value that was passed as a parameter

d) insert that new node in that same place in the linked list where the other node was removed

***NOTE****

you MAY NOT make any changes to the Node class. you MAY NOT add a setData method.

**** To think about****

This replace method inserts the new node in the same place that the other node was deleted, however that might not be the correct place for this node (if we are keeping the list sorted). As a result you cannot call methods delete or insert here.

**********************

3) Create a method called sum that will traverse (travel through) all of the nodes in a linked list and output (JOptionPane or to the console) the sum of the integers off all of those nodes.

**********************

4) Create the methods find, delete and replace in class LinkedList2

Explanation / Answer

This is a list that does what you asked. List are difficult and best to start with a working list and alter as needed.

This file has a main.cpp, header.h

main.cpp*************************************************************************************************************

#include <iostream>

#include "header.h"

using namespace std;

int main()
{
// set list header to NULL
myList<int> *header = NULL, *currPtr;
for(int i = 0; i < 10; i++){InsertFront(header, i);}

cout << "myList has been created and pre-loaded with integers. This is a template "
"so you can use other data types. " << endl;
cout << "__________________________________________________" << endl;

//prints mylist
PrintList(header);
cout << "__________________________________________________" << endl;

// determines the size of the list
int sizeMyList;
sizeMyList = SizeList(header);
cout << "The size of myList is: " << sizeMyList << endl;
cout << "__________________________________________________" << endl;

// determines if there a match in the list with a user requested input
bool match;
int in;
cout << "Search the list, what are you looking for:" << endl;
cin >> in;
match = containList(header, in);
if (match)
cout << "There is a match within the list." << endl;
else
cout << "There was a not a match within the list." << endl;
cout << "__________________________________________________" << endl;

// adds to list if not already in list
bool added;
added = addList(header, 300);

if(!added){cout << "This was an unique value and was added to the list." << endl;}

//prints mylist
cout << "__________________________________________________" << endl;
cout << "The updated list: " << endl;
PrintList(header);
cout << "__________________________________________________" << endl;

cout << "This function will delete a element if it exists within the list." << endl;
bool del;
del = delList(header, 300);
if (del){cout << "A match was found and removed from the list."<<endl;}
cout << "The updated list: " << endl;
PrintList(header);
cout << "__________________________________________________" << endl;

cout << "COMPLETE" << endl;

return 0;
}

header.h************************************************************************************************************

#include <iostream>
#include <stdlib.h>
using namespace std;

template <class T>
class myList
{
private:
// next is the address of the following node
myList<T> *next;
public:
// the data is public
T data;

// constructor
myList (const T& item, myList<T>* ptrnext = NULL);

// destructor
~myList (void);

// list modification methods
void InsertAfter(myList<T> *p);
myList<T> *DeleteAfter(void);
void InsertFront(const T& item);

// obtain the address of the next node
myList<T> *NextmyList(void) const;

myList<T> *GetmyList(void) const;

void PrintList(myList<T> *p);

int SizeList(myList<T> *p);

bool containList(myList<T> *p, T&);

bool addList(myList<T> *p, T&);

bool delList(myList<T> *p, T&);
};

// constructor. initialize data and pointer members
template <class T>
myList<T>::myList(const T& item, myList<T>* ptrnext):data(item), next(ptrnext)
{}

// detructor
template <class T>
myList<T>::~myList(void)
{
cout << "Object is being deleted" << endl;
}

// return value of private member next
template <class T>
myList<T> *myList<T>::NextmyList(void) const
{
return next;
}

// insert a node p after the current one
template <class T>
void myList<T>::InsertAfter(myList<T> *p)
{
// p points to successor of the current node
// and current node points to p.
p->next = next;
next = p;
}

// delete the node following current and return its address
template <class T>
myList<T> *myList<T>::DeleteAfter(void)
{
// save address of node to be deleted
myList<T> *tempPtr = next;

// if there isn't a successor, return Null
if (next == NULL)
return NULL;

// current node points to successor of tempPtr.
next = tempPtr->next;

// return the pointer to the unlinked node
return tempPtr;
}

// allocate a node with data member item and pointer nextPtr
template <class T>
myList<T> *GetmyList(const T& item, myList<T> *nextPtr = NULL)
{
myList<T> *newmyList;

// allocate memory while passing item, NextPtr to constructor. terminate program if allocation fails
newmyList = new myList<T>(item, nextPtr);
if (newmyList == NULL)
{
cerr << "Memory allocation failure" << endl;
exit(1);
}
return newmyList;
}

// insert item at the front of list
template <class T>
void InsertFront(myList<T>* & header, T item)
{
// allocate new node so it points to original list header
// update the list header
header = GetmyList(item, header);
}

// print a linked list
template <class T>
void PrintList(myList<T> *header)
{
myList<T> *currPtr = header;

while(currPtr != NULL)
{
cout << currPtr ->data << endl;
currPtr = currPtr->NextmyList();
}
}

// determine the size of the headerer
template <class T>
int SizeList(myList<T> *header)
{
myList<T> *currPtr = header;
int counter = 0;

while(currPtr != NULL)
{
counter++;
currPtr = currPtr->NextmyList();
}
return counter;
}

// determine if a object is within the list
// returns false if there is not a match
template <class T>
bool containList(myList<T> *header, T x)
{
bool isMatch = false;
myList<T> *currPtr = header;

while(currPtr != NULL)
{

if(currPtr->data == x)
{
isMatch = true;
return isMatch;
}
currPtr = currPtr->NextmyList();
}
return isMatch;
}

// determine if a object is within the list and if not adds it
template <class T>
bool addList(myList<T>* &header, T x)
{
bool match = 0;
match = containList(header, x);

if(match)
cout << "No additions already exists" << endl;
else
{
InsertFront(header, x);
}

return match;
}

// determine if a object is within the list and if not adds it
template <class T>
bool delList(myList<T>* &header, T x)
{
myList<T> *currPtr = header, *prevPtr = NULL;
bool match = 0;
match = containList(header, x);

if(currPtr == NULL)
return match;

while (currPtr != NULL && currPtr->data != x)
{
// advance currPtr so prevPtr trails it
prevPtr = currPtr;
currPtr = currPtr->NextmyList();
}

// if currPtr != NULL, key located at currPtr.
if (currPtr != NULL)
{
// prevPtr == NULL means match at front myList
if (prevPtr == NULL)
header = header->NextmyList();
else
// match 2nd or subsequent myList
prevPtr->DeleteAfter();

// dispose of the myList
delete currPtr;
}
return match;
}

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.