Vectors vs. Linked lists

[Jsel]

What are the pros and cons of vectors and linked lists? Are there any tasks that are better suited for one or the other? Thanks.

[quirkyusername]

It depends entirely on what you want to use the data structure for, linked lists are good for sorting for example since you can just swap pointers around instead of copying data, but if you want random access to elements in a linked list you can't just view the element you want to view outright like you can with a vector, you have to start from the head pointer and iterate through every element until you get to the one you're searching for.

[Athar]

Vectors:
- constant time random element access
- good cache locality
- elements are contiguous in memory (so vector can be used with C array interfaces)
- insertions/deletions in the middle/beginning of the vector are slow
- insertions/deletions invalidate iterators

Linked lists:
- no random element access
- bad cache locality, elements are not contiguous in memory
- insertions/deletions are fast at any point in the list
- references/iterators to elements stay valid when other elements are inserted/deleted (depends on the implementation, though)

[Jsel]

Thanks guys.

[firix]

Hi,

The Vector is a form of dynamic array.The vector is the official array of C++. Part of the Standard Template Library

A linked list is a data structure which can change during execution.
It can grow or shrink in size during execution of a program.