Arrays are static in the number of elements they can hold.


element_at).
  
for (r=l.start(); l.more; r=l.next())
foreach (e in l)
void f(e: element) { ... }
map(f, l)
l that satisfy p.
for (r=l.start(); l.more; r=l.next())
  if (p(l.element_at(r))
    l.remove(r)

start() sets the cursor to the first element. 
    next() advances the cursor one element.
      start() and next() return the cursor.
      
| Array | List | |
|---|---|---|
| (Array) | ||
| create | O(1) | O(1) | 
| delete | O(1) | O(1) | 
| add | O(n) | O(n) | 
| remove | O(n) | O(n) | 
| traversal | O(1) | O(1) | 
| navigation | O(1) | O(n) | 
| dynamic | No | No | 
| 
 | 
 
 | 
struct Node T data; Node * next // singly-linked. Node * prev // doubly-linked.
size() operation.
  
| 
 
 | 
 
 | 
| Array | List | List | |
|---|---|---|---|
| (Array) | (Node) | ||
| create | O(1) | O(1) | O(1) | 
| delete | O(1) | O(1) | O(1) | 
| add | O(n) | O(n) | O(1) | 
| remove | O(n) | O(n) | O(1) | 
| traversal | O(1) | O(1) | O(1) | 
| navigation | O(1) | O(n) | O(n) | 
| dynamic | No | No | Yes | 
| int | point | |||
|---|---|---|---|---|
| simple | 0.09 | 0.1 | ||
| free list | 0.03 | 0.07 | ||
| block | 0.02 | 0.05 | 

| 
 | 
 |