i have a couple of should be simple linked list questions one of which is how to make it insert in a sorted fashion i have a way i think should work but it doesnt i can post the code if needed. also i have to delete the last n amount of items of the list i also have some code that i think should work but it will delete the last n and for some reason an extra item and i cant figure out why any ideas

``````bool LinkedList::insert(elementType elt)
{
int num = elt;
nodePtr insertPtr = getNode(elt);
if (insertPtr == NULL)
return false;
else
{/*
while (currPtr->item < elt)
{
prevPtr = currPtr;
currPtr = currPtr->next;
}
insertPtr = currPtr;
prevPtr->next = insertPtr;*/
}
return true;
}

{
for (int i = 0; i < (size() - n); i++)
{
currPtr = currPtr->next;
}
while (currPtr != NULL)
{
prevPtr = currPtr;
currPtr = currPtr->next;
delete prevPtr;
}
}``````

line 5: wrong data type. Should be elementType, not int.

move lines 3, 4 and 5 down into the if statement. No point in doing that extra work when head is a NULL pointer.

line 20: at this point you need to allocate a new node to insert into the linked list. You didn't post getNode() so I'll guess that it just returns the node where the new node should be inserted.

``````nodeptr NewNode = new node; // I'm assuming the underlying structure is named "node"
NewNode->data = elt;
NewNode->next = insertPtr->nex;
insertPtr->NewNode;``````

line 30: What will that do if the value of n is greater than size()?

The delete function has a memory leak because it doesn't destory the nodes that are removed from the linked list.

``````while( currPtr != NULL)
{
nodePtr hold = currPtr;
currPtr = currPtr->next;
delete hold;
}``````

as of line 30 in my driver function i dont allow for anything greather then size and i have a function that creates a new node insertPtr is the new node with the date already in it and the int part isnt there anymore i dont know why i put it there and the delete function im not worried about the leaks right now ill deal with that when i need to but can you tell why its messing up what happens is when i try to display them it displays an extra one that is obviously not part of the list cause its junk value

this is the insert function now

``````bool LinkedList::insert(elementType elt)
{
nodePtr newNode = getNode(elt);
if (newNode == NULL)
return false;
else
{
while (currPtr->item < newNode->item)
{
currPtr = currPtr->next;
}
newNode->next = currPtr->next;
currPtr ->next = newNode;
}
return true;
}``````

Post the whole program -- I'm not going to guess any more.

alright.. this is the driver file

``````#include <iostream>
#include <fstream>
#include <string>
using namespace std;

struct objects;
void getChoice(char &choice);

struct objects
{
};

int main()
{
char choice;
objects list;
cout << "Welcome to the Linked List Program!\n\n";
do
{
getChoice(choice);
}
while ((choice != 'q') && (choice != 'Q'));
return 0;
}
// dispays menu for user to pick from
{
cout << "A) Load list from file\n"
<< "B) Delete first N elements\n"
<< "C) Delete last N elements\n"
<< "D) Delete all elements\n"
<< "E) Copy First Half\n"
<< "F) Copy Last Half\n"
<< "G) Display Primary List\n"
<< "H) Display Secondary List\n"
<< "Q) Quit\n\n";
}
void getChoice(char &choice)
{
cin >> choice;
}

{
switch(choice)
{
case 'A':
case 'a':
system("cls");
break;
case 'B':
case 'b':
system("cls");
deleteFirstN(list.primary);
break;
case 'C':
case 'c':
system("cls");
deleteLastN(list.primary);
break;
case 'D':
case 'd':
system("cls");
list.primary.deleteList();
break;
case 'E':
case 'e':
system("cls");
list.primary.copyFirstHalf(list.secondary);
break;
case 'F':
case 'f':
system("cls");
list.primary.copyLastHalf(list.secondary);
break;
case 'G':
case 'g':
system("cls");
cout << endl << list.primary << endl << endl;
break;
case 'H':
case 'h':
system("cls");
cout << endl << list.secondary << endl << endl;
break;
case 'Q':
case 'q':
system("cls");
cout << "Thank you for using the Linked List Program\n\n";
break;
default:
cout << "Invalid Response Pick one of the menu items \n";
break;
}
}
// error traps for bad file names
{
string fileName;
ifstream inFile;
cout << "Enter the name of the input file: ";
cin >> fileName;
inFile.open(fileName.c_str());
while(!inFile.good())
{
inFile.clear(ios::goodbit);
cout << "The file name '" << fileName << "' does not exist.\n"
<< "Enter the name of the input file: ";
cin >> fileName;
inFile.open(fileName.c_str());
}
list.deleteList();
while(!inFile.eof())
{
inFile >> list;
}
inFile.close();
return;
}
// asks for number of first number of things user wants to delete
// then deletes that number of items
{
int num;
cout << endl << "How many items would you like to delete from the begginning (0-"
<< list.size() << "): ";
cin >> num;
while ((num < 0) || ( num > list.size()))
{
cout << "Enter a valid number: ";
cin >> num;
}
list.deleteFirstN(num);
}
// function asks user how many nodes they would like to delete off the end off the list
{
int num;
cout << endl << "How many items would you like to delete from the end (0-"
<< list.size() << "): ";
cin >> num;
if (( num <= 0 ) || ( num > list.size()))
{
cout << endl << "Cannot delete that amount!\n\n";
return;
}
list.deleteLastN(num);
}``````

