My list replies on the user adding the data in themselves, so would it be better for me to amend my add/add_to_end functions to sort the objects as they are added in?

That would be simpler. If you need to sort multiple times (that is, if you have multiple lists you want to sort), then writing a sort function that can be reused would make sense. But I'd go with what you suggested there if that's all you need to do.

Whatever language you are using there should be a standard library for sorting stuff so that you don't have to write your own.

As for sorting on multiple attributes, the best way is to do it in one call but use a compare function like this (pseudocode):

int node_diff(node1, node2) {
int diff = string_diff(node1.name, node2.name);
if (diff == 0)
diff = node1.health - node2.health;
return diff;
}

where diff < 0 indicates less-than, == 0 for equal-to, and >0 for greater-than.

My list relies on the user adding the data in themselves, therefore there is nothing in the list to start with, so would it be better for me to amend my add/add_to_end functions to sort the objects as they are added in?

In this case, you should consider storing the data in a binary search tree instead of a linked list because if you insert into a binary search tree you get sorted-ness for free. I don't know what language you are working in but in C++ i'm talking about using either an std::set or an std::map.

However, i don't know what you are doing so it might make sense to use a linked list maintained as ordered if you actually need list functionality such as O(1) unordered inserts or O(1) splicing of two lists together, etc.

Optimizing (if the circumstances allow it)

If the data DOESNT change as much as the sorted list gets displayed, then retaining the Sort results data between its use (only resorting when the list changes).

Then it might even be possible to optimize by extracting each individual changed item from the Sort data and re-insert it into that previous Sort-Result (eliminating a full/complete resort every time) -- only if a few change.

For data sets that the majority of data constantly change, you will have to rebuild the sorted results every time you used them (display them)

----

Another consideration for the actual Sort methodology is how big is the set of items being sorted. Some more complicated Sort methodology (which may be efficient for large data sets) may have alot of overhead as compared to a simpler more brute-force Sort done on a small set. Sometimes you can even check the data set size at run-time and have a decision made between two methods (after having off-line tested to see where the crossover point is with typical data set size ranges)

----

I would use a Binary Tree Sort for large random data sets (the sorted tree data is seperate from the 'link list' so can be a different data type - though I have frequently had both the link list chain data AND seperate tree Sort data elements in the objects 'record' struct.

More esoteric :

For some huge data sets, cache hit/collision issues with some sorts become important for game speed and you want the Sort manipulation data to be as tiny as possible (possibly one of those "Structure of Arrays" kind of things for permanent object data)

Looks like it's because of line endings.

Enjoy it ;)


void SimpleLinkedList::add_numerical(Beast *b)
{
if(head == NULL)
{
head = b;
return;
}
Beast *previous = head;
Beast *next = previous->get_next();
while(next != NULL)
{
if(head->get_HP() < b->get_HP())
{
next = head;
head = b;
b->set_next(next);
}
if(next->get_HP() get_HP()) -- //wtf?
{
previous->set_next(b);
next = next->get_next();
}
if(next->get_HP() > b->get_HP())
{
next = next->get_next();
}
}
}


I suggest you to write abstract Linked list such it's in STL and then inherits custom list of it.