By definition, 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.
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 (quote (1 2 3)).
In Ruby and Prolog, lists can be written like:
[1,2,4.5,"hello",[1,2,3]]
In Java, List is an interface in the standard library java.util.List; the type of all entries must be Object.
C++ provides general list facilities in its Standard Template Library (STL).
Some languages do not offer a list data structure, but offer the use of associative arrays or some kind of table to emulate lists.
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 or not. Some languages may instead implement lists using other data structures, such as arrays.
Lists can be manipulated using iteration or recursion.
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).