List (data structure)
   HOME

TheInfoList



OR:

In
computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includi ...
, a list or sequence is an
abstract data type In computer science, an abstract data type (ADT) is a mathematical model for data types. An abstract data type is defined by its behavior (semantics) from the point of view of a ''user'', of the data, specifically in terms of possible values, pos ...
that represents a finite number of ordered values, where the same value may occur more than once. An instance of a list is a computer representation of the
mathematical Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
concept of a
tuple In mathematics, a tuple is a finite ordered list (sequence) of elements. An -tuple is a sequence (or ordered list) of elements, where is a non-negative integer. There is only one 0-tuple, referred to as ''the empty tuple''. An -tuple is defi ...
or finite
sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is calle ...
; the (potentially) infinite analog of a list is a stream. Lists are a basic example of
container A container is any receptacle or enclosure for holding a product used in storage, packaging, and transportation, including shipping. Things kept inside of a container are protected on several sides by being inside of its structure. The term ...
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 structures that can be used to implement abstract lists, especially linked lists and
array An array is a systematic arrangement of similar objects, usually in rows and columns. Things called an array include: {{TOC right Music * In twelve-tone and serial composition, the presentation of simultaneous twelve-tone sets such that the ...
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 Class-based programming, or more commonly class-orientation, is a style of object-oriented programming (OOP) in which inheritance occurs via defining ''classes'' of objects, instead of inheritance occurring via the objects alone (compare prototy ...
, lists are usually provided as instances of subclasses of a generic "list" class, and traversed via separate
iterator In computer programming, an iterator is an object that enables a programmer to traverse a container, particularly lists. Various types of iterators are often provided via a container's interface. Though the interface and semantics of a given iterat ...
s. Many
programming language A programming language is a system of notation for writing computer programs. Most programming languages are text-based formal languages, but they may also be graphical. They are a kind of computer language. The description of a programming ...
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 commas,
semicolon The semicolon or semi-colon is a symbol commonly used as orthographic punctuation. In the English language, a semicolon is most commonly used to link (in a single sentence) two independent clauses that are closely related in thought. When a ...
s, and/or
space Space is the boundless three-dimensional extent in which objects and events have relative position and direction. In classical physics, physical space is often conceived in three linear dimensions, although modern physicists usually cons ...
s, within a pair of delimiters such as
parentheses A bracket is either of two tall fore- or back-facing punctuation marks commonly used to isolate a segment of text or data from its surroundings. Typically deployed in symmetric pairs, an individual bracket may be identified as a 'left' or 'r ...
'()', brackets '[]', brace (punctuation), braces '', or angle brackets '<>'. Some languages may allow list types to be array index, indexed or array slicing, sliced like array data type, array types, in which case the data type is more accurately described as an array. In
type theory In mathematics, logic, and computer science, a type theory is the formal presentation of a specific type system, and in general type theory is the academic study of type systems. Some type theories serve as alternatives to set theory as a fou ...
and
functional programming In computer science, functional programming is a programming paradigm where programs are constructed by applying and composing functions. It is a declarative programming paradigm in which function definitions are trees of expressions that ...
, 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.


Operations

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.


Implementations

Lists are typically implemented either as linked lists (either singly or doubly linked) or as
arrays An array is a systematic arrangement of similar objects, usually in rows and columns. Things called an array include: {{TOC right Music * In twelve-tone and serial composition, the presentation of simultaneous twelve-tone sets such that the ...
, usually variable length or dynamic arrays. 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 In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...
, 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 In computer science CDR coding is a compressed data representation for Lisp linked lists. It was developed and patented by the MIT Artificial Intelligence Laboratory, and implemented in computer hardware in a number of Lisp machines derived from t ...
) which had a special internal representation (invisible to the user). Lists can be manipulated using
iteration Iteration is the repetition of a process in order to generate a (possibly unbounded) sequence of outcomes. Each repetition of the process is a single iteration, and the outcome of each iteration is then the starting point of the next iteration. ...
or
recursion Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathemati ...
. The former is often preferred in imperative programming languages, while the latter is the norm in
functional language In computer science, functional programming is a programming paradigm where programs are constructed by applying and composing functions. It is a declarative programming paradigm in which function definitions are trees of expressions that ...
s. Lists can be implemented as
self-balancing binary search tree In computer science, a self-balancing binary search tree (BST) is any node-based binary search tree that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions.Donal ...
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 In computer science, an associative array, map, symbol table, or dictionary is an abstract data type that stores a collection of (key, value) pairs, such that each possible key appears at most once in the collection. In mathematical terms an ...
s or some kind of table to emulate lists. For example,
Lua Lua or LUA may refer to: Science and technology * Lua (programming language) * Latvia University of Agriculture * Last universal ancestor, in evolution Ethnicity and language * Lua people, of Laos * Lawa people, of Thailand sometimes referred t ...
provides tables. Although Lua stores lists that have numerical indices as arrays internally, they still appear as dictionaries. 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 a collection of pairs, consisting of a value and a pointer to the next pair (or null value), making a singly linked list.


Applications

As the name implies, lists can be used to store a list of elements. However, unlike in traditional
arrays An array is a systematic arrangement of similar objects, usually in rows and columns. Things called an array include: {{TOC right Music * In twelve-tone and serial composition, the presentation of simultaneous twelve-tone sets such that the ...
, 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 In computer science, a self-balancing binary search tree (BST) is any node-based binary search tree that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions.Donal ...
s or
hash table In computing, a hash table, also known as hash map, is a data structure that implements an associative array or dictionary. It is an abstract data type that maps keys to values. A hash table uses a hash function to compute an ''index'', ...
s, rather than a list. Lists also form the basis for other
abstract data types In computer science, an abstract data type (ADT) is a mathematical model for data types. An abstract data type is defined by its behavior (semantics) from the point of view of a '' user'', of the data, specifically in terms of possible values, ...
including the
queue __NOTOC__ Queue () may refer to: * Queue area, or queue, a line or area where people wait for goods or services Arts, entertainment, and media *''ACM Queue'', a computer magazine * ''The Queue'' (Sorokin novel), a 1983 novel by Russian author ...
, the stack, and their variations.


Abstract definition

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''1, ''l''1) = cons (''e''2, ''l''2) if ''e''1 = ''e''2 and ''l''1 = ''l''2 Note that first (nil ()) and rest (nil ()) are not defined. These axioms are equivalent to those of the abstract stack data type. In
type theory In mathematics, logic, and computer science, a type theory is the formal presentation of a specific type system, and in general type theory is the academic study of type systems. Some type theories serve as alternatives to set theory as a fou ...
, the above definition is more simply regarded as an
inductive type In type theory, a system has inductive types if it has facilities for creating a new type from constants and functions that create terms of that type. The feature serves a role similar to data structures in a programming language and allows a t ...
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 In computer science, pattern matching is the act of checking a given sequence of tokens for the presence of the constituents of some pattern. In contrast to pattern recognition, the match usually has to be exact: "either it will or will not be ...
on the ''cons'' constructor and separately handling the ''nil'' case.


The list monad

The list type forms a
monad Monad may refer to: Philosophy * Monad (philosophy), a term meaning "unit" **Monism, the concept of "one essence" in the metaphysical and theological theory ** Monad (Gnosticism), the most primal aspect of God in Gnosticism * ''Great Monad'', a ...
with the following functions (using ''E''* rather than ''L'' to represent monomorphic lists with elements of type ''E''): :\text\colon A \to A^ = a \mapsto \text \, a \, \text :\text\colon A^ \to (A \to B^) \to B^ = l \mapsto f \mapsto \begin \text & \text \ l = \text\\ \text \, (f \, a) \, (\text \, l' \, f) & \text \ l = \text \, a \, l' \end where ''append'' is defined as: :\text\colon A^ \to A^ \to A^ = l_1 \mapsto l_2 \mapsto \begin l_2 & \text \ l_1 = \text \\ \text \, a \, (\text \, l_1' \, l_2) & \text \ l_1 = \text \, a \, l_1' \end Alternatively, the monad may be defined in terms of operations ''return'', ''fmap'' and ''join'', with: :\text \colon (A \to B) \to (A^ \to B^) = f \mapsto l \mapsto \begin \text & \text \ l = \text\\ \text \, (f \, a) (\text f \, l') & \text \ l = \text \, a \, l' \end :\text \colon ^ \to A^ = l \mapsto \begin \text & \text \ l = \text\\ \text \, a \, (\text \, l') & \text \ l = \text \, a \, l' \end 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 In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being 0. Monoid ...
under the ''append'' operation. The identity element of the monoid is the empty list, ''nil''. In fact, this is the
free monoid In abstract algebra, the free monoid on a set is the monoid whose elements are all the finite sequences (or strings) of zero or more elements from that set, with string concatenation as the monoid operation and with the unique sequence of zero ele ...
over the set of list elements.


See also

*
Array An array is a systematic arrangement of similar objects, usually in rows and columns. Things called an array include: {{TOC right Music * In twelve-tone and serial composition, the presentation of simultaneous twelve-tone sets such that the ...
*
Queue __NOTOC__ Queue () may refer to: * Queue area, or queue, a line or area where people wait for goods or services Arts, entertainment, and media *''ACM Queue'', a computer magazine * ''The Queue'' (Sorokin novel), a 1983 novel by Russian author ...
* Set * Stack * Stream


References

{{DEFAULTSORT:List (Computing) Data types Composite data types Abstract data types