linked list questions

[Ryan61343]

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)
{
	nodePtr currPtr = head;
	nodePtr prevPtr = head;
	int num = elt;
    nodePtr insertPtr = getNode(elt);
    if (insertPtr == NULL)
       return false;
    if (head == NULL)
       head = insertPtr;
    else
    {/*
		while (currPtr->item < elt)
	    {
			prevPtr = currPtr;
			currPtr = currPtr->next;
	    }
	    insertPtr = currPtr;
	    prevPtr->next = insertPtr;*/
		insertPtr->next = head;
		head = insertPtr;
    }
    return true;
}

void LinkedList::deleteLastN(int n)
{
	nodePtr currPtr = head;
	nodePtr prevPtr = head;
	for (int i = 0; i < (size() - n); i++)
	{
		currPtr = currPtr->next;
	}
	while (currPtr != NULL)
	{
		prevPtr = currPtr;
		currPtr = currPtr->next;
		delete prevPtr;
	}
}

[Ancient Dragon]

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;
}

[Ryan61343]

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

[Ryan61343]

this is the insert function now

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

[Ancient Dragon]

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

[Ryan61343]

alright.. this is the driver file

#include <iostream>
#include <fstream>
#include <string>
#include "linked_list.h"
using namespace std;

struct objects;
void displayMenu();
void getChoice(char &choice);
void menuSwitch(char choice, objects &list);
void loadPrimary(LinkedList &list);
void deleteFirstN(LinkedList &list);
void deleteLastN(LinkedList &list);

struct objects
{
	LinkedList primary;
	LinkedList secondary;
};

int main()
{
	char choice;
	objects list;
	cout << "Welcome to the Linked List Program!\n\n";
	do
	{
		displayMenu();
		getChoice(choice);
		menuSwitch(choice, list);
	}
	while ((choice != 'q') && (choice != 'Q'));
	return 0;
}
// dispays menu for user to pick from
void displayMenu()
{
	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";
}
// asks user for input
void getChoice(char &choice)
{
	cout << "Your Choice: ";
	cin >> choice;
}

void menuSwitch(char choice, objects &list)
{
	switch(choice)
	{
	case 'A':
	case 'a':
		system("cls");
		loadPrimary(list.primary);
		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;
	}
}
// loads the linked list from a file of your choosing
// error traps for bad file names
void loadPrimary(LinkedList &list)
{
	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
void deleteFirstN(LinkedList &list)
{
	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
void deleteLastN(LinkedList &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;
};

class LinkedList
{
   public:
      // Constructors and destructor
      LinkedList();
      LinkedList(const LinkedList &list);
      ~LinkedList();
      // Member functions
      int size();
      bool insert(elementType elt); // needs work
      bool remove(elementType elt);
      bool retrieve(elementType elt, int &position);
      elementType& operator [ ] (int position);
      LinkedList& operator = (const LinkedList &list);		
      friend istream& operator >> 
            (istream &sourceFile, LinkedList &list);
      friend ostream& operator << 
            (ostream &destFile, const LinkedList &list);
	  //added functions
	  void deleteList(); //done
	  void deleteFirstN(int n); // done
	  void deleteLastN(int n); // needs work 
	  void copyFirstHalf(LinkedList &list); // done
	  void copyLastHalf(LinkedList &list); // done
   private:
      // Data member
      nodePtr head;
      // Member function
      nodePtr getNode(elementType elt);
};
#endif

implementation file

// Class implementation file: linkedList.cpp //
#include "linked_list.h"
#include <cassert>
using namespace std;
// The default constructor merely sets up an empty LinkedList. //
LinkedList::LinkedList()
{
   head = NULL;
}
// The copy constructor makes a deep copy of the parameterized LinkedList. //
LinkedList::LinkedList(const LinkedList &list)
{
   nodePtr currPtr, thisCurrPtr, thisPrevPtr;
   if (list.head == NULL)
      head = NULL;
   else
   {
      head = getNode(list.head->item);
      thisPrevPtr = head;
      currPtr = list.head->next;
      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 
LinkedList& LinkedList::operator = (const LinkedList &list)
{
   nodePtr currPtr, thisCurrPtr, thisPrevPtr;
   if(head == list.head)
      return *this;
   (*this).~LinkedList();
   if (list.head == NULL)
      head = NULL;
   else
   {
      head = getNode(list.head->item);
      thisPrevPtr = head;
      currPtr = list.head->next;
      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.         //
LinkedList::~LinkedList()
{
   nodePtr currPtr;
   while (head != NULL)
   {
      currPtr = head;
      head = head->next;
      currPtr->next = NULL;
      delete currPtr;
   }
}
// The size member function returns the //
// number of nodes in the LinkedList.   //
int LinkedList::size()
{
   int count = 0;
   nodePtr currPtr = head;
   while (currPtr != NULL)
   {
      currPtr = currPtr->next;
      count++;
   }
   return count;
}
// The insert member function creates a new    //
// node containing the parameterized value,    //
// inserting it at the head of the LinkedList. //
// A boolean value indicating whether the      //
// insertion worked is returned.               //
bool LinkedList::insert(elementType elt)
{
	nodePtr currPtr = head;
    nodePtr newNode = getNode(elt);
    if (newNode == NULL)
       return false;
    if (head == NULL)
       head = newNode;
    else
    {
		while (currPtr->item < newNode->item)
	    {
			currPtr = currPtr->next;
		}
		newNode->next = currPtr->next;
		currPtr ->next = newNode;
//		insertPtr->next = head;
//		head = insertPtr;
    }
    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.                     //
bool LinkedList::remove(elementType elt)
{
   nodePtr currPtr = head;
   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)
         head = currPtr->next;
      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 LinkedList::retrieve(elementType elt, int &position)
{
   bool foundIt = false;
   nodePtr currPtr = head;
   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)
{
   nodePtr currPtr = head;
   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 LinkedList::getNode(elementType elt)
{
   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
void LinkedList::deleteList()
{
	nodePtr currPtr;
	while (head != NULL)
	{
		currPtr = head;
		head = head->next;
		currPtr->next = NULL;
		delete currPtr;
	}
}
// delets the first N items of Linked list
void LinkedList::deleteFirstN(int n)
{
	nodePtr currPtr = head;
	for (int i = 0; i < n; i++)
	{
		head = head->next;
		delete currPtr;
		currPtr = head;
	}
}
// deletes the last N items of a linked List
void LinkedList::deleteLastN(int n)
{
	nodePtr currPtr = head;
	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
void LinkedList::copyFirstHalf(LinkedList &list)
{
	nodePtr currPtr = head;
	int half;
	int i = 0;
	if (size() % 2 == 0)
		half = size() / 2;
	else 
		half = (size() / 2)+1;
	if (head == NULL)
		return;
	if(list.head == NULL)
	{
		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
void LinkedList::copyLastHalf(LinkedList &list)
{
	nodePtr currPtr = head;
	int half;
	int i = 0;
	half = size() / 2;
	if ( list.head == NULL)
	{	
		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;
		}
	}
}

[Ancient Dragon]

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.

[Ryan61343]

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

[Ancient Dragon]

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;
    if (head == NULL)
        head = newNode;
    else
    {
        nodePtr currPtr = head;
        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,
                // add the new node to the head
                // of the list
                head = newNode;
            else
                // insert the new node
                // somewhere in the middle of the list
                prevPtr->next = newNode;
        }
    }
    return true;
}

[Ryan61343]

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

[Ancient Dragon]

deleting the last node incorrectly

void LinkedList::deleteLastN(int n)
{
    nodePtr currPtr = head;
    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;
    }
}