this is the definition file

``````#ifndef LINKED_LIST_H
#define LIKED_LIST_H
#include <string>
using namespace std;
typedef string elementType;
struct node;
typedef node* nodePtr;
struct node
{
elementType item;
nodePtr next;
};

{
public:
// Constructors and destructor
// Member functions
int size();
bool insert(elementType elt); // needs work
bool remove(elementType elt);
bool retrieve(elementType elt, int &position);
elementType& operator [ ] (int position);
friend istream& operator >>
friend ostream& operator <<
void deleteList(); //done
void deleteFirstN(int n); // done
void deleteLastN(int n); // needs work
private:
// Data member
// Member function
nodePtr getNode(elementType elt);
};
#endif``````

implementation file

``````// Class implementation file: linkedList.cpp //
#include <cassert>
using namespace std;
// The default constructor merely sets up an empty LinkedList. //
{
}
// The copy constructor makes a deep copy of the parameterized LinkedList. //
{
nodePtr currPtr, thisCurrPtr, thisPrevPtr;
else
{
while (currPtr != NULL)
{
thisCurrPtr = getNode(currPtr->item);
thisPrevPtr->next = thisCurrPtr;
thisPrevPtr = thisCurrPtr;
currPtr = currPtr->next;
}
}
}
// The assignment operator makes the current
// object a copy of the parameterized object
{
nodePtr currPtr, thisCurrPtr, thisPrevPtr;
return *this;
else
{
while (currPtr != NULL)
{
thisCurrPtr = getNode(currPtr->item);
thisPrevPtr->next = thisCurrPtr;
thisPrevPtr = thisCurrPtr;
currPtr = currPtr->next;
}
}
return *this;
}
// The destructor systematically deletes //
// every node in the LinkedList.         //
{
nodePtr currPtr;
{
currPtr->next = NULL;
delete currPtr;
}
}
// The size member function returns the //
// number of nodes in the LinkedList.   //
{
int count = 0;
while (currPtr != NULL)
{
currPtr = currPtr->next;
count++;
}
return count;
}
// The insert member function creates a new    //
// node containing the parameterized value,    //
// A boolean value indicating whether the      //
// insertion worked is returned.               //
{
nodePtr newNode = getNode(elt);
if (newNode == NULL)
return false;
else
{
while (currPtr->item < newNode->item)
{
currPtr = currPtr->next;
}
newNode->next = currPtr->next;
currPtr ->next = newNode;
}
return true;
}
// The remove member function locates the first occurrence of the parameterized //
// value in the LinkedList and detaches it from the LinkedList.  A boolean      //
// value indicating whether the removal worked is returned.                     //
{
nodePtr prevPtr = NULL;
bool foundIt = false;
while ((!foundIt) && (currPtr != NULL))
{
if (currPtr->item == elt)
foundIt = true;
else
{
prevPtr = currPtr;
currPtr = currPtr->next;
}
}
if (foundIt)
{
if (prevPtr == NULL)
else
prevPtr->next = currPtr->next;
delete currPtr;
}
return foundIt;
}
// The retrieve member function locates the first occurrence of the parameterized  //
// value in the LinkedList and sets the parameterized nodePtr to its memory        //
// location.  A boolean value indicating whether the retrieval worked is returned. //
{
bool foundIt = false;
position = 0;
while ((!foundIt) && (currPtr != NULL))
{
position++;
if (currPtr->item == elt)
foundIt = true;
else
currPtr = currPtr->next;
}
return foundIt;
}

// The subscript operator retrieves the element in the parameterized position //
// of the LinkedList.  Note that the starting index for this operator is one. //
elementType& LinkedList::operator [ ] (int position)
{
assert((position > 0) && (position <= size()));
for (int i = 1; i < position; i++)
currPtr = currPtr->next;
return currPtr->item;
}
// The input operator reads all values of type          //
// elementType from the parameterized input stream,     //
// inserting them into the parameterized LinkedList,    //
// until the input stream has been completely depleted. //
istream& operator >> (istream &sourceFile, LinkedList &list)
{
elementType nextElt;
sourceFile >> nextElt;
while (!sourceFile.eof())
{
list.insert(nextElt);
sourceFile >> nextElt;
}
return sourceFile;
}

