Why you should never, EVER use linked-lists in your code

<i>Until then, why do not we all just stay away from the linked-list for the time being? After all C++ is all about performance - and linked-list is not!</i><p>No, thank you. Instead, why don't we try and understand the benefits and pitfalls of various data structures? Although linked lists may not be a great generic data structure, they can be incredibly useful for certain types of actions. Enumerating their strengths is a much more useful exercise than asserting sweeping generalizations.<p>As for your example: any stack or queue data structure is more efficiently implemented with a linked list than an array/vector. (Or any data structure that just needs to do operations on the head/tail of a data structure.)

Why you should never, EVER write an article that advises other people to never, EVER do something:<p>a) You have red gnomes jumping in front of you<p>b) You have no idea why, in my case, using linked lists actually makes a lot of sense<p>c) if linked lists were to be "considered evil", someone else would have found out in the last 20 years.<p>The bottom line is: know what you're doing. The article has a point (locality of reference) and therefore it's worthwhile. The advise to simply not use linked lists, doesn't help.

The author does an insertion sort in a linked list, of course that's going to be slow.<p>For a sorted insert you need to do 2 things: find the right spot for insertion and the insert itself. An insertion sort does this n times.<p>For a simple array/vector that's:<p><i>search: O(n)</i><p><i>insert: O(1)</i><p><i>total takes (O(n) + O(1)) x O(n) = O(n^2)</i><p>For a linked list:<p><i>search: O(n)</i><p><i>insert: O(n)</i><p><i>total takes (O(n) + O(n)) x O(n) = O(n^2)</i><p>There we go, the algorithm takes O(n^2) for both data structures. The theory already proves that a linked list has absolutely no advantage over an array when using this algorithm. On top of that, iterating over a linked list is slower than over an array for various reasons, even thought they are both O(n). So that's where the difference is coming from.<p>The example he uses is clearly a wrong use case for a linked list, it's plain wrong to conclude that the whole data structure should never be used.

The article has some good points about cache locality, but to suggest that you should never, EVER use linked-list is just terrible, terrible, terrible advice.

Examples based on integers. This is lame, because moving integers in vectors is only memcpy call.<p>Linked-list is better for heavy objects. Inserting heavy objects into middle of container causes N copy-constructors calls. Here comes the pain.<p>Some kind of medium between vectors and lists is vector of pointers(or indexes) to objects (stored in another vector). You need to divide storing from ordering, and you get positives side of each variant.

Well we should obviously NEVER EVER use any LISP derivatives (car/cdr/cons).<p>These sort of articles make me sigh. They are narrow minded and miss the point that everything is a compromise and choosing the right compromise is the art, not a bunch of explicit rules.<p>On the subject, I don't think a real native LISP machine would have cache locality problems. An x86 perhaps which brings in the question that doesn't the architecture define what is good and bad and isn't it a compiler's job to make this issue go away (not ours).