Lists vs. Arrays

A DScript list is very similar to what is called an array in other programming languages. However, there are differences. In most other languages, you must declare an array before you can use it. For example, if you want to work with an array of ten numbers, you first declare the array and specify its size. The programming language then allocates a single block of memory large enough to hold all ten numbers. In DScript, there is no need to declare arrays because memory is allocated and freed as the array grows and shrinks. DScript does this by allocating memory in small blocks instead of allocating a single, large block to hold the entire array.

In DScript, arrays are stored as linked lists. For example, suppose you create an array of 10 numbers as follows:

Array=[1,2,3,4,5,6,7,8,9,10];

DScript will allocate 10 small blocks of memory that each holds one number. Each block of memory includes a pointer to the next item in the list. That is, the number 1 points to 2, 2 points to 3, and so on. Finally, the number 10 points to nothing because this is the end of the list.

The linked list structure allows you to do things with DScript lists that you cannot do with traditional arrays. For example, the following statement will replace the third element in Array with a text string:

Array[2]="This is the third element.";

This is impossible to do in most programming languages because the text string requires more memory to store than does a number. However, since DScript stores the array as a list of separate memory blocks, all it needs to do is allocate a block of memory to hold the text string, free the block that holds the number 3, and then update the pointers so that 2 points to the string and the string points to 4. The result is a list equivalent to the following:

Array=[1,2,"This is the third element.",4,5,6,7,8,9,10];

The linked list structure allows you to store data of different types in the same array; it allows you to change dynamically the type of an element; and, it allows you to dynamically add and delete elements in an array. However, there is a price for this additional functionality--processing linked lists can be slower than traditional arrays. For example, if you have an array with 1000 elements and you want to read the value of the 900th element, a program written for a traditional language will be able to calculate the exact memory location of that element and go directly to it. With a linked list, the program must traverse all 899 elements preceding the 900th element in order to find the memory location where the 900th element is stored.

Fortunately, lists provide additional functionality that allows you to get around this inefficiency--so long as you use list-processing capabilities. The following code adds one to every element in a list:

for(var n=0; List[n]!=null; n++)
List[n]+=1;

As long as the list is short, this code is reasonably efficient. However, as you start to add one to elements far down the list, DScript will spend most of its time traversing preceding elements in the list. For example, when n is equal to 900, DScript must traverse 899 elements twice, once when evaluating List[n]!=null and again when evaluating List[n]+=1.

A better way to accomplish this same function is to use the following statement:

List+=1;

DScript will recognize that List is not a single number and it will add one to every element in List. This code is not only much more efficient than the for loop, it is much more efficient than any for loop you can construct in a programming language that uses traditional arrays.