1

I've been spending a lot of time going back and forth on whether I should use a vector or a linked list. I've been reading many completely contradicting views on the topic, so I'd like a strait up answer based on TODAY'S hardware in the REAL world.

So I've been told that if you are doing a lot of insertion and deletion in the middle of your sequence, a linked list would be ideal, with a complexity of O(1) (which in itself I don't fully understand, since you have to traverse all the way to the desired location anyway) while insertion into a vector is apparently very slow, with a complexity of O(n)

On the other hand, after watching this lecture by Bjarne Stroustrup https://www.youtube.com/watch?v=YQs6IC-vgmo it seems as though there is no real use for linked lists, and using linked lists because there will be a lot of insertion and deletion would really only be implemented by a naive student. What I got from this is that essentially by the nature of the traverse of a linked list it is performing random access several times as it travels through different locations in memory, while a vector performs random access once, sending you directly to the desired location. Is this Interpretation accurate?

In my implementation, the sequence is to maintain order, being updated with new values for each element every frame, hence, a lot of deletion and insertion.

My question is: is there really any use for a linked list anymore? Even if it is to maintain order and than simply be run strait through?

background info:

  • the sequence is for a 2D sweep and prune broad phase collision detection;
  • the upper bound of number of elements in the sequence would be about 30,000
Charles Hetterich
  • 171
  • 2
  • 10
  • If your insertions and deletions occur on opposite ends of each-other, (e.g. a queue), and you don't need access to elements at arbitrary positions. – Benjamin Lindley Nov 11 '14 at 07:25
  • I could give you a straight answer, but it would immediately be contested by other users, which would make it not so straight after all. –  Nov 11 '14 at 07:26
  • Your interpretation of Bjarne is correct, and so is your comment "which in itself I don't fully understand"; insertion in an *arbitrary* location in a linked list is O(n) with much worse memory locality than with a vector. – molbdnilo Nov 11 '14 at 07:26
  • I don't really see an answerable question here. Use a linked list if you need stable iterators/references, or fast insertion/removal at a *known* location. (As you say, insertion/removal from an *unknown* location requires iteration to find it). You probably want something else (probably a vector) if you need the fastest possible iteration, or random access. – Mike Seymour Nov 11 '14 at 07:27
  • You may find [Chandler Carruth's CppCon talk](https://www.youtube.com/watch?v=fHNmRkzxHWs) interesting. – T.C. Nov 11 '14 at 07:29
  • @MikeSeymour but even if you have a know location, in a linked list, wouldn't you still have to traverse to the desired reference, nullifying the fact that you know exactly where in the linked list you want to go? – Charles Hetterich Nov 11 '14 at 07:35
  • 2
    Seems like an optimization/engineering task. Make evidence based decisions for yourself, and not based on "only a fool would use that" kind of sentiments - so test it for yourself in a clear A/B test. How does your program work with linked lists vs vectors? You'll get a grip on the situation and how BIG the problem actually is on performance - if the performance impact is lower than 0.1%, does it really matter? – Arend Nov 11 '14 at 07:35
  • @CharlesHetterich, you could traverse it once, and then hold a reference to a node (provided the list is doubly-linked). – Alex D Nov 11 '14 at 07:35
  • 2
    @CharlesHetterich: No, by "a known location", I mean a location for which you have an iterator telling you exactly where in the linked list you want to go. In that case, insertion/removal is constant time. – Mike Seymour Nov 11 '14 at 07:36

1 Answers1

3

I won't comment on your specific situation, but yes, there are plenty of instances in the "real" world, on "today's" hardware, where it makes sense to use linked lists.

One example: implementations of malloc and free (i.e. dynamic memory allocators) typically keep track of blocks of available memory using linked lists. A few extra bytes are included within each memory block for a linked-list pointer. This way, the free blocks themselves can be linked together, without allocating any extra memory elsewhere to keep track of them (as would be required by a vector).

This means that the allocator only requires a constant amount of memory for its own internal recordkeeping. Otherwise your dynamic allocator would itself need to use a dynamic allocator to grow its free lists (actually "free vectors").

The Linux kernel (and probably other OS kernels) uses linked lists for a lot of things. I guess that if it used vectors, that could lead to undesirable latency spikes when it had to grow the vectors (which would be very bad if it happened while holding some important lock, or while masking interrupts, etc).

Alex D
  • 29,755
  • 7
  • 80
  • 126