Linked Lists

[chappie]

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

I understand linked lists insertions/deletions are constant time whereas the vectors are linear. However, considering you have to perform a linear search on a linked list in order to insert/delete, doesnt 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 dont understand how that is an advantage over a vector. In my mind, its the same. Both (ultimately) require a linear operation in order to insert/delete.

What am I missing here?

[Peter87]

If you already have the position that you want to delete you can do it in constant time.

[chappie]

But the likelihood of that is minimal making it negligible...if you have an address book, what's the likelihood you'll have the exact position to insert/delete a new contact. which means you have to perform a linear search in order to insert/delete the contact. same costs as shuffling in a vector.

[Repeater]

To insert into a vector, you then need to copy everything following that location one element to the right. To insert into a list, you must find the position in question, but then you need only edit the preceding element (and the following element if the list is bi-directional). The question thus arises; when is it faster to do the first, and when the second? Order notation and linear operation vs. quardatic operation, and so on, doesn't tell us anything at all about speed or which algorithm is faster; it only tells us how something will scale.

Reality, what say you?

https://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html

It has some really good diagrams and a good range of comparisons. His conclusion; use the linked list if you've got a lot of large object (and, I would add, you are going to be doing a lot of insertion/removal). Otherwise, vector or deque.

What you specifically mention - insert/delete - is covered towards the middle. It does not assume you already know the location. As can been seen, with small inexpensive data types, up to a surprisingly high number of elements, vector/deque is the way to go.

Obviously that's only one particular implementation, but it's a very common implementation.