Thread: Sorted Linked Lists

Why do people talk about linked lists being sorted so much? I even remember when I learned about linked lists my lecturer (who I think was rather old-school, e.g. didn't like std::string and told us to prefer cstrings!), he said that linked lists store sorted data. What's with that? It's not efficient to maintain a sorted list. It would only make sense to me to use a list for sorted data if you put the data in there once, then sort it, and don't modify it. A multiset should be used to maintain sorted data, right?

Well I guess it would be alright if memory was a lot more scarce than CPU time, maybe.

Why do people talk about linked lists being sorted so much?

That begs the question. I have seen tutorials for this which do not make a list that is going to maintain sorted order. (e.g. here and here)

A multiset should be used to maintain sorted data, right?

Sure, because std::multiset has specific properties. I have the rather obnoxious opinion that you can sort pretty much anything that isn't a heap, a tree, or a hash table. I don't think the STL is necessarily word of god on data structures. The STL is an implementation of them.

Originally Posted by Mr.777

I want Elysia to comment about this.
Elysia can better explain everything about it.

Oh I'd like to see someone stop Elysia commenting on this :-P.