Which list?
Start with an array. Choose something else when the way you add and remove items says so.
| You need | Use | Cost to know |
|---|---|---|
| Items by position: the default | Array[T], also written T[] |
Reading any position and adding at the end are fast. Inserting or removing in the middle shifts everything after it. |
The same, plus sort and contains |
OrderedArray[T] |
Its elements must be comparable. |
| Work that waits its turn: first in, first out | Deque[T] |
Adding and removing at either end take the same short time, however long it gets. |
| First in, first out, and the line stays short | Queue[T] |
Built on an array, so taking from the front shifts the rest. Use Deque when the queue grows long. |
| Last in, first out | Stack[T] |
Push and pop at the top are fast. |
| Items kept in sorted order as they arrive | SortedList[T] |
Each insert walks to its place; the smallest and largest are always at hand. Elements must be comparable. |
| Each value once, and quick "is it there?" | Set[V, H] |
See Which dictionary?: a set is a dictionary with only keys. |
| Fast insert and remove at both ends of a long list | LinkedList[T] |
Finding an item means walking to it. |
| Items that must never be copied | OwnedList[T] |
It only ever moves its items, and you remove one by the id add gave you. |
| One value of its own on the heap | Box[T] |
Mostly for a type that contains itself, such as a tree of expressions. |
Storing an item takes it, unless you ask for a copy. append, push, enqueue, insert and
add take ownership of the value you pass, and the compiler stops you using it afterwards.
appendCopy, pushCopy and the other …Copy forms make a deep copy and leave yours alone. The name
says which one you chose.
Taking an item out can fail, and says so. popFront, dequeue, pop and peekFirst return the
item or a failure, which you test in an IF or a WHILE: an empty list is never a crash.
CLASS Main IMPLEMENTS TaskStarter {
METHOD start() RETURNS STATUS {
// Work waiting its turn: a Deque takes from the front and adds at the back.
Deque[String] jobs := CREATE Deque[String]()
$? := jobs->pushBack("compile")
$? := jobs->pushBack("link")
WHILE jobs->popFront() DO {
String job := $RETURNED
printline(("running $1")->format(job))
}
// Values kept in order as they arrive: a SortedList.
SortedList[int64] scores := CREATE SortedList[int64]()
$? := scores->insert(42)
$? := scores->insert(7)
$? := scores->insert(19)
IF scores->peekFirst() THEN {
int64 lowest = $RETURNED
printline(("lowest score: $1")->format(lowest))
}
RETURN (SUCCESS)
}
}