View source for Linked list library

[[Category:Linked list library functions]]
[[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 can be of use in some algorithms that require a quick way to add items to a collection, when you have no way of determining in advance a ceiling on the maximum number of items, and when the algorithm is doing something more complex than simply extracting a subset of items in an array. 

== Linked Lists ==
A linked list is a data structure containing an ordered list of items that enables quick prepending of new items to the front of the list, and reasonable quick "walking" of the items in sequential order, but slow random access to items. Do not confuse ''linked list'' with Analytica's native ''list'' data structure (See [[#Alternatives|Alternatives]] below for more).

The special value [[Null]] is used as the zero-length linked list. Otherwise, a linked list is a reference to the first ''node'' of the linked list. Each item is stored in a ''node'', which contains the item and a reference to the following node. The functions in the [[Linked list library]] isolate you from the specifics of internals of the data structure, but you will be exposed to the internals if you view a linked list in a result table. The linked list displays as <code>«ref»</code>, and as you double click on each «ref», you can drill-down into the internals.

Each item in a linked list can be a scalar, array, list, or any other data structure.

== Using the Linked list library== 

Use a linked list within algorithms that need to collect an undetermined number of items, or when your algorithm needs to maintain a stack by pushing and popping context. With algorithms that collect items, after the algorithm has collected all the items, it is usually more convenient and more efficient to convert the linked list into an array (list) using [[LL_To_RArray]] or [[LL_To_Array]], rather than to attempt to use the linked list directly as a collection of items. The linked list is efficient for collecting items, but the array is more efficient for accessing items, and the array is far more convenient since all other Analytica functions expect arrays and it can be viewed directly in a result table.

When collecting items, use [[LL_Push]] to push an item onto the front of an existing linked list. Start with [[Null]] as the empty list. Because [[LL_Push]] adds each new item to the front of the list, the linked list stores items in the reverse order that they are pushed.

When converting a linked list to an array, use [[LL_To_RArray]] to obtain an array with the items in the same order you "pushed" them, or [[LL_To_Array]] to obtain an array with the items in the reverse order that you pushed them. 

The operations [[LL_Push]], [[LL_First]] and [[LL_Remove_First]] are constant time operations. Hence, linked lists are useful when the core of your algorithm needs only these operations. 

== Example ==

This example collects all numbers visited by the 3n + 1 algorithm when started from 27. The 3n + 1 algorithm starts at a whole number, then moves according to the rule: If n is even, halve it, if odd move to 3*n + 1. Terminate when you reach 1. It is a conjecture in number theory that the algorithm always terminates for any positive starting integer, but it remains an open problem to prove.

:<code>Var n := 27;</code>
:<code>Var LL := null;</code>
:<code>While (n > 1) do (</code>
::<code>LL := LL_Push(LL, n);</code>
::<code>n := If Mod(n, 2) Then 3*n + 1 Else n/2</code>
:<code>);</code>
:<code>LL_To_RArray(LL, "step")&rarr;</code>

:[[image:Start_3n+1_from_27.png]]
:::&nbsp;          &#8942;
:[[image:End_3n+1_from_27.png]]

== 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.

If you are extracting a subset of items with a known property, [[Subset]] can be used, and will return a list directly, usually much faster than would be possible using a linked list to build up the list one element at a 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:
:<code>Var a := null;</code>
:<code>Var n := 0;</code>
:<code>a[I = (n := n + 1)] := 'a';   { Add 'a' as first element }</code>
:<code>a[I = (n := n + 1)] := 'b';   { Add 'b' as second element }</code>
:<code>...</code>

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.

== Instructional value ==
Some programming languages have ''record'' or ''struct'' constructs that group data items into a single record. In Analytica, this is accomplished using an Index to define the members of the record, and references for non-scalar member items. One of the values of the linked list library is that it provides a simple example of using an index to define a record structure. The <code>Linked_list</code> index defines a record or struct for storing one node of the linked list. This record has two fields -- item and next.

== See Also ==
* [[media:Linked List Library.ana|Linked List Library.ana]]
* [[Subset]]
* [[Slice assignment]]
* [[LL_Length]]
* [[LL_Push]]
* [[LL_First]]
* [[LL_Remove_First]]
* [[LL_To_RArray]]
* [[LL_To_Array]]
* [[LL Nth]]
* [[Concat]]
* [[Analytica Libraries and Templates]]