List (computing)


List (computing)

In computer science, a list is an ordered collection of entities/items.

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:

* 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")

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.

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.

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.

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 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.

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.

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.

Some languages implement lists using arrays.

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.

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.


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • List — or lists may refer to:* A mailing list * Comma separated lists, a common way of listing in everyday life and computing. ( British usage : Comma separated values) * An electronic mailing list * An electoral list * List (computing) * Lists… …   Wikipedia

  • Computing Research Association — The Computing Research Association (CRA) is an association of more than 220 North American academic departments of computer science, computer engineering, and related fields; laboratories and centers in industry, government, and academia engaging …   Wikipedia

  • List of British Jewish scientists — is a list that includes scientists from the United Kingdom and its predecessor states who are or were Jewish or of Jewish descent. Physicists * Petrus Alphonsi, Spanish born astronomer and doctor [Oxford Dictionary of National Biography, art.… …   Wikipedia

  • List of schools in East Sussex — List of primary schools, middle schools, secondary schools, special schools, further education colleges and universities in the county of East Sussex, England. [cite web |url=http://www.eastsussex.gov.uk/educationandlearning/schools/schoolsearch/s… …   Wikipedia

  • List of Pennsylvania firsts — List of Pennsylvania firstsPennsylvania was the second state , but it was first in many respects: Firsts * 1688 mdash; First public protest of slavery in America, Germantown, (now part of Philadelphia) [ [http://www.religioustolerance.org/chr… …   Wikipedia

  • List of schools in Kent — List of primary schools, middle schools, secondary schools, special schools, further education colleges and universities in the ceremonial county of Kent, England. [cite web | title = UK Schools Colleges Database | publisher = Schools Web… …   Wikipedia

  • List of computing topics — Originally, the word computing was synonymous with counting and calculating, and the science and technology of mathematical calculations. Today, computing means using computers and other computing machines. It includes their operation and usage,… …   Wikipedia

  • List of computer science conferences — This is a list of academic conferences in computer science. Most of these academic conferences are annual or bi annual events.The order with which the conferences are listed in their respective fields corresponds to a rough and non authoritative… …   Wikipedia

  • List of important publications in computer science — This is a list of important publications in computer science, organized by field. Some reasons why a particular publication might be regarded as important: Topic creator – A publication that created a new topic Breakthrough – A publication that… …   Wikipedia

  • List of schools in Yorkshire and the Humber — The following is a partial list of currently operating schools in the Yorkshire and the Humber region of England. You may also find of use to find a particular school. See also the List of the oldest schools in the United Kingdom.Listed by local… …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.