Thread: linked lists for set operations, right?

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?

Originally Posted by stabu

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.