Hacker News new | past | comments | ask | show | jobs | submit login

Linked lists and arrays / slices are two totally different data structures with different applications: Removing objects from (anything but the end of) arrays / slices is expensive. If this is a common operation, linked list might be prefarable. This is not a language issue. At my day job, I manipulate lists a lot, this would not be faesable at all with arrays/slices.

Edit: this is a simplified, but typical example of my problem space: http://tex.stackexchange.com/a/233489/243 Traversing a list and manipulate the list entries by adding other items to the list.




Computer architecture being what it is now, though, it has been observed recently that a lot of uses of linked lists are still faster with arrays/vectors, even if you do the "expensive" operations with them.

Point here not being "you're wrong", because you're still right in at least some cases, but that benchmarking can be called for if you're really choosing them for performance because the expense of cache misses and the way linked lists verge on the pathological case for cache misses (not quite, you do stand a chance the next element is in cache and possibly even the next element of RAM, but over time it's not a very good chance) means that arrays can win more often than you would naively think due to the fact linked lists take a rather staggeringly large constant factor nowadays, and it can take rather a lot of using their O(1) advantages to make up for it. This is totally a reachable bar, just, less than you might think.

http://www.codeproject.com/Articles/340797/Why-you-should-ne...

https://www.youtube.com/watch?v=YQs6IC-vgmo

(Note that for instance the second video computes a bit of a pathological case where you have to traverse to find where to insert. In some cases, you will for some reason or other already have that point in hand, which is one of the things that indicates linked lists may be useful; if you always have that case linked lists could still win. But the point should still be taken that vectors/arrays can be way faster than you'd think.)

Of course, if you're using a dynamic scripting language where everything's guaranteed boxed and there's no hope of keeping things local anyhow, well, you might as well take whatever makes the algorithms easier.


Another problem where double linked lists are generally better suited than arrays is caches with LRU eviction.

Example: https://github.com/sebcat/store/blob/master/store.go#L68-L15...




Consider applying for YC's Spring batch! Applications are open till Feb 11.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: