Is linked list limited use?

Question

Today I looked at my STL options well. Then I thought of something.

The linked list (std :: list) seems to be limited to limited use. Namely, it only really seems useful if

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

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

That is, if I just want a lot of data and don't care about its order, I better use std :: set (balanced tree) if I want to search for O (log n) or std :: unordered_map (hash map) if I I want to expect the expected search O (1) or std :: vector (adjacent array) for better locality of the link or std :: deque (double-ended queue) if I need to insert front and back.

OTOH, if the order matters, I better use std :: vector for better link locality and less overhead, or std :: deque if you need to resize.

So am I missing something? Or is the linked list just not that good? Except for the middle insert / erase, why does anyone want to use it?

Answer 1

Any insertion / deletion is O (1). Even std :: vector is not O (1) for additions, it approaches O (1) because most of the time it is, but sometimes you will have to grow this array.

, . 1 1 (concat), O (1). ( / ) O (n) ( n - ).

Answer 2

. , . , , (vector ++) (deque). , (, ) . , . , , . deque vs vector: vector, / , deque. . .

, .

Answer 3

std::list splice(), - .

Answer 4

. , .

Answer 5

- . , -, . O (1) , , . , 10 100 .

, , - , ( ) . , Set , .

Answer 6

std:: list :

• Front Seuqence
• Seuqence

std::vector (Back Seuqence)
std:: set ( )

?
O (1) rend() rbegin() ..

.:
?

Answer 7

, (= ). - , . , .

You can easily create or decompose lists without changing any value.

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

In C ++, which is an imperative language, you will not often use it list. One example is the list of spaceships in the game from which you can easily remove all spaceships that were destroyed from the previous frame.