1

I'm wondering what the difference is between STL:list, STL:vector, array and linked list on a basic level in comparison to one another.

My understanding is that, generally, linked lists allow for grow-able lists, inserts and deletes are much easier but it takes longer to direct access a single element in the linked list since you would need to traverse through every element.

I am probably missing many other key differences so you could also point some more obvious ones out as well.

How do lists and vectors come into play in comparison and when would you choose one over the other?

Kev
  • 11
  • 1
  • 4
  • possible duplicate of [std::vector versus std::array in C++](http://stackoverflow.com/questions/4424579/stdvector-versus-stdarray-in-c) – paddy Apr 16 '13 at 23:41
  • tl;dr: use vectors – it’ll be the right tool 99% of the time. Linked lists are almost never beneficial. – Konrad Rudolph Apr 16 '13 at 23:41
  • Please note it's not called the Standard Template Library anymore. It's the C++ Standard Library. – paddy Apr 16 '13 at 23:42
  • I marked the wrong duplicate. Try this: http://stackoverflow.com/questions/2209224/vector-vs-list-in-stl – paddy Apr 16 '13 at 23:44
  • possible duplicate of [LInked List vs Vector](http://stackoverflow.com/questions/19039972/linked-list-vs-vector) – Sam Jul 02 '15 at 01:58

1 Answers1

1

Below are some differences between lists and vectors.

  1. Time taken for Insertion: Lists take constant time to insert an element into them, where as vectors internally need to relocate the data present in the vector before inserting a new value if the capacity of vector is equal to number of elements present in the vector. This takes a overhead to the processor and time.
  2. Time taken to access the data: Vectors has upper hand over lists in this aspect. Vector takes constant time to access elements present at the middle. Where as lists need to traverse through the list to reach the required element.
  3. Memory taken by the container: The capacity and size of vector necessarily need not be same. The capacity of vector grows exponentially intern consuming more memory than actually needed by the container. Lists take exactly same memory required to store elements, hence no extra memory is allocated during allocation by which you can save memory.
arjun jawalkar
  • 138
  • 1
  • 10