linked lists vs arrays

Question

sorry if this been asked already...

Why and when Should I use linked lists over vectors? I just don't like all those pointer overheads...

From my knowledge: vector is faster, more compact because there's no extra pointers, and is easier to implement; also I think that linked lists do not exploit the principle of spatial locality because nodes are in totally random memory locations so your code becomes slower... so when you are using linked lists you are increasing your cache misses which you don't want to do...

Of course the advantage of lists is that you can avoid overflows with dynamic memory allocation...

In summation, my question is: where should you use, if ever, linked lists over vectors? which data struct do you prefer more?

Default to vectors and use lists when you've determined that the performance difference is significant enough. — chris, Aug 31 '14 at 19:37
Given the [tag:c] tag, this isn't really just about `std::list`, but about linked lists in general. http://stackoverflow.com/q/2429217/179910 — Jerry Coffin, Aug 31 '14 at 19:38
I think this table says it all: http://bigocheatsheet.com/#data-structures — Rafael Almeida, Aug 31 '14 at 19:43
You listed all of `vector`'s strengths, but none of its weaknesses. Those weaknesses happen to be strengths of a linked list (i.e., insertions and deletions) — Ed S., Aug 31 '14 at 19:44

score 1 · Answer 1 · edited May 23 '17 at 11:58

1

Linked Lists are for situations where you want to insert or remove an item without shifting or insert/push or pop item in constant time and when you don't know the number of elements and maybe don't need a random access. for more information see this .

edited May 23 '17 at 11:58

Community

1
1

answered Aug 31 '14 at 19:38

Amen

1,524
5
22
41

linked lists vs arrays

1 Answers1