In
computer programming
Computer programming is the process of performing a particular computation (or more generally, accomplishing a specific computing result), usually by designing and building an executable computer program. Programming involves tasks such as ana ...
, a collection is a grouping of some variable number of data items (possibly zero) that have some shared significance to the problem being solved and need to be operated upon together in some controlled fashion. Generally, the data items will be of the same type or, in languages supporting inheritance, derived from some common ancestor type. A collection is a concept applicable to
abstract data type
In computer science, an abstract data type (ADT) is a mathematical model for data types. An abstract data type is defined by its behavior (Semantics (computer science), semantics) from the point of view of a ''User (computing), user'', of the dat ...
s, and does not prescribe a specific implementation as a concrete
data structure
In computer science, a data structure is a data organization, management, and storage format that is usually chosen for efficient access to data. More precisely, a data structure is a collection of data values, the relationships among them, a ...
, though often there is a conventional choice (see
Container
A container is any receptacle or enclosure for holding a product used in storage, packaging, and transportation, including shipping.
Things kept inside of a container are protected on several sides by being inside of its structure. The term ...
for
type theory
In mathematics, logic, and computer science, a type theory is the formal presentation of a specific type system, and in general type theory is the academic study of type systems. Some type theories serve as alternatives to set theory as a foundat ...
discussion).
Examples of collections include
lists
A ''list'' is any set of items in a row. List or lists may also refer to:
People
* List (surname)
Organizations
* List College, an undergraduate division of the Jewish Theological Seminary of America
* SC Germania List, German rugby unio ...
,
sets,
multisets
In mathematics, a multiset (or bag, or mset) is a modification of the concept of a set that, unlike a set, allows for multiple instances for each of its elements. The number of instances given for each element is called the multiplicity of that ...
,
trees
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are u ...
and
graphs
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
.
Fixed-size arrays (or tables) are usually not considered a collection because they hold a fixed number of data items, although they commonly play a role in the implementation of collections. Variable-size arrays are generally considered collections.
Linear collections
Many collections define a particular linear ordering, with access to one or both ends. The actual data structure implementing such a collection need not be linear—for example, a priority queue is often implemented as a
heap, which is a kind of tree. Important linear collections include:
*
lists
A ''list'' is any set of items in a row. List or lists may also refer to:
People
* List (surname)
Organizations
* List College, an undergraduate division of the Jewish Theological Seminary of America
* SC Germania List, German rugby unio ...
;
*
stacks;
*
queues;
*
priority queues
In computer science, a priority queue is an abstract data-type similar to a regular queue or stack data structure in which each element additionally has a ''priority'' associated with it. In a priority queue, an element with high priority is s ...
;
*
double-ended queues;
*
double-ended priority queues.
Lists
In a list, the order of data items is significant. Duplicate data items are permitted. Examples of operations on lists are searching for a data item in the list and determining its location (if it is present), removing a data item from the list, adding a data item to the list at a specific location, etc. If the principal operations on the list are to be the addition of data items at one end and the removal of data items at the other, it will generally be called a
queue __NOTOC__
Queue () may refer to:
* Queue area, or queue, a line or area where people wait for goods or services
Arts, entertainment, and media
*''ACM Queue'', a computer magazine
* ''The Queue'' (Sorokin novel), a 1983 novel by Russian author ...
or
FIFO. If the principal operations are the addition and removal of data items at just one end, it will be called a
stack
Stack may refer to:
Places
* Stack Island, an island game reserve in Bass Strait, south-eastern Australia, in Tasmania’s Hunter Island Group
* Blue Stack Mountains, in Co. Donegal, Ireland
People
* Stack (surname) (including a list of people ...
or
LIFO. In both cases, data items are maintained within the collection in the same order (unless they are removed and re-inserted somewhere else) and so these are special cases of the list collection. Other specialized operations on lists include sorting, where, again, the order of data items is of great importance.
Stacks
A stack is a LIFO data structure with two principal operations: ''push'', which adds an element to the "top" of the collection, and ''pop'', which removes the top element.
Queues
Priority queues
In a priority queue, the tracks of the minimum or maximum data item in the collection are kept, according to some ordering criterion, and the order of the other data items does not matter. One may think of a priority queue as a list that always keeps the minimum or maximum at the head, while the remaining elements are kept in a bag.
Double-ended queues
Double-ended priority queues
Associative collections
Other collections can instead be interpreted as a sort of function: given an input, the collection yields an output. Important associative collections include:
*
sets;
*
multisets
In mathematics, a multiset (or bag, or mset) is a modification of the concept of a set that, unlike a set, allows for multiple instances for each of its elements. The number of instances given for each element is called the multiplicity of that ...
;
*
associative arrays
In computer science, an associative array, map, symbol table, or dictionary is an abstract data type that stores a collection of (key, value) pairs, such that each possible key appears at most once in the collection. In mathematical terms an a ...
.
A set can be interpreted as a specialized multiset, which in turn is a specialized associative array, in each case by limiting the possible values—considering a set as represented by its
indicator function
In mathematics, an indicator function or a characteristic function of a subset of a set is a function that maps elements of the subset to one, and all other elements to zero. That is, if is a subset of some set , one has \mathbf_(x)=1 if x\i ...
.
Sets
In a set, the order of data items does not matter (or is undefined) but duplicate data items are not permitted. Examples of operations on sets are the addition and removal of data items and searching for a data item in the set. Some languages support sets directly. In others, sets can be implemented by a
hash table
In computing, a hash table, also known as hash map, is a data structure that implements an associative array or dictionary. It is an abstract data type that maps keys to values. A hash table uses a hash function to compute an ''index'', als ...
with dummy values; only the keys are used in representing the set.
Multisets
In a multiset (or bag), like in a set, the order of data items does not matter, but in this case duplicate data items are permitted. Examples of operations on multisets are the addition and removal of data items and determining how many duplicates of a particular data item are present in the multiset. Multisets can be transformed into lists by the action of sorting.
Associative arrays
In an associative array (or map, dictionary, lookup table), like in a dictionary, a lookup on a ''key'' (like a word) provides a ''value'' (like a definition). The value might be a reference to a compound data structure. A
hash table
In computing, a hash table, also known as hash map, is a data structure that implements an associative array or dictionary. It is an abstract data type that maps keys to values. A hash table uses a hash function to compute an ''index'', als ...
is usually an efficient implementation, and thus this data type is often known as a "hash".
Graphs
In a graph, data items have associations with one or more other data items in the collection and are somewhat like trees without the concept of a ''root'' or a ''parent-child relationship'' so that all data items are peers. Examples of operations on graphs are traversals and searches which explore the associations of data items looking for some specific property. Graphs are frequently used to model real-world situations and to solve related problems. An example is the
Spanning tree protocol
The Spanning Tree Protocol (STP) is a network protocol that builds a loop-free logical topology for Ethernet networks. The basic function of STP is to prevent bridge loops and the broadcast radiation that results from them. Spanning tree also al ...
, which creates a graph (or mesh) representation of a data network and figures out which associations between switching nodes need to be broken to turn it into a tree and thus prevent data going around in loops.
Trees
In a tree, which is a special kind of graph, a ''root'' data item has associated with it some number of data items which in turn have associated with them some number of other data items in what is frequently viewed as a ''parent-child relationship''. Every data item (other than the root) has a single parent (the root has no parent) and some number of children, possibly zero. Examples of operations on trees are the addition of data items so as to maintain a specific property of the tree to perform sorting, etc. and traversals to visit data items in a specific sequence.
Tree collections can be used to naturally store hierarchical data, which is presented in a tree-like manner, such as menu systems and files in directories on a data storage system.
Specialized trees are used in various algorithms. For example, the
heap sort
In computer science, heapsort is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort: like selection sort, heapsort divides its input into a sorted and an unsorted region, and it iteratively shrinks the ...
uses a kind of tree called a
heap.
Abstract concept vs. implementation
As described here, a collection and the various kinds of collections are abstract concepts. There exists in the literature considerable confusion between the abstract concepts of computer science and their specific implementations in various languages or kinds of languages. Assertions that collections like lists, sets, trees, etc. are data structures, abstract data types or classes must be read with this in mind. Collections are first and foremost abstractions that are useful in formulating solutions to computing problems. Viewed in this light, they retain important links to underlying mathematical concepts which can be lost when the focus is on the implementation.
For example, a priority queue is often implemented as a heap, while an associative array is often implemented as a hash table, so these abstract types are often referred to by this preferred implementation, as a "heap" or a "hash", though this is not strictly correct.
Implementations
Some collections may be ''
primitive data type
In computer science, primitive data types are a set of basic data types from which all other data types are constructed. Specifically it often refers to the limited set of data representations in use by a particular processor, which all compiled pr ...
s'' in a language, such as lists, while more complex collections are implemented as ''
composite data type
In computer science, a composite data type or compound data type is any data type which can be constructed in a program using the programming language's primitive data types and other composite types. It is sometimes called a structure or aggreg ...
s'' in libraries, sometimes in the
standard library
In computer programming, a standard library is the library made available across implementations of a programming language. These libraries are conventionally described in programming language specifications; however, contents of a language's as ...
. Examples include:
* C++: known as "
container
A container is any receptacle or enclosure for holding a product used in storage, packaging, and transportation, including shipping.
Things kept inside of a container are protected on several sides by being inside of its structure. The term ...
s", implemented in
C++ Standard Library
The C standard library or libc is the standard library for the C programming language, as specified in the ISO C standard.ISO/IEC (2018). '' ISO/IEC 9899:2018(E): Programming Languages - C §7'' Starting from the original ANSI C standard, it wa ...
and earlier
Standard Template Library
The Standard Template Library (STL) is a Library (computer science), software library originally designed by Alexander Stepanov for the C++ programming language that influenced many parts of the C++ Standard Library. It provides four components ...
* Java: implemented in the
Java collections framework
The Java collections framework is a set of classes and interfaces that implement commonly reusable collection data structures.
Although referred to as a framework, it works in a manner of a library. The collections framework provides both interf ...
* Oracle
PL/SQL
PL/SQL (Procedural Language for SQL) is Oracle Corporation's procedural extension for SQL and the Oracle relational database. PL/SQL is available in Oracle Database (since version 6 - stored PL/SQL procedures/functions/packages/triggers since ...
implements collections as programmer-defined types
[
]
* Python: some built-in, others implemented in th
collectionslibrary
References
External links
Apache Commons Collections
AS3Commons Collections FrameworkActionScript3 implementation of the most common collections.
CollectionSpy— A profiler for Java's Collections Framework.
Guava
Mango Java library
{{DEFAULTSORT:Collection
Abstract data types