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 allocates 10 small blocks of memory that each hold 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 lets you do things with DScript lists you cannot do with traditional arrays. For example, the following statement replaces 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, it simply allocates a block of memory to hold the text string, freed the block that holds the number 3, and updates the pointers so 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 lets you:

  • Store data of different types in the same array
  • Change dynamically the type of an element
  • 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 can 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 lets you get around this inefficiency, as 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 spends 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 recognizes that List is not a single number and it adds 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 using traditional arrays.

See About the For Statement.