View source for Linked list library

[[category:Function libraries]]

The [[Linked list library]] is a library that comes with Analytica. To use it, you must add the library to your model by selecting '''Add Library...''' from the '''File''' menu. You can either Link or Embed the library, it shouldn't make much difference.

== Linked Lists ==

== Using the Linked list library== 


== Alternatives ==

A linked list is a data structure that is not the same as an Analytica list or array. You can "push" something on the front of a normal Analytica list using
<code>[[Concat]](x,L)</code>
which in many cases is more direct, or on the rear of a list using <code>[[Concat]](L,x)</code>. However, when doing so, the elements of the list are copied with each push. When a large number of items are "pushed" onto a normal list in this fashion, your algorithm ends up with an <math>O(n^2)</math> time complexity. Using a linked list enables you to push ''n'' items in <math>O(n)</math> time.

Another alternative is to use an array. Start with an index, <code>I</code> that has more than the maximum number of items you would ever have in your collection, and then use slice assignment to add items to the array. This takes the form:
 Var a := null;
 Var n := 0;
 a[ I = (n := n+1) ] := 'a';   { Add 'a' as first element }
 a[ I = (n := n+1) ] := 'b';   { Add 'b' as second element }
 ...

Using an array with [[Slice assignment]] in this fashion is likely to be the most efficient method, but it does require you to have a bound on the maximum number of elements that can ever be in the collection, whereas when using a linked list, no such assumptions are necessary.

== See Also ==