It's important to consider that if your objective is scalability and performance, then the article's advice is appropriate. The article's title ought to read "Stop Using Linked Lists if you care about High Scalability", but I attach the dependent clause on many titles I read from that site.
In a lot of cases they really want to be able to do O(1) inserts/deletes at the beginning/end of the list, which is where linked lists do have a major advantage.
Short linked lists aren't too bad, using them for storing bulk data is mostly a bad idea unless you can't avoid it.
So.. if you want to write a web server/service that can serve tens of thousands of requests - Write it both ways and see for yourself. Its obvious that linked lists are a performance drag. Although they have much in common with other forced indirection penalties (virtual functions, etc)
Edit: ah, found a nice post that has analyzed just this.
http://rusty.ozlabs.org/?p=168
Look at the performance profile here. Using linked lists is the right choice because of the way they are used...
Usage of various data structures determines the asymptotic complexity of whatever you're doing. However, the thing that some uneducated people don't understand about asymptotic complexity is that this metric doesn't measure performance, but rather growth.
Usage of a linked list may mean that searches in it will always be O(n). However, depending on the case, this may be worse than logarithmic or O(1) complexity only for large-enough values of N, because for small values the constant factor plays a role too. Say for instance that you're searching for some value in a linked list. If you're talking about 100 items tops that's being traversed, that's probably going to be faster than a recursive function without TCO searching in a tree.
Priceless is the moment you realise that thinking in terms of asymptotic complexity is the most important thing you could ever do for performance.
Because it's a rather stupid thing to worry about things like cache locality if you don't first optimize the algorithms used. Because, for example, a quick-sort is going to be more efficient for most cases than a bubble sort and a bubble sort is going to be more efficient than a quick-sort for nearly sorted lists, with all the branch predictions or cache locality you could ever pull.
For a real world example, think of databases like MySQL. Performance on inserts in most databases, such as MySQL, deteriorates at an exponential rate, even though most of them are written in hard-core C with all CPU optimizations thrown at it that you can think of. This means that at scale, in one moment your database server is running fine, but in the next moment your server is gone. By comparisson, with a database where inserts degrade linearly, you can notice problems with months in advance.
All one can accomplish with CPU or GPU optimizations is improving the constant factor. This constant factor can be significant indeed, but at large scale it pales in comparison with the speed benefits you get from proper algorithms.
Going further, after you get your algorithms right, which is much easier to do with clean code that uses the right data-structures, you can then easily optimize the underlying implementation of those data-structures. For lists, for the interface of "push()" and "pop()" or of "queue()" and "dequeue()", you can use arrays instead, or linked lists where the items are arrays, or balanced binary search trees, or freaking Patricia tries, or whatever floats your boat, as long as you can maintain the FIFO or LIFO contract.
So that's why the advice is stupid. Because it's not putting things into context.
In fact, I would tell people - try not to use linked lists, because the notion of head and tail is an imperative concept that leaked into the functional world. Which really means it's not a future-proof concept and you'll have problems optimizing it, because you're still thinking in terms of how, versus what.
Citation needed. Haskell's most basic data structure is a singly-linked list. The concept of a linked list seems to fit quite well with functional programming, as adding an additional element is simply a matter of making an element that points back to the unchanged previous element. And, linked lists work very well with recursion, as you can process the head, then move on to the rest of the list.
Are you aware of a functional datatype that can store an arbitrary amount of information and is simpler than a linked-list?
http://skillsmatter.com/podcast/scala/scala-days-keynote-301...
The gist of the matter is this - lists preserve insertion order (instead of the elements themselves having a natural order) and can only be accessed sequentially. You cannot easily split lists in two, or multiple chunks, which means we'll have a hard time doing automatic parallelizing of computations performed on linked lists.
Think of this simple expression:
someList.filter(_ % 2 == 0).map(_ + 10)
If the underlying data-structure would be a balanced binary tree, you could easily split the work required in multiple threads. Because you're specifying the "what" instead of "how" and you can let the platform choose the best solution, like splitting it in threads or offloading that to a GPU, right? Well, linked list have the "how" encoded in them.Maybe it helps to think of data-structures for what they really are: frozen algorithms.
Guy Steele is working on some pretty cool stuff in Fortress. Check that video out.
Furthermore, I am not aware of another functional data structure which has O(1) append time, which allows us to construct lists element by element easily.
It's true though, Lists are easy to implement, easy to reason about and speaking of frozen algorithms, you can view a linked list as being a frozen tail-recursion :-)
The advice should probably be "use the right tool for the job." I wouldn't dream of writing functional programs without lists, but I also don't use e.g. the String type if I don't actually need it to be a list. Lists and arrays have very different algorithmic complexities for different operations. Figure out which operations you need, and pick the data structure that best suits what you intend to do.
Is String actually efficient for this use case? If you insert in the middle of a String, wouldn't it have to copy all of the preceding characters? Only the tail could be shared, I would think.
His examples aren't bad. But they're focused on traversal. Of course use an array when you're mostly traversing linearly. But linked lists are very versatile. Deep down in your OS, the kernel is probably not representing IO buffers as linked lists. But, it's almost certainly storing free IO buffers in a linked list, or using lists to track threads waiting on a lock, etc.
Also, the implication you should ignore algorithmic complexity is questionable. I'd rather be slower by a constant factor than sometimes suffer catastrophic performance when a workload causes the asymptotic complexity to dominate the constant factors. I remember debugging an algorithm that worked fine on some developer's test machine with a few nodes, but exploded on a load with many nodes. It had factorial complexity...
Lists backed by arrays have the same problem as arrays: pointers to elements are not stable. To take the example in my post, say you want to save the environment of every AST node so you can generate debug info mapping from variable names to register numbers at each line. When the list nodes are stable, it's trivial to just save a pointer to the head of the list. When addition/removal operations on the list can cause reallocation, that becomes much harder.
> Linked lists will only win when you need to add or remove elements in random positions (AND don't need random access, so this is usually very niche scenarios where you iterate the list end-to-end but make some updates, e.g. to insert new elements in order).
This is not a niche use. There are a huge number of operations where you don't traverse the list but need to add/remove from the middle. Consider something like the task scheduler in a kernel. When a process makes a call that blocks, the scheduler gets a pointer to the task structure and needs to remove the process from the run queue until the data it is waiting for arrives. If you store the runque as an array, you need to search it and remove the relevant task. If you store it as a doubly linked list, you can remove it with just a couple of pointer modifications. Indeed, inside a kernel or memory allocator, if you're iterating over any potentially large sequences, you've already lost the battle.
This is only a problem if the list is constituted exclusively by its backing store; which is a common implementation for linked lists in some langs/libraries, but rarely for lists backed by arrays. In the latter case, the "list object" typically has a pointer to the backing array, and also other fields like indexes of first/last element in use. This means one extra level of indirection for any use of the list, but in practice compiler optimizations easily hoist or constant-propagate this overhead away in any code where it matters.
> There are a huge number of operations where you don't traverse the list but need to add/remove from the middle
Admittedly, my use of "niche" is context-dependent. In languages like Java where List is a kind of catch-all data structure -- it's the collection that people use when they don't have a very good reason for any other option -- the huge majority of uses do not involve updates in non-tail position (or even any updates after the initial population; most of the time a fixed-size array would work just right... except that it's against modern Java religi, er, style, to ever use its primitive arrays).
It really doesn't matter what the reference actually is, all that matters is that the information for accessing the next node is contained within the current node.
Having optimizations like XOR-ing the back/forth pointers for encoding a doubly-linked list with a single word per node, instead of two, or linking together arrays of fixed size, that's just an implementation detail.
Also, your whole explanation is unnecessary, when this advice is analogous to ... stop using stacks!
I would add queues here too, though people might mistake that for priority queues, which can be modelled as trees.
It turned out he was asking about dynamic memory allocation, i.e., malloc/free and new/delete.
(I didn't get the job)
Speaking of memory allocation, the stack is named that way because it's an actual stack and most function calls receive parameters through it and return their results through it. This is why it's cheaper to store things on the stack, because if you want to use a value from memory, it's going to end up on that stack anyway (e.g. boxing / unboxing), not to mention that items get allocated and deallocated in LIFO order, so you've got no issues with searching for available space or fragmentation.
An example is maintaining the lexical environment as you're compiling a programming language. The first response might be to use something like a hash table. But then how do you handle shadowing (where an inner block shadows a variable of the same name in an other block)? A much cleaner way is to use an association list that's implicitly maintained as you recurse over the AST.
E.g. in psuedo-Python:
For those unfamiliar with Lisp, "let" introduces a new name bound to the value of an initializing expression, which is only in scope for the body of the "let" construct. Assume here that we're generating code from an AST and that the return value of a parse function is the register number where you can find the result of the expression, and the lexical environment maintains a mapping from a variable name to the register where that variable can be found. Or we could be creating an intermediate representation and the lexical environment maintains a mapping from a name to an IR node. Or whatever.Here, "environment" is the association list. Assume that "acons" is a Python function that adds a pair of (key, value) to the front of a linked list. Note how the list is never explicitly mutated, it is maintained implicitly by passing a new value for "environment" as you recurse down. The beauty of this is that entries are removed from the lexical environment implicitly as parsing functions return, and also that "environment" is a purely functional data structure. You can stash away "environment" in say an IR node and it will always refer to a snapshot of the lexical environment for a given AST node, even after other nodes are parsed or the current function returns. This is non-trivial with say a hash table. Storing a copy at each IR node would eat memory. With a linked list, sharing of sub parts falls out for free.
Also, look at the Linux kernel sometime. It uses linked lists all over the place. Your malloc() implementation likely keeps a set of segregated free lists maintained as linked lists. They do this because they avoid ever traversing the list completely. They just operate on the head/tail.