List (abstract data type)
   HOME

TheInfoList



OR:

In
computer science Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
, a list or sequence is a collection of items that are finite in number and in a particular order. An instance of a list is a computer representation of the
mathematical Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
concept of a tuple 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 cal ...
. A list may contain the same value more than once, and each occurrence is considered a distinct item. The term ''list'' is also used for several concrete
data structure In computer science, a data structure is a data organization and storage format that is usually chosen for Efficiency, efficient Data access, access to data. More precisely, a data structure is a collection of data values, the relationships amo ...
s that can be used to implement abstract lists, especially
linked list In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes whi ...
s and arrays. In some contexts, such as in
Lisp Lisp (historically LISP, an abbreviation of "list processing") is a family of programming languages with a long history and a distinctive, fully parenthesized Polish notation#Explanation, prefix notation. Originally specified in the late 1950s, ...
programming, the term ''list'' may refer specifically to a linked list rather than an array. In class-based programming, lists are usually provided as instances of subclasses of a generic "list" class, and traversed via separate iterators. Many
programming language A programming language is a system of notation for writing computer programs. Programming languages are described in terms of their Syntax (programming languages), syntax (form) and semantics (computer science), semantics (meaning), usually def ...
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, semicolons, and/or
space Space is a three-dimensional continuum containing positions and directions. In classical physics, physical space is often conceived in three linear dimensions. Modern physicists usually consider it, with time, to be part of a boundless ...
s, within a pair of delimiters such as parentheses '()', 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 and theoretical computer science, a type theory is the formal presentation of a specific type system. Type theory is the academic study of type systems. Some type theories serve as alternatives to set theory as a foundation of ...
and
functional programming In computer science, functional programming is a programming paradigm where programs are constructed by Function application, applying and Function composition (computer science), composing Function (computer science), functions. It is a declarat ...
, 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. A
stream A stream is a continuous body of water, body of surface water Current (stream), flowing within the stream bed, bed and bank (geography), banks of a channel (geography), channel. Depending on its location or certain characteristics, a strea ...
is the potentially infinite analog of a list.


Operations

Implementation of the list data structure may provide some of the following operations: * create * test for empty * add item to beginning or end * access the first or last item * access an item by index


Implementations

Lists are typically implemented either as
linked list In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes whi ...
s (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 Lisp (historically LISP, an abbreviation of "list processing") is a family of programming languages with a long history and a distinctive, fully parenthesized Polish notation#Explanation, prefix notation. Originally specified in the late 1950s, ...
, 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 In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes whi ...
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, e.g., including only woody plants with secondary growth, only ...
, 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 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 occurs when the definition of a concept or process depends on a simpler or previous version of itself. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in m ...
. The former is often preferred in imperative programming languages, while the latter is the norm in functional languages. Lists can be implemented as self-balancing binary search trees 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 In computer science, a data structure is a data organization and storage format that is usually chosen for Efficiency, efficient Data access, access to data. More precisely, a data structure is a collection of data values, the relationships amo ...
, but offer the use of
associative array In computer science, an associative array, key-value store, 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 math ...
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. In
Lisp Lisp (historically LISP, an abbreviation of "list processing") is a family of programming languages with a long history and a distinctive, fully parenthesized Polish notation#Explanation, prefix notation. Originally specified in the late 1950s, ...
, 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

Unlike in an array, a list can expand and shrink. 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 trees or hash tables, rather than a list. Lists also form the basis for other abstract data types including the queue, 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 and theoretical computer science, a type theory is the formal presentation of a specific type system. Type theory is the academic study of type systems. Some type theories serve as alternatives to set theory as a foundation of ...
, 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''): :\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 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.


See also

* * * * *


References

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