List
- This article is about the word list as used in computer science. For other uses, see list (disambiguation).
In computer science, a list is usually defined as an instance of an abstract data type (ADT) formalizing the concept of on ordered collection of entities. For example, an ADT for untyped, mutable lists may be specified in terms of a constructor and four operations:
- a constructor for creating an empty list;
- an operation for testing whether or not a list is empty;
- an operation for prepending an entity to a list (cons);
- an operation for determining the first component of a list (car);
- an operation for referring to the list consisting of all the components of a list except for its first (cdr);
In practice, lists are usually implemented using arrays or linked lists of some sort. Lists have properties that arrays and linked lists share.
Informally, the term list is sometimes used synonymously with linked list. A sequence is another name, emphasizing the ordering and suggesting that it may not be a linked list.
The size and contents of lists may or may not vary at runtime, depending on implementations. Random access over lists also may or may not be possible, depending on implementations.
Sometimes equality of lists is defined simply in terms of object identity: two lists are equal if and only if they are the same object. In modern programming languages, equality of lists is normally defined in terms of structural equality of the corresponding entries, except that if the lists are typed, then the list types may also be relevant.
Lists may be typed. This implies that the entries in a list must have types that are compatible with the list's type. It is common that lists are typed when they are implemented using arrays.
In Lisp, lists are the fundamental data type and can represent both program code and data. In most dialects, the list of the first three prime numbers could be written as (list 2 3 5). In several dialects of Lisp, including Scheme, a list is collection of pairs, consisting of a value and a pointer to the next pair (or null value).
The standard way of implementing lists, originating with Lisp, is to have each element of the list contain both its value and a pointer indicating the location of the next element in the list. This results in either a linked list or a tree, depending on whether the list has nested sublists. Although LISP implementations (such as the LISP used for the Symbolics 3600) often use "compressed lists" which are arrays.
Some languages do not offer a list data structure, but offer the use of associative arrays or some kind of table to emulate lists. For example, Lua provides tables. Although Lua stores lists that have numerical indices as arrays internally, they still appear as hash tables.
Some languages may instead implement lists using other data structures, such as arrays. However, it is generally assumed that elements can be inserted into a list in constant time, while access of a random element in a list requires linear time; this is to be contrasted with an array (or vector), for which the time complexities are reversed.
Lists can be manipulated using iteration or recursion. The former is often preferred in non-tail-recursive languages, and languages in which recursion over lists is for some other reason uncomfortable. The latter is generally preferred in functional languages, since iteration is associated with arrays and often regarded as imperative.
Because in computing, lists are easier to realize than sets, an finite set in mathematical sense can be realized as a list with additional restrictions, that is, duplicate elements are disallowed and such that order is irrelevant. If the list is sorted, it speeds up determining if a given item is already in the set but in order to ensure the order, it requires more time to add new entry to the list.
See also
| 
