Linked Lists Sorting with objects

[schmiischmoo]

Hi guys,
Right now I'm trying to make a program that has a linked list of objects, and can sort the list in ascending order based off the member variables of the nodes (string lName //for last name).

I was able to do it by swapping the value of the objects however I want to try doing it by switch the links of the node.

The output I thought I would get was:
Simpson Holt Davidson Lawson Ngo
Davidson Holt Lawson Ngo Simpson

But instead I am only getting:
Simpson Holt Davidson Lawson Ngo
Simpson

I believe the problem occurs in my sort() function of the addressType class

I am using a singly linked list for this program.

Can anybody explain why this is happening? Thank you for your assistance.

//the node class file
#include "test.h"
class node
{
public:
	test info;
	node* link;

};

//the test object file
class test
{
public:
	test(std::string l = " ");
	std::string getName();

private:
	std::string lName;

};


//the addressType (linked list) .h file
#include "node.h"
#include <iostream>
class addressType
{
public:
	addressType();
	void insert(const test&);
	void print() const;
	void sort();
private:
	node* first;
	node* last;
	int count = 0;
};


//the addressType (linked list) cpp file
#include "addressType.h"

addressType::addressType()
{
	first = nullptr;
	last = nullptr;
	count = 0;
}

void addressType::print() const
{
	node* current = first;

	while (current != nullptr)
	{
		std::cout << current->info.getName() << " ";
		current = current->link;
	}
}

void addressType::insert(const test& newItem)
{
	node* newNode = new node;
	newNode->info = newItem;
	newNode->link = nullptr;

	if (first == nullptr)
	{
		first = newNode;
		last = newNode;
	}

	else
	{
		newNode->link = first;
		first = newNode;
	}

	count++;
}

void addressType::sort()
{
	node* current = first;
	node* trail = current;


	if (first == nullptr || count == 1)
		std::cout << "Nothing to sort!\n";

	else
	{
		current = current->link;

		while (current != nullptr)
		{
			if (trail->info.getName() > current->info.getName())
			{
				trail->link = current->link;
				current->link = trail;
				current = trail->link;
			}

			else
			{
				trail = current;
				current = current->link;
			}
		}
	}
}

//the main user file
int main()
{
	addressType book;
	test one("Ngo");
	test two("Lawson");
	test three("Davidson");
	test four("Holt");
	test five("Simpson");

	book.insert(one);
	book.insert(two);
	book.insert(three);
	book.insert(four);
	book.insert(five);

	book.print();
	book.sort();
	std::cout << "\n";
	book.print();
    return 0;
}

[jonnin]

its messy, but I highly suggest you print the list every iteration in your sort.
I don't see your error yet, but most likely you broke the list (injected a null pointer, probably by swapping a null pointer with a good pointer) so it came out sorted but only with 1 record surviving the ordeal.

I hate linked lists. I advise that if you want a sorted list, sort it as you insert. If you must sort it on the fly, consider using a pseudo linked list that points to vector entries and sort the hidden vector instead and reconstruct the false pointer list after that. If you must sort it as a linked list, you are on the right track, just need to get those pointers hooked up correctly. I think printing each iteration (with a pause) will show you where it is broken.

If I remember it right, the fastest way to sort a LL using only LL approach is to build a second sorted list from the first list, by pulling the pointers apart. So you make a new list, put the head into it, and move head to the next entry, the get the next head, figure out where it goes, repeat. That is, in pseudo code..

while(head)
{
tmp = head;
head = head -> next;
newlist.insert_sorted(tmp); //you write this, it inserts into an existing sorted list in sorted order. It does not create any memory, it just fiddles with the pointers.
}

head = newlist; //just a pointer copy and its back.

[jlb]

The output I thought I would get was:
Simpson Holt Davidson Lawson Ngo

Why do you think you should get this output? You inserted them in the reverse order I would think they should appear in the order inserted. "Ngo Lawson Davidson Holt Simpson".

You say you're using a singly linked list, then why do you have two node pointers in your class. A singly linked list should only need one pointer.