One of Clojure's fundamental opinions, asserted by the language eagerly, is that vector quantities should be treated as values the way scalar quantities are in most languages. Specifically, this means that when you operate with a list and append to it, instead of modifying the value of the next (cdr) pointer in the last node, you create a new list and return the new list as the result of the append operation. These immutable collections afford certain classes of algorithm that destructively modified ones do not. Rich reviews this concept pretty well here: <a href="http://www.infoq.com/presentations/Value-Values" rel="nofollow">http://www.infoq.com/presentations/Value-Values</a><p>This story doesn't spend much time discussing this particular opinion of Clojure's or why you would choose to circumvent it by making a mutable linked list. Additionally by virtue of skipping the immutability discussion, it fails to discuss how append to the head of a list is crucially different from append to the tail when working with data structurally sharing underlying data.<p>Additionally it prefers to define an interface over a protocol (using definterface instead of defprotocol), and it uses camelCase naming instead of Clojure's culturally embraced hyphen-cased naming.<p>In short this describes a way to build a data structure in Clojure, but is not a particularly good as an example to be followed of how you should build data structures in Clojure. johnwalker cited a couple more idiomatic examples, e.g. data.finger-trees: <a href="https://github.com/clojure/data.finger-tree/blob/master/src/main/clojure/clojure/data/finger_tree.clj" rel="nofollow">https://github.com/clojure/data.finger-tree/blob/master/src/...</a>
Those days I guess the phrase "linked list" shouldn't really appear without the phrase "locality of reference" somewhere near. From what I understand, the only practical context in which classic linked lists could be better than dynamic arrays on current hardware, maybe except some really atypical applications (huge objects in the nodes?), is when there is a lot of appending and removal done on the ends of the list, or if you need a lot of insertions somewhere in the middle.<p>The wikipedia article on linked lists linked in the article explores a lot of angles and is really excellent. There are some newer, cache-friendlier versions of linked lists, I hope they will start being covered more commonly:<p><a href="http://en.wikipedia.org/wiki/Unrolled_linked_list" rel="nofollow">http://en.wikipedia.org/wiki/Unrolled_linked_list</a><p><a href="http://en.wikipedia.org/wiki/CDR_coding" rel="nofollow">http://en.wikipedia.org/wiki/CDR_coding</a><p>Given linked lists are the workhorse of every Lisp, I wonder if there has been work on using those kinds of data structures in Lisp implementations, or is for example Clojure still using classic linked lists internally.
Certainly a nice intro to Clojure types, though it might be a bit confusing to a beginner, given that linked lists are already built in to Clojure and there's nothing I can see in the tutorial saying "You don't actually have to do any of this, this is just an exercise it for pedagogical purposes."
Why not just stop at the point that a Pair is just two pointers and a List is a bunch of nested Pairs, without any classes, deftypes or monads?)<p>Btw, the classic trick from SICP lectures, where a Pair was implemented as a closure (a procedure) that accepts messages (to illustrate code-is-data principle) is much more interesting abstraction than this overengineered OO stuff.)