// The output operator outputs the values in the LinkedList, //
// each on a separate output line in the parameterized       //
// output stream, starting with the head element.            //
ostream& operator << (ostream &destFile, const LinkedList &list)
{
nodePtr ptr;
for (ptr = list.head; ptr != NULL; ptr = ptr->next)
destFile << ptr->item << endl;
return destFile;
}

// The getNode member function creates and returns //
// a new nodePtr, pointing to a node with the      //
// parameterized value as its item member and with //
// NULL as the value of its next member.           //
{
nodePtr temp = new node;
if (temp != NULL)
{
temp->item = elt;
temp->next = NULL;
}
return temp;
}
// deletes the entire linked list
// essicially does the same job as a destructor
{
nodePtr currPtr;
{
currPtr->next = NULL;
delete currPtr;
}
}
// delets the first N items of Linked list
{
for (int i = 0; i < n; i++)
{
delete currPtr;
}
}
// deletes the last N items of a linked List
{
nodePtr prevPtr;
for (int i = 0; i < (size() - n); i++)
{
currPtr = currPtr->next;
}
while (currPtr != NULL)
{
prevPtr = currPtr;
currPtr = currPtr->next;
delete prevPtr;
}
}
// copys the first half of an linked list parameter
// into the current linked list
{
int half;
int i = 0;
if (size() % 2 == 0)
half = size() / 2;
else
half = (size() / 2)+1;
return;
{
while(i < half)
{
list.insert(currPtr->item);
currPtr = currPtr->next;
i++;
}
}
else
{
list.deleteList();
while(i < half)
{
list.insert(currPtr->item);
currPtr = currPtr->next;
i++;
}
}
}
// copys the last half of a linked list parameter
// into the current linked list
{
int half;
int i = 0;
half = size() / 2;
{
while ( i < half)
{
currPtr = currPtr->next;
i++;
}
while (currPtr != NULL)
{
list.insert(currPtr->item);
currPtr = currPtr->next;
}
}
else
{
list.deleteList();
while ( i < half)
{
currPtr = currPtr->next;
i++;
}
while ( currPtr != NULL)
{
list.insert(currPtr->item);
currPtr = currPtr->next;
}
}
}``````

The while statement on line 96 isn't quite right. It needs to check for end of list, such as the value of elt is greater than any value in the list. In that case the loop will continue beyond the end lf the linked list.

it still doesnt want to insert right i mean correct me if im wrong the code looks like it shoould work apart from the not checking for null which i fixed but it just wont insert for some reason maybe i need to overload the < operator but doesnt the string class already have that since i am using strings

The operator >> isn't quite right. A common problem of using eof() incorrectly. The way you have it coded the function will read the last line twice and insert the same number twice into the list

``````istream& operator >> (istream &sourceFile, LinkedList &list)
{
elementType nextElt;
//   sourceFile >> nextElt;
//   while (!sourceFile.eof())
//   {
//      list.insert(nextElt);
//      sourceFile >> nextElt;
//   }
while( sourceFile >> nextElt )
list.insert(nextElt);
return sourceFile;
}``````

Next: insert

``````bool LinkedList::insert(elementType elt)
{
nodePtr newNode = getNode(elt);
if (newNode == NULL)
return false;
else
{
nodePtr prevPtr = NULL;
while (currPtr && currPtr->item < newNode->item)
{
prevPtr = currPtr;
currPtr = currPtr->next;
}
//
if( currPtr == NULL)
// If at end of list, just add the new node
// to the tail of the list
{
prevPtr->next = newNode;
}
else
{
newNode->next = currPtr;
if( prevPtr == NULL)
// If at the head of the list,
// of the list
else
// insert the new node
// somewhere in the middle of the list
prevPtr->next = newNode;
}
}
return true;
}``````

worked like a charm ...have any answer for the deleteLastN cause its still messed up i made a couple of tweaks but still screwed

deleting the last node incorrectly

``````void LinkedList::deleteLastN(int n)
{
nodePtr prevPtr;
int length = size() - n - 1;
// keep the value returned by size() in a local
// variable so that it doesn' have to be recalculated
// on every loop iteration.
for (int i = 0; i < length; i++)
{
currPtr = currPtr->next;
}
prevPtr = currPtr;
currPtr = currPtr->next;
prevPtr->next = NULL;
while (currPtr != NULL)
{
prevPtr = currPtr;
currPtr = currPtr->next;
delete prevPtr;
}
}``````
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.