Like Tree1Likes
  • 1 Post By iMalc

Sorted Linked Lists

This is a discussion on Sorted Linked Lists within the C++ Programming forums, part of the General Programming Boards category; Why do people talk about linked lists being sorted so much? I even remember when I learned about linked lists ...

  1. #1
    C++ Junkie Mozza314's Avatar
    Join Date
    Jan 2011
    Location
    Australia
    Posts
    174

    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.

  2. #2
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,758
    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.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Quote Originally Posted by Mozza314 View Post
    Why do people talk about linked lists being sorted so much?
    They do? That's odd! WHat about queues and stacks and all the other uses that have nothing to do with sorting?
    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!),
    Ding ding ding (warning bells)
    he said that linked lists store sorted data. What's with that?
    Did he also say that cars are red? That statement is equally true.
    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.
    No, if you never modify it after it is set up and sorted then an array would definitely be better.
    A multiset should be used to maintain sorted data, right?
    Not a matter of "should", but that's just what it does. It is sometimes the best thing to use and sometimes not. Much higher overhead than a sorted array.
    Last edited by iMalc; 03-30-2011 at 01:24 PM.
    Mr.777 likes this.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    Programming King Mr.777's Avatar
    Join Date
    Mar 2011
    Location
    Middle of NoWhere
    Posts
    320
    didn't like std::string
    I want Elysia to comment about this.
    Elysia can better explain everything about it.
    I don't care if someone doesn't like me, i was not put on earth to entertain everyone.

    No King, no Queen, I am the ACE of battle.

  5. #5
    C++ Junkie Mozza314's Avatar
    Join Date
    Jan 2011
    Location
    Australia
    Posts
    174
    Quote Originally Posted by Mr.777 View Post
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Linked Lists?!
    By hwing91 in forum C Programming
    Replies: 32
    Last Post: 11-08-2010, 06:13 PM
  2. learning how to do sorted linked lists
    By ktran03 in forum C Programming
    Replies: 2
    Last Post: 03-29-2009, 04:34 AM
  3. Linked Lists 101
    By The Brain in forum C++ Programming
    Replies: 5
    Last Post: 07-24-2004, 05:32 PM
  4. need help w/ linked lists
    By MKashlev in forum C++ Programming
    Replies: 11
    Last Post: 08-05-2002, 09:57 PM
  5. eof in fstream & singly linked lists
    By mazo in forum C++ Programming
    Replies: 3
    Last Post: 06-03-2002, 10:50 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21