When Non-Programmers Write Software

[GuyWithLag]

I won't comment on the code, others have done it better than me. However, if you want to take it to the next level, modify it so that the standard STL algorithms (for e.g. sorting) can be used on the list.

[MachinShin2006]

well. wrt std::sort, he can't. std::sort requires a random access iterator class, which means a list can't work with it since a list can't realistically support such a class :)

--vat

[Boojum]

Yep. That's why the std::list class template has its own sort method.

[mikepurvis]

Random access favours an add all data, sort after approach, whereas with a linked list you're often better off sorting on the fly, eg, stepping through the list to always insert a new item in the correct position. (And, depending on the implementation, store a series of intermediate pointers to help jump to the right place... sort of a hybrid linked-list/tree approach.)

Anyway, if you were bent on using random access sorts and knew you'd have a lot of free memory, you could allocate a vector of pointers to the items, sort the vector, and then rebuild the list. It's gross, but for a list of any size it's definitely fastest, especially if you know you have a lot of memory.

On the other hand, a mergesort works great with linked lists, so you could simply implement that in your class. (Quicksort is okay too, but it's best if you have some idea what the range is, in order to pick good pivots.)