A linked list is a tool for making sure that your data is never in the cache when you want it to be that a lot of developers fetishize because lisp and because

A linked list is a tool for making sure that your data is never in the cache when you want it to be that a lot of developers fetishize because lisp and because they're so easy to implement that every CS curriculum will make you implement one at some point. Just use (dynamically growable) arrays, like, almost always, or heaps or binary trees in special circumstances. Okay, now that I've got that out of my system, I'll try to contribute something positive. Linked lists are useful to understand because they're very similar to, but less complex than, a common representation of trees and graphs. In a tree or graph, each node can have several children instead of just one. There are also some special algorithms that make use of the ability to grow or shrink a linked list in the middle without copying the whole tail [1]. The thing that makes this more rarely useful than you might think is that random access to the middle is O(n), so you have to be moving around in order adding/deleting things. [1] Dancing Links: http://en.m.wikipedia.org/wiki/Dancing_Links http://en.m.wikipedia.org/wiki/Dancing_Links Note, this is actually a circular, doubly linked list.