By definition, a list is a (possibly empty) sequence, that is, an ordered collection of elements in which repetition is allowed. The elements are usually referred to as entries. In some programming languages, it is possible to specify infinite lists, but in most contexts, the length of a list is constrained to be finite but allowed to vary.
In some programming and data definition languages, lists are typed. This implies that the entries in a list must have typess that are compatible with the list's type.
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 equality of the corresponding entries, except that if the lists are typed, then the list types may also be relevant.
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 (quote (1 2 3)).
In Ruby and Prolog, lists can be written like:
In Java, List is an interface in the standard library java.util.List; the type of all entries must be Object.
C++ provides general list facilities in its Standard Template Library (STL).
Some languages do not offer a list data structure, but offer the use of associative arrays or some kind of table to emulate lists.
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 or not. Some languages may instead implement lists using other data structures, such as arrays.
Lists can be manipulated using iteration or recursion.
An array is normally a typed list whose length is fixed within a certain context.
Nearly all kinds of tree structures can also be stored as lists.
A finite mathematical set can be thought of as a list in which duplicate elements are disallowed and such that order is irrelevant; in fact, sets are commonly implemented as lists in which the entries are unique and sorted (for efficiency).
Equality of lists
Lists in programming languages
[1,2,4.5,"hello",[1,2,3]]
Related concepts
See also