Look up list in
Wiktionary, the free dictionary.

About lists in Wikipedia: Wikipedia:Lists

This article is about the word list as used in computer science. For other uses, see list (disambiguation).

In computer science, a list is a collection of entities/items. Wikipedia does not have an article with this exact name. ... Wiktionary (a portmanteau of wiki and dictionary) is a multilingual, Web-based project to create a free content dictionary, available in over 150 languages. ... List can refer to: Lists in computer science Task lists, also known as to-do lists. ... Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... In mathematics, a multiset (sometimes also called a bag) differs from a set in that each member has a multiplicity, which is a natural number indicating (loosely speaking) how many times it is a member, or perhaps how many memberships it has in the multiset. ... An entity is something that has a distinct, separate existence, though it need not be a material existence. ... Look up item in Wiktionary, the free dictionary. ...

In the context of object-oriented programming languages, a list is defined as an instance of an abstract data type (ADT), formalizing the concept of an ordered collection of entities. For example, an ADT for untyped, mutable lists may be specified in terms of a constructor and four operations: An object-oriented programming language (also called an OO language) is one that allows or encourages, to some degree, object-oriented programming techniques such as encapsulation, inheritance, interfaces, and polymorphism. ... An object is fundamental concept in object-oriented programming. ... In computing, an abstract data type (ADT) is a specification of a set of data and the set of operations that can be performed on the data. ... For other uses, see Concept (disambiguation). ... Order theory is a branch of mathematics that studies various kinds of binary relations that capture the intuitive notion of a mathematical ordering. ... In object-oriented programming, a collection class is any class that is capable of storing other objects. ... An entity is something that has a distinct, separate existence, though it need not be a material existence. ... In computer science, an immutable object, as opposed to a mutable object, is a kind of object whose internal states cannot be modified. ... Constructor is possibly one of a number of things: a model or a plan for contruction of something, for example a blueprint a special method used in object oriented programming which puts the objects members into a valid state. ... In logic and mathematics, an operation ω is a function of the form ω : X1 × … × Xk → Y. The sets Xj are the called the domains of the operation, the set Y is called the codomain of the operation, and the fixed non-negative integer k is called the arity of the operation. ...

• 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 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 (or its "tail")

An example of a list - a single linked-list, with 3 integer values

In practice, lists are usually implemented using arrays or linked lists of some sort; due to lists sharing certain properties with arrays and linked lists. Informally, the term list is sometimes used synonymously with linked list. A sequence is another name, emphasizing the ordering and suggesting that it may not be a linked list. A singly-linked list diagram for the Linked List page, made in Illustrator by Derrick Coetzee. ... A singly-linked list diagram for the Linked List page, made in Illustrator by Derrick Coetzee. ... This article does not cite any references or sources. ... In computer science, a linked list is one of the fundamental data structures, and can be used to implement other data structures. ... In computer science, a linked list is one of the fundamental data structures, and can be used to implement other data structures. ...

Characteristics

Lists have the following properties:

• The size of lists. It indicates how many elements there are in the list.
• Equality of lists:
  • In mathematics, 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 structural equality of the corresponding entries, except that if the lists are typed, then the list types may also be relevant.
• Lists may be typed. This implies that the entries in a list must have types that are compatible with the list's type. It is common that lists are typed when they are implemented using arrays.
• Each element in the list has an index. The first element has index 0 (or some other predefined integer). Subsequent elements have indices that are 1 higher than the previous element. The last element has index (initial index) + (size) − 1.
  • It is possible to retrieve the element at a particular index.
  • It is possible to traverse the list in the order of increasing index.
  • It is possible to change the element at a particular index to a different value, without affecting any other elements.
  • It is possible to insert an element at a particular index. The indices of elements at higher indices are increased by 1.
  • It is possible to remove an element at a particular index. The indices of elements at higher indices are decreased by 1.

In mathematics, two mathematical objects are considered equal if they are precisely the same in every way. ... An identity in object-oriented programming, object-oriented design and object-oriented analysis describes the property of objects that the object can be distinguished from other objects. ... A programming language is an artificial language that can be used to control the behavior of a machine, particularly a computer. ... In computer science, a datatype or data type (often simply a type) is a name or label for a set of values and some operations which one can perform on that set of values. ...

Applications

As the name implies, lists can be used to store a list of records. The items in a list can be sorted or unsorted for the purpose of fast search (binary search for instance) or fast inserting. In computer science, binary search or binary chop is a search algorithm for finding a particular value in a linear array, by ruling out half of the data at each step. ...

Implementations

There are two main ways to implement lists: linked lists (either singly or doubly-linked) and dynamic arrays. See those articles for more information. In computer science, a linked list is one of the fundamental data structures, and can be used to implement other data structures. ... A dynamic array, growable array, resizable array, dynamic table, or array list is a data structure, an array which is automatically expanded to accommodate new objects if filled beyond its current size. ...

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. Lisp is a family of computer programming languages with a long history and a distinctive fully-parenthesized syntax. ... Scheme is a multi-paradigm programming language. ...

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. However, some LISP implementations (such as the LISP used for the Symbolics 3600) often use "compressed lists" which are arrays. In computer science, a linked list is one of the fundamental data structures, and can be used to implement other data structures. ... In computer science, a tree is a widely-used computer data structure that emulates a tree structure with a set of linked nodes. ...

Some languages do not offer a list data structure, but offer the use of associative arrays 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 hash tables. A binary tree, a simple type of branching linked data structure. ... An associative array (also map, hash, dictionary, finite map, lookup table, and in query-processing an index or index file) is an abstract data type composed of a collection of keys and a collection of values, where each key is associated with one value. ... The Lua (pronounced LOO-ah, or in IPA) programming language is a lightweight, reflective, imperative and procedural language, designed as a scripting language with extensible semantics as a primary goal. ...

Some languages implement lists using arrays. This article does not cite any references or sources. ...

Lists can be manipulated using iteration or recursion. The former is often preferred in non-tail-recursive languages, and languages in which recursion over lists is for some other reason uncomfortable. The latter is generally preferred in functional languages, since iteration is associated with arrays and often regarded as imperative. The word iteration is sometimes used in everyday English with a meaning virtually identical to repetition. ... A visual form of recursion known as the Droste effect. ... In computer science, tail recursion is a special case of recursion that can be transformed into an iteration. ... Functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions. ... In computer science, imperative programming, as opposed to declarative programming, is a programming paradigm that describes computation in terms of a program state and statements that change the program state. ...

Because in computing, lists are easier to realize than sets, a finite set in mathematical sense can be realized as a list with additional restrictions, that is, duplicate elements are disallowed and such that order is irrelevant. If the list is sorted, it 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. In mathematics, a set can be thought of as any collection of distinct objects considered as a whole. ... In computing, a self-balancing binary search tree or height-balanced binary search tree is a binary search tree that attempts to keep its height, or the number of levels of nodes beneath the root, as small as possible at all times, automatically. ... In computer science, a hash table is a data structure that speeds up searching for information by a particular aspect of that information, called a key. ...