CODEWITHSUNDEEP
c++listvector
chappie
chappie

Reputation: 169

Linked Lists vs Vector

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?

Upvotes: 2

Views: 2891

Answers (2)

Ryder052
Ryder052

Reputation: 81

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!

Upvotes: 0

Ishani Gupta
Ishani Gupta

Reputation: 166

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.

Upvotes: 1

Related Questions