[srssays]

> Linked lists are a very convenient and surprisingly universal data structure, but they really shine wherever you have a recursive algorithm. Which is, in the languages mentioned, almost all the time.

Linked lists were way ahead of their time. Nowadays everything is so fast that we can probably use them without guilt, but there is still a sense of disgust associated them.

[klibertp]

Linked lists are indeed wasteful in terms of memory usage, compared to simple arrays. There are ways of optimizing this, but you won't get away from having an additional pointer to the next element.

However, linked lists offer many advantages that arrays do not. The length of a list need not be known at compile time, for one. It's trivial and very fast to insert a new element in the middle of the list. They are not optimized for random access, but they pose no performance penalty (over arrays) if you need to traverse them from start to end.

But the most important advantage of linked lists is that they are their own iterators (in C++ parlance). You don't need an additional state for iterating over a list - you don't need to store and update the index, for example. Each element of a list is the beginning of the rest of the list, so if you hold a reference to one, you can stop and restart iteration without problems. Moreover, you can add elements to the list and still be able to use the previously captured element as a start of new iteration: no need to invalidate the iterator.

In other words, Linked List has some very desirable properties and it makes sense to use it for almost anything other than a fixed-length, random-access collection. All Lisps provide vectors and hashes for the latter use-case.

I think the problem with Linked Lists is that they are not hard to implement and taught on the entry-level courses, with C as an implementation language. This makes it very hard to see their usefulness. With a bit of tooling (library functions) and language support, they really shine.

[lispm]

> but you won't get away from having an additional pointer to the next element

It was done on some Lisp Machines with CDR-coding. newly allocated lists did not have any CDR pointers. Optimizing lists that way could also be done by the garbage collector, when it needed to copy lists or in optimization runs before saving an image.

Most other implementations did not implement it.

http://www.faqs.org/faqs/lisp-faq/part2/section-9.html