In computer science, a list or sequence is an abstract data type that represents a countable 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 concept of a finite sequence; the (potentially) infinite analog of a list is a stream.[1]:§3.5 Lists are a basic example of containers, as they contain other values. If the same value occurs multiple times, each occurrence is considered a distinct item. A singly linked list structure, implementing a list with 3 integer elements. The name list is also used for several concrete data structures that can be used to implement abstract lists, especially linked lists. Many programming languages 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 spaces, within a pair of delimiters such as parentheses '()', brackets '[]', braces ' ', or angle brackets '<>'. Some languages may allow list types to be indexed or sliced like array types, in which case the data type is more accurately described as an array. In object-oriented programming languages, lists are usually provided as instances of subclasses of a generic "list" class, and traversed via separate iterators. List data types are often implemented using array data structures or linked lists of some sort, but other data structures may be more appropriate for some applications. In some contexts, such as in Lisp programming, the term list may refer specifically to a linked list rather than 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.[2] Contents 1 Operations
2 Implementations
3
5.1 The list monad 6 References 7 See also Operations[edit] 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.) Implementations[edit]
Lists are typically implemented either as linked lists (either singly
or doubly linked) or as arrays, 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,
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 or recursion. 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.[3]
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 (e1, l1) = cons (e2, l2) if e1 = e2 and l1 = l2 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, 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[edit] The list type forms a monad with the following functions (using E* rather than L to represent monomorphic lists with elements of type E): return : A → A ∗ = a ↦ cons a nil displaystyle text return colon Ato A^ * =amapsto text cons ,a, text nil bind : A ∗ → ( A → B ∗ ) → B ∗ = l ↦ f ↦ nil if l = nil append ( f a ) ( bind l ′ f ) if l = cons a l ′ displaystyle text bind colon A^ * to (Ato B^ * )to B^ * =lmapsto fmapsto begin cases text nil & text if l= text nil \ text append ,(f,a),( text bind ,l',f)& text if l= text cons ,a,l'end cases where append is defined as: append : A ∗ → A ∗ → A ∗ = l 1 ↦ l 2 ↦ l 2 if
l 1 = nil cons a ( append l 1 ′ l 2 ) if
l 1 = cons a l 1 ′ displaystyle text append colon A^ * to A^ * to A^ * =l_ 1 mapsto l_ 2 mapsto begin cases l_ 2 & text if l_ 1 = text nil \ text cons ,a,( text append ,l_ 1 ',l_ 2 )& text if l_ 1 = text cons ,a,l_ 1 'end cases Alternatively, the monad may be defined in terms of operations return, fmap and join, with: fmap : ( A → B ) → ( A ∗ → B ∗ ) = f ↦ l ↦ nil if l = nil cons ( f a ) ( fmap f l ′ ) if l = cons a l ′ displaystyle text fmap colon (Ato B)to (A^ * to B^ * )=fmapsto lmapsto begin cases text nil & text if l= text nil \ text cons ,(f,a)( text fmap f,l')& text if l= text cons ,a,l'end cases join : A ∗ ∗ → A ∗ = l ↦ nil if l = nil append a ( join l ′ ) if l = cons a l ′ displaystyle text join colon A^ * ^ * to A^ * =lmapsto begin cases text nil & text if l= text nil \ text append ,a,( text join ,l')& text if l= text cons ,a,l'end cases 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. References[edit] ^ Abelson, Harold; Sussman, Gerald Jay (1996). Structure and Interpretation of Computer Programs. MIT Press. ^ Reingold, Edward; Nievergelt, Jurg; Narsingh, Deo (1977). Combinatorial Algorithms: Theory and Practice. Englewood Cliffs, New Jersey: Prentice Hall. pp. 38–41. ISBN 0-13-152447-X. ^ Barnett, Granville; Del tonga, Luca (2008). "Data Structures and Algorithms" (PDF). mta.ca. Retrieved 12 November 2014. ^ Lerusalimschy, Roberto (December 2003). Programming in Lua (first edition) (First ed.). Lua.org. ISBN 8590379817. Retrieved 12 November 2014. ^ Steele, Guy (1990). Common Lisp (Second ed.). Digital Press. pp. 29–31. ISBN 1-55558-041-6. See also[edit] Look up list in Wiktionary, the free dictionary. Array Queue Set Stream v t e Data structures Types Collection Container Abstract Associative array Multimap List Stack Queue Double-ended queue Priority queue Double-ended priority queue Set Multiset Disjoint-set Arrays
Linked Association list Linked list Skip list Unrolled linked list XOR linked list Trees B-tree Binary search tree AA tree AVL tree Red–black tree Self-balancing tree Splay tree Heap Binary heap Binomial heap Fibonacci heap R-tree R* tree R+ tree Hilbert R-tree Trie Hash tree Graphs Binary decision diagram Directed acyclic graph Directed acyclic word graph List of data structures v t e Data types Uninterpreted Bit
Byte
Trit
Tryte
Word
Numeric Arbitrary-precision or bignum Complex Decimal Fixed point Floating point Double precision Extended precision Half precision Long double Minifloat Octuple precision Quadruple precision Single precision Integer signedness Interval Rational Pointer Address physical virtual Reference Text Character String null-terminated Composite Algebraic data type generalized Array Associative array Class Dependent Equality Inductive List Object metaobject Option type Product Record Set Union tagged Other Boolean Bottom type Collection Enumerated type Exception Function type Opaque data type Recursive data type Semaphore Stream Top type Type class Unit type Void Related topics Abstract data type Data structure Generic Kind metaclass Parametric polymorphism Primitive data type Protocol interface Subtyping Type constructor Type conversion Type system Type theory See also platform-dependent and independent units of |