Bubble sort duplicates linked list items

[moonman239]

My assignment is to create a function that sorts the provided linked list. When I run the program and sort the list, some list items appear twice, despite there being no duplicate entries before the sort. I tried inserting some code into the second while loop to try to get my program to stop when this duplication occurs.

        bool shouldContinue = true; // Indicates whether to continue the loop.
  	while (shouldContinue) {
	while (LinkedList->GetCurrentNode() != LinkedList->GetLastNode()) // have not reached end of linked list
	{
	string current = LinkedList->GetCurrentNode()->GetString();
	LinkedList->Next();
	string next = LinkedList->GetCurrentNode()->GetString();
//   Compare the two items
		int compare = current.compare(next);
		if (compare == 1) {
			//Insert the second item into the list before the first item
			LinkedList->Previous();
			LinkedList->Insert(next);
     // Delete the second item from its original location
			LinkedList->Next();
			LinkedList->Delete();
		}
		else
		{
			shouldContinue = false;
		}
		iCompareCount++; // increment iCompareCount
//Loop end
	}
	LinkedList->SetCurrentNode(LinkedList->GetFirstNode());
//Repeat the loop until no changes are made
}

[moonman239]

UPDATE: It appears to be more than that. When the loop terminates, the data isn't exactly sorted. Instead, perhaps the outer loop is terminating prematurely.

[doug4]

Not knowing exactly what the LinkedList member functions do, I have some questions to ask.

I assume GetLastNode returns the actual last node of the list, not the first element past the end of the list like the standard template containers do.

After "Insert", what does GetCurrentNode return? Is it the node that was inserted or the one that it was pointing to before?

Does Insert put the node before or after the current node?

After "Delete", what does GetCurrentNode return?

What you need to do is draw out (on paper) 2 nodes in your list and figure out what lines 12 - 16 are actually doing. Make sure after each step that your current node as well as all of your nodes and links are updated before you consider your next step.