Lua library module "list"

Author: Hans van der Meer

The Lua modules arraylist and linkedlist are C-modules for the manipulation of lists. Both have the same API, but in the underlying implementation they differ fundamentally.

In the array implementation of arraylist access to the elements can be accomplished very efficiently, as well as adding nodes at the end. But insertion and removal of nodes can be costly, because the nodes above the insertion or deletion point must all be moved up or down, respectively. The doubly linked implementation of the linkedlist excels where the arraylist has difficulties. Insertion and deletion can be effected more efficiently, but finding the nodes to be accessed is not a one step process as with the arraylist. Their strong points and weaknesses complement each other more or less. The choice between the one or the other is therefore dictated by the needs of the program at hand.

Both share the same API, making substitution of the one for the other a simple matter.



  1. Functions that return the list allow chaining of operations.
  2. An index out of range or nil forces an error.
  3. Negative index values are count backwards, -1 denoting the last entry.
  4. The value nil is not allowed as contents of the list and will be ignored.
  5. Sorted lists maintain their sort order through all additions.

Create list return empty list optional name (string) initial capacity (positive number) compare (function) reverse default compare sorted list
new and create are synonyms
The function compare(elt1, elt2) shall return integer values +1, 0 or -1 for in-order, equal and out-order results, respectively. A return of +1 has the meaning that the values are out of order with respect to sorting. The parameters elt1, elt2 are the two elements to compare. If compare is not given the elements are by default compared arithmetically. In that case an error is raised if they are not numbers. Value true for the direction parameter choose ascending compare results for the default compare, false selects descending.
The (name, capacity, compare, -1, true) parameters can be given in any order and in any combination. Other parameter values or types are acceptable, but will be silently ignored.

Add element

unsorted sorted
l:add(value) add at end insert in order
l:insert(value) insert at front insert in order
l:insert(value, index) insert at index insert in order
all return the list
Tables are allowed as input value and are fully expanded to include their values.

Remove element

l:delete() make list empty
l:delete(index) remove element at index
all return the list, delete and remove are synonyms

Get element value

l:get(index [,index [...]]) return values at index
l:get() return table of all values
Requesting all values returns them in a table, because their number might be so large as to exhaust the capacity of the return stack.

Get element iterator

l:iterator() return forward iterator
l:iterator(-1) return reverse iterator
Do not alter the contents of the list (add, insert, remove) while there are active iterators: the results are unpredictable or even disastrous.

Find element

l:find(value) return index of value or nil
l:find(value, index) start at given index

Order of elements

l:compare(elt1, elt2) return result of compare
As stated above, the compare function returns +1 for an in order result, 0 for equality and -1 for out of order compare result.
If sorted collections must be extracted, it is best to create the list as a sorted one and extract all values in a table. Otherwise one has to sort the extracted values oneself.

Query state

l:empty() true/false for list empty/not empty
l:size(), #l list size
l:sorted() return true if sorted list
l:ident() identity stamp, name or nil
list.version() version of the module