I have to write functions for a Linked List in c++. I am having trouble with a f
ID: 3796903 • Letter: I
Question
I have to write functions for a Linked List in c++. I am having trouble with a few functions.
The addBack function, which is suppose to add a new data item to the end of the list. I have included the code I have so far. It does not work and sends me into an infinite loop.
void addBack(node * & start, int value)
{
node * walker = new node;
walker = start;
while (walker != nullptr)
{
walker = walker->next;
}
walker->data = value;
walker->next = nullptr;
start->next = walker;
}
The equal function, which will return true if two lists are equal and false if they are not. I have included the code I have written, but it sends me into an infinite loop.
bool equal(const node * left, const node * right)
{
const node * walker = left;
const node * roamer = right;
if (length(left) != length(right))
{
return false;
}
if (walker->data == roamer->data)
{
while (left->next != nullptr)
{
walker = walker->next;
roamer = roamer->next;
}
return true;
}
else
{
return false;
}
}
I also do not know how to write the max or min functions with a Linked List.
int max(const node *start)
{
}
int min(const node * start)
{
}
Here is the code for the function declarations and the main portion. I have written all the other functions. Thanks for the help.
#include<iostream>
#include <string>
using namespace::std;
const int NUMBER_NAMES = 19;
const string names[NUMBER_NAMES] = { " printForward"," printReverse"," length"," lengthR"," sum"," max"," min"," countValueOccurences"," addFront",
" addBack","removeFront","removeBack","clear","isSorted","isSortedR","hasDuplicate","equal","equalR","search" };
struct node
{
int data;
node * next;
};
void printForward(const node *);
void printReverse(const node *);
int length(const node *); // count the number of nodes in the linked list
int lengthR(const node *);
int sum(const node *); // sum the data values in the linked list
int max(const node *); // assume linked list is not empty
int min(const node *); // assume linked list is not empty
int countValueOccurences(const node *, int valueToTally);
void addFront(node * &, int);
void addBack(node * &, int);
void removeFront(node * &); // if the list is empty, just return
void removeBack(node * &); // if the list is empty, just return
void clear(node * &); // return all heap memory
bool isSorted(const node *); // check if in ascending order, ok to have adjacent equal values
bool isSortedR(const node *);
bool hasDuplicate(const node *);
bool equal(const node *, const node *); // same number of members and all corresponding members are equal
bool equalR(const node *, const node *);
const node * search(const node *, int); // return the addres of the first node found holding the dat value, returnn nullptr if not found
// Utility functions written by instructor
void buildSpecificLinkedList(node * & start);
void buildFromArray(node * & start, const int * theArray, int howMany);
void returnMemory(node * & start);
int menu();
void main()
{
node * testLL = nullptr;
node * testLL2 = nullptr;
node * testLL3 = nullptr;
node * testLL4 = nullptr;
int testData[10] = { 8,2,9,6,2,12,2,6,1,7 };
int testData2[10] = { 8,2,9,6,2,12,2,6,1,7 };
int testData3[10] = { 8,3,4,5,8,51,4,0,9,7 };
int testData4[5] = { 1, 3, 5, 3, 5 };
buildFromArray(testLL, testData, 10);
buildFromArray(testLL2, testData2, 10);
buildFromArray(testLL3, testData3, 10);
buildFromArray(testLL4, testData4, 5);
int choice = 0;
while (choice != -1)
{
choice = menu();
switch (choice) {
case 0: cout << "testing " << names[choice] << endl;
printForward(testLL);
break;
case 1: cout << "testing " << names[choice] << endl;
printReverse(testLL);
break;
case 2: cout << "testing " << names[choice] << endl;
cout << "length is " << length(testLL) << endl;
break;
case 3: cout << "testing " << names[choice] << endl;
cout << "length is " << lengthR(testLL) << endl;
break;
case 4: cout << "testing " << names[choice] << endl;
cout << "sum is " << sum(testLL) << endl;
break;
case 5: cout << "testing " << names[choice] << endl;
cout << "max is " << max(testLL) << endl;
break;
case 6: cout << "testing " << names[choice] << endl;
cout << "min is " << min(testLL) << endl;
break;
case 7: cout << "testing " << names[choice] << endl;
int valueToCount;
cout << "Enter value to tally ";
cin >> valueToCount;
cout << "tally is " << countValueOccurences(testLL, valueToCount) << endl;
break;
case 8: cout << "testing " << names[choice] << endl;
int valueToAddFront;
cout << "Enter the value to add at the front ";
cin >> valueToAddFront;
addFront(testLL, valueToAddFront);
break;
case 9: cout << "testing " << names[choice] << endl;
int valueToAddBack;
cout << "Enter the value to add at the back ";
cin >> valueToAddBack;
addBack(testLL, valueToAddBack);
break;
case 10: cout << "testing " << names[choice] << endl;
removeFront(testLL);
break;
case 11: cout << "testing " << names[choice] << endl;
removeBack(testLL);
break;
case 12: cout << "testing " << names[choice] << endl;
clear(testLL);
break;
case 13: cout << "testing " << names[choice] << endl;
cout << "is sorted " << isSorted(testLL) << endl;
break;
case 14: cout << "testing " << names[choice] << endl;
cout << "is sorted R " << isSortedR(testLL) << endl;
break;
case 15: cout << "testing " << names[choice] << endl;
cout << "has duplicate " << hasDuplicate(testLL) << endl;
break;
case 16: cout << "testing " << names[choice] << endl;
cout << "is equal " << equal(testLL, testLL2) << endl;
cout << "is equal " << equal(testLL, testLL3) << endl;
break;
case 17: cout << "testing " << names[choice] << endl;
// need code to test equarR
break;
case 18: cout << "testing " << names[choice] << endl;
int valueToSearchFor;
cout << "Enter value to search for ";
cin >> valueToSearchFor;
cout << "value found in node with address " << search(testLL, valueToSearchFor) << endl;
break;
default: cout << "Invalid choice" << endl;
break;
}; // end switch
} // end while
} // end main
Explanation / Answer
Here are four methods you asked for
void addBack(node * & start, int value)
{
node *walker = new node;
walker = start;
node *prev = walker;
while (walker != nullptr)
{
prev = walker;
walker = walker->next;
}
node *newNode = new node;
newNode->data = value;
newNode->next = nullptr;
prev->next = newNode;
}
bool equal(const node * left, const node * right)
{
const node * walker = left;
const node * roamer = right;
if (length(left) != length(right))
{
return false;
}
while (walker != nullptr && roamer != nullptr)
{
if (walker->data != roamer->data)
{
return false;
}
walker = walker->next;
roamer = roamer->next;
}
return true;
}
int max(const node *start)
{
const node * walker = start;
int m;
if (start != nullptr)
m = start->data;
else
return -1;
while (walker != nullptr)
{
if (walker->data > m)
{
m = walker->data;
}
walker = walker->next;
}
return m;
}
int min(const node * start)
{
const node * walker = start;
int m;
if (start != nullptr)
m = start->data;
else
return -1;
while (walker != nullptr)
{
if (walker->data < m)
{
m = walker->data;
}
walker = walker->next;
}
return m;
}
If they do not work please share your full code implementation so that I can compile and run program. Currently its based on logical code.