Maple lists are not linked lists. Maple lists are really arrays of
pointers to their entries. Maple lists differ from Maple arrays in
that they are read only, i.e. you can't assign to a component of a Maple list.
Linked lists are recursive data structures.
The difference can be seen by studying a simple example.
Consider representing a polynomial
in Maple. One possibility would be to store the coefficients
in a Maple list.
For instance, we could represent the polynomial
as follows
[11, 2, 3, 0, 1]
The degree of the polynomial is the number of entries in the list minus one. Alternatively we could use a linked list
[ 1, [ 0, [ 3, [ 2, [ 11, NIL ]]]]]
We see that the linked list is a recursive data structure.
It is either list of two values, traditionally called the CAR
and CDR - terminology from the Lisp programming language,
or it is the special value NIL signifying the empty linked list.
The first field contains a data value, in our case,
a coefficient. The second field is a pointer to another linked list
which contains the rest of the data values.
Note that in order to compute the degree of a polynomial represented
by a linked list, we have to compute the depth of the linked list.
If is a linked list, you could do this using the loop
for n from 0 while p <> NIL do p := p[2] od;
Now, why would we represent a polynomial using a linked list instead
of a Maple list? The principle reason is that we can put a new
entry onto the front of a linked list in constant time instead of linear time.
For example, suppose we wanted to add the term to our polynomial
.
In the Maple list representation we must create a
new list with 6 entries by doing
[op(p),5];
This requires at least 6 words of storage for the new Maple list.
Don't be fooled. The op call is short for
op(1..nops(p),p) which creates a sequence of all the entries
in the Maple list . This takes constant time and uses no storage
but now, we have sequence (11, 2, 3, 0, 1), 5 which
results in the new larger sequence 11, 2, 3, 0, 1, 5 being created.
This is where 6 words of storage get allocated.
In general, adding
to a polynomial of degree
takes
time and storage. But what about the linked list?
To add the term
we do
[5,p];
which only needs to create a new Maple list of length two,
hence constant storage.
The time will also be linear time if is a global variable,
but constant time if
is a local variable or parameter inside a procedure.
This evaluation detail will be explained in the section on procedures.
But for now assume that the running time for this operation
is also
for linked lists.