Is the linked list only of limited use?

Question

I was having a nice look at my STL options today. Then I thought of something.

It seems a linked list (a std::list) is only of limited use. Namely, it only really seems useful if

• The sequential order of elements in my container matters, and

• I need to erase or insert elements in the middle.

That is, if I just want a lot of data and don't care about its order, I'm better off using an std::set (a balanced tree) if I want O(log n) lookup or a std::unordered_map (a hash map) if I want O(1) expected lookup or a std::vector (a contiguous array) for better locality of reference, or a std::deque (a double-ended queue) if I need to insert in the front AND back.

OTOH, if the order does matter, I am better off using a std::vector for better locality of reference and less overhead or a std::deque if a lot of resizing needs to occur.

So, am I missing something? Or is a linked list just not that great? With the exception of middle insertion/erasure, why on earth would someone want to use one?

Answer 1

Order is important very often. When it is, linked lists are good. If you have a growing collection, you have the option of linked lists, array lists (vector in C++) and double-ended queues (deque). Use linked lists if you want to modify (add, delete) elements anywhere in the list often. Use array lists if fast retrieval is important. Use double-ended queues if you want to add stuff to both ends of the data structure and fast retrieval is important. For the deque vs vector question: use vector unless inserting/removing things from the beginning is important, in which case use deque. See here for an in-depth look at this.

If order isn't important, linked lists aren't normally ideal.

Answer 2

Any sort of insertion/deletion is O(1). Even std::vector isn't O(1) for appends, it approaches O(1) because most of the time it is, but sometimes you are going to have to grow that array.

It's also very good at handling bulk insertion, deletion. If you have 1 million records and want to append 1 million records from another list (concat) it's O(1). Every other structure (assuming stadard/naive implementations) are at least O(n) (where n is the number of elements added).

Answer 3

This question reminds me of this infamous one. Read it for the parallels as to why such simple data structures are important.

Answer 4

Linked List is a fundamental data structure. Other data structures, like hash maps, may use linked lists internally.

Two different algorithms may have O(1) time complexity, for a look up, but that doesn't mean they have the same performance. For example the first one may be 10 or 100 times faster than the second.

Whenever you need to store, iterate and do something with a bunch of data, the normal (and fast) data stucture for that task is the Linked List. More complex data structures are for special cases, ie Set is suitable when you don't want repeated values.

Answer 5

std::list has the following properties:

• Sequence
• Front Seuqence
• Back Seuqence
• Forward Container
• Reverse Container

Of these properties std::vector does not have (Back Seuqence)
While std::set does not support any sequence properties or (Reverse Container)

So what does this mean?
Will a back sequence supports O(1) for rend() and rbegin() etc

For full information see:
http://stackoverflow.com/questions/181693/what-are-the-complexity-guarantees-of-the-standard-containers

Answer 6

Linked lists are immutable and recursive datastructures whereas arrays are mutable and imperative (=change-based). In functional programming, there are usually no arrays - You don't change elements but transform lists into new lists. While linked lists don't even need additional memory here, this isn't possible efficiently with arrays.

You can easily build or decompose lists without having to change any value.

double [] = []
double (head:rest) = (2 * head):(double rest)

In C++, which is an imperative language, you won't use lists that often. One example could be a list of spaceships in a game from which you can easily remove all spaceships that have been destroyed since the previous frame.

Answer 7

std::list is notable for its splice() method, which allows you to move one more more elements from one list to another in constant time, without copying or allocating any elements or list nodes.