Thread: linked lists for set operations, right?

  1. #1
    Registered User
    Join Date
    Mar 2008

    linked lists for set operations, right?


    I want to create simple sets, say a bunch of different names,

    and then go deleting a few of the names and perhaps adding some others, all the time knowing how big and small the set gets and knowing where each element is.

    It seems to me natural to use a simple linked list for this. It fulfills all the needs, and I think performance should be OK, though later I might upgrade to doubly linked list to improve that aspect.

    Would readers agree? In perl and python I've often seen recommendations for the use of associated arrays for set operations. C++ and Java have their own modules for this.

    I haven't though of hash tables much in this respect, because I reckon linked lists are a more natural format. It would be interesting to hear other people opinion on this.

    Many thanks!

  2. #2
    Join Date
    Jul 2009
    Ask yourself what operations you'll want to perform on this data, and how important the performance characteristics of these operations are to you. Is constant-time access to elements important?
    Disclaimer: This post shows my ignorance at the time of its making. I claim ownership of but not responsibility for all errors in it. Reference at your own peril.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    New Zealand
    Quote Originally Posted by stabu View Post
    I think performance should be OK, though later I might upgrade to doubly linked list to improve that aspect.
    Changing from a singly-linked-list to a doubly-linked-list is worse for both performance and memory usage. It merely trades a little performance and memory for being able to iterate through the list in reverse.

    I think you're asking if a linked-list is the best container for set operations. If that were the case that a std::set in C++ would use a list. In fact it does not, it normally uses a self-balancing binary tree. This improves performance dramatically at the cost of just a little more memory. It also keeps the items ordered. A hash-table i.e. a std::unordered_set in C++ is another option if you don't care about keeping the items in order and are even more keen on something fast.
    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"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help in Linked List Operations
    By aren34 in forum C Programming
    Replies: 54
    Last Post: 03-22-2011, 08:35 PM
  2. Replies: 4
    Last Post: 05-01-2010, 10:19 PM
  3. Question about Linked lists of lists
    By hear_no_evil in forum C Programming
    Replies: 2
    Last Post: 11-08-2004, 02:49 AM
  4. question on linked lists(stack with linked lists)
    By dionys in forum C Programming
    Replies: 1
    Last Post: 06-02-2004, 11:08 AM
  5. Linked List of Linked lists Revisited.
    By Qui in forum C++ Programming
    Replies: 11
    Last Post: 04-11-2004, 09:45 PM