2

Question regarding linked lists vs vectors w/ regards to efficiency.

I understand linked lists insertions/deletions are constant time whereas the same operations with vectors are linear. However, considering you have to perform a linear search on a linked list in order to insert/delete, doesn't that end up being a linear operation.

The insertion/deletion operation itself is constant but since you cannot insert/delete w/o traversing the linked list, you end up with a linear operation. search + insert/delete = linear.

So I don't understand how that is an advantage over a vector. For me, it is the same. Both (ultimately) require a linear operation in order to insert/delete.

What am I missing here?

Ishani Gupta
  • 147
  • 1
  • 10
chappie
  • 119
  • 4
  • 12
  • You are not missing a thing. Many people misunderstand and believe that `O(1)` is always faster than `O(n)`, but it doesn't have to be. 1 minute can be more than n seconds. It depends on how large n is. Using a `std::vector`is often a lot faster than using a `std::list`. See [vector vs. list in STL](https://stackoverflow.com/questions/2209224/vector-vs-list-in-stl) – Bo Persson Nov 09 '17 at 23:52
  • 4
    "*you have to perform a linear search on a linked list in order to insert/delete*" - not if you already know ahead of time where to insert/delete, such as doing such operations relative to nodes you have saved beforehand. – Remy Lebeau Nov 10 '17 at 00:06

2 Answers2

1

Insertion: When we insert in vector(assuming not at the end), we need to shuffle all the elements after the position of insertion O(n) whereas in linkedlist we just have point previous node to new node and new node to old next node O(1).

Reaching: In reaching the position of insertion in vector we just go to the index O(1) whereas in linkedlist it takes O(n) as we stroll from start to the position.

Hence, there is pro and cons for both hence, it depends on the application.

If there are many inserts at random positions, shuffling the elements, again and again, will be inefficient and linkedlist is a better solution. This point consolidates when dealing with complex objects in the vectors/linkedlist.

If the insertion is few times operation and that too at a fixed position(especially at end of the series), the vector will be a better option.

Ishani Gupta
  • 147
  • 1
  • 10
  • "If there are many inserts at random positions..." wouldnt this mean for each random insert you have to perform a linear search to find the position to insert resulting in a O(n), same as vector? – chappie Nov 10 '17 at 00:19
  • Or is it that the costs of shuffling a vector is less efficient than traversing a linked lists even though both are O(n)? Is that safe to say? – chappie Nov 10 '17 at 00:22
  • @chappie - Again, you cannot just compare `O(x)` to `O(y)` and see what is fastest. The `O` notation only tells you the number of operations, not how long time each operation takes. Traversing a linked list involves dereferencing a pointer and loading data from a random position in memory. Traversing a vector means looking at the next position, often already in the cache. – Bo Persson Nov 10 '17 at 00:44
  • starting to see the bigger picture. need to do more reading. only have surface knowledge. didnt even consider memory allocation...thanks:) – chappie Nov 10 '17 at 01:20
  • "In reaching the position of insertion in vector we just go to the index O(1)" ...this sentence seems to assume that the appropriate position to insert something in a vector is at some well known number of nodes from the start, which isn't necessarily true. – H Walters Nov 10 '17 at 02:56
0

Generally, containers differ in complexity depending on the operation. There are many resources for these things. I find this one clear enough.

One more thing to consider is memory allocation style.

Vectors store data continuously, preventing cache misses, which can speed up your application greatly. The downside of this is pointers to data stored inside vectors getting invalidated when performing common operations. There are workarounds, like reserving the memory during initialization, but the issue is there.

Linked lists, on the other hand, have the memory spread out. There is potentially a lot of cache misses, but the pointers are valid through insertions and deletions.

Study each container and pick the one that best suits your needs!

Ryder052
  • 71
  • 6