In computer science
, a list or sequence is an abstract data type
that represents a countable number of order
s, where the same value may occur more than once. An instance of a list is a computer representation of the mathematical
concept of a tuple
or finite sequence
; the (potentially) infinite analog of a list is a stream
. Lists are a basic example of container
s, as they contain other values. If the same value occurs multiple times, each occurrence is considered a distinct item.
The name list is also used for several concrete data structure
s that can be used to implement abstract
lists, especially linked list
s and array
s. In some contexts, such as in Lisp
programming, the term list may refer specifically to a linked list rather than an array. In class-based programming
, lists are usually provided as instance
s of subclasses of a generic "list" class, and traversed via separate iterator
Many programming language
s provide support for list data types, and have special syntax and semantics for lists and list operations. A list can often be constructed by writing the items in sequence, separated by comma
s, and/or space
s, within a pair of delimiters such as parentheses
s '', [[brace (punctuation)|brace]]s '', or [[angle bracket]]s '<>'. Some languages may allow list types to be [[array index|index]]ed or [[array slicing|slice]]d like [[array data type|array type]]s, in which case the data type is more accurately described as an array.
In type theory
and functional programming
, abstract lists are usually defined inductively
by two operations: ''nil'' that yields the empty list, and ''cons'', which adds an item at the beginning of a list.
Implementation of the list data structure may provide some of the following 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
* an operation for appending an entity to a list
* an operation for determining the first component (or the "head") of a list
* an operation for referring to the list consisting of all the components of a list except for its first (this is called the "tail" of the list.)
* an operation for accessing the element at a given index.
Lists are typically implemented either as linked list
s (either singly or doubly linked) or as arrays
, usually variable length or dynamic array
The standard way of implementing lists, originating with the programming language 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. Some older Lisp implementations (such as the Lisp implementation of the Symbolics
3600) also supported "compressed lists" (using CDR coding
) which had a special internal representation (invisible to the user). Lists can be manipulated using iteration
. The former is often preferred in imperative programming languages
, while the latter is the norm in functional language
Lists can be implemented as self-balancing binary search tree
s holding index-value pairs, providing equal-time access to any element (e.g. all residing in the fringe, and internal nodes storing the right-most child's index, used to guide the search), taking the time logarithmic in the list's size, but as long as it doesn't change much will provide the illusion of random access
and enable swap, prefix and append operations in logarithmic time as well.
Programming language support
Some languages do not offer a list data structure
, but offer the use of associative array
s 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 dictionaries.
, 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 a collection of pairs, consisting of a value and a pointer to the next pair (or null value), making a singly linked list.
As the name implies, lists can be used to store a list of elements. However, unlike in traditional arrays
, lists can expand and shrink, and are stored dynamically in memory.
In computing, lists are easier to implement than sets. A finite set
in the mathematical sense can be realized as a list with additional restrictions; that is, duplicate elements are disallowed and order is irrelevant. Sorting the list 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. In efficient implementations, however, sets are implemented using self-balancing binary search tree
s or hash table
s, rather than a list.
Lists also form the basis for other abstract data types
including the queue
, the stack
, and their variations.
The abstract list type ''L'' with elements of some type ''E'' (a monomorphic
list) is defined by the following functions:
:nil: () → ''L''
:cons: ''E'' × ''L'' → ''L''
:first: ''L'' → ''E''
:rest: ''L'' → ''L''
with the axioms
:first (cons (''e'', ''l'')) = ''e''
:rest (cons (''e'', ''l'')) = ''l''
for any element ''e'' and any list ''l''. It is implicit that
:cons (''e'', ''l'') ≠ ''l''
:cons (''e'', ''l'') ≠ ''e''
) = cons (''e''2
) if ''e''1
Note that first (nil ()) and rest (nil ()) are not defined.
These axioms are equivalent to those of the abstract stack
In type theory
, the above definition is more simply regarded as an inductive type
defined in terms of constructors: ''nil'' and ''cons''. In algebraic terms, this can be represented as the transformation 1 + ''E'' × ''L'' → ''L''. ''first'' and ''rest'' are then obtained by pattern matching
on the ''cons'' constructor and separately handling the ''nil'' case.
The list monad
The list type forms a monad
with the following functions (using ''E''*
rather than ''L'' to represent monomorphic lists with elements of type ''E''):
where ''append'' is defined as:
Alternatively, the monad may be defined in terms of operations ''return'', ''fmap'' and ''join'', with:
Note that ''fmap'', ''join'', ''append'' and ''bind'' are well-defined, since they're applied to progressively deeper arguments at each recursive call.
The list type is an additive monad, with ''nil'' as the monadic zero and ''append'' as monadic sum.
Lists form a monoid
under the ''append'' operation. The identity element of the monoid is the empty list, ''nil''. In fact, this is the free monoid
over the set of list elements.
Category:Composite data types
Category:Abstract data types