3

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?

Improve this question
5
  • Google is also a good friend :) Commented Aug 31, 2014 at 19:26
  • Default to vectors and use lists when you've determined that the performance difference is significant enough. Commented Aug 31, 2014 at 19:37
  • Given the c tag, this isn't really just about std::list, but about linked lists in general. stackoverflow.com/q/2429217/179910 Commented Aug 31, 2014 at 19:38
  • I think this table says it all: bigocheatsheet.com/#data-structures Commented Aug 31, 2014 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) Commented Aug 31, 2014 at 19:44

1 Answer 1

Reset to default
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 .

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.