List
In computer science, a list is a kind of data structure or abstract data type.In concrete terms, a list is a (possibly empty) sequence, that is, an ordered collection of elements in which repetition is allowed. The elements are usually referred to as entries. In some programming languages, it is possible to specify infinite lists, but in most contexts, the length of a list is constrained to be finite but allowed to vary.
In some programming and data definition languages, lists are typed. This implies that the entries in a list must have typess that are compatible with the list's type.
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 equality of the corresponding entries, except that if the lists are typed, then the list types may also be relevant.
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
In Python, Ruby and Prolog, a list can be written as
In Java,
C++ provides general list facilities in its Standard Template Library (STL). It is important to note that in C++ all items in a list must be of the same type.
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.
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. Some languages may instead implement lists using other data structures, such as arrays. However, it is generally assumed that elements can be inserted into a list in constant time, while access of a random element in a list requires linear time; this is to be contrasted with an array (or vector), for which the time complexities are reversed.
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.
An array is normally a typed list whose length is fixed within a certain context.
Nearly all kinds of tree structures can also be stored as lists.
A finite mathematical set can be thought of as a list in which duplicate elements are disallowed and such that order is irrelevant; in fact, sets are commonly implemented as lists in which the entries are unique and sorted (for efficiency).Equality of lists
Lists in programming languages
(list 2 3 5). In several dialects of Lisp, including Scheme, a list is collection of pairs, consisting of a value and a pointer to the next pair (or null value).[1, 2, 4.5, "hello", [1, 2, 3]].List is an interface in the standard library package java.util. All items in such a list must have reference type; i.e., they must be instances of the class named Object (which all objects are, by definition).Related concepts