
5.5.2.8 Example: linked lists and the fast accumulation of results For many applications, one needs to be able to build up a list of some intermediate results obtained in some computation. The easiest way to set up such a list is to use Append or Prepend (or perhaps, AppendTo or PrependTo). However, for large lists this method is quite inefficient. The reason is that lists in Mathematica are implemented as arrays, and thus every time we add an element, the entire list is copied. We can use FoldList to illustrate the creation of a list in such manner :
Now, let us do some performance tests :
We see that the time used by this operation is quadratic in the size of the list. We of course would like a linear time. One way to achieve this which is available starting with the Mathematica version 5.0 is to use the ReapSow technique (to be described in Part II). Another (perhaps, slightly less efficient) way to get a linear time is to use linked lists. We will follow the discussion in the book of David Wagner [7].
A linked list in Mathematica is a structure of the type
The advantage of this representation is that on every level, we have a list containing just 2 elements, which is easy to copy. It will not work in this way for elements that are lists themselves, but then one can replace a list by an arbitrary head <h>.
To avoid a possible conflict with some < h > already defined, we can use Module[{h}, ...] to make it local. Using Fold is the most natural way to create such structures :
Converting them back to a normal list is just as easy with Flatten :
Notice that in the second case we used the fact that Flatten takes as an optional third argument the head which has to be Flatten  ed, and then Flatten  s only subexpressions with this head. In any case, this is another lineartime operation.
Let us do some performance tests:
We see that the time is roughly linear in the list size, and for example, for a list of 20000 we get already a speed  up of the order of 100 times! Flattening is even faster:
Here we assumed that the list of results is accumulated immediately, just to separate this topic from the other problem  specific part of a program. If the list is accumulated not immediately but some other operations are performed in between (which is what usually happens), one just has to use the idiom list = {newelement, list}, to achieve the same result.

