 | This articleneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Collection" abstract data type – news ·newspapers ·books ·scholar ·JSTOR(October 2014) (Learn how and when to remove this message) |
Incomputer programming, acollection is anabstract data type that is a grouping of items that can be used in apolymorphic way.
Often, the items are of the samedata type such asint orstring. Sometimes the items derive from a common type; even deriving from the most general type of aprogramming language such asobject orvariant.
Although easily confused with implementations in programming languages, collection, as an abstract concept, refers to mathematical concepts which can be misunderstood when the focus is on an 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 incorrect conceptually.
Other abstract data types are more specific than collection.
Some collections maintain a linear ordering of items – with access to one or both ends. The data structure implementing such a collection need not be linear. For example, a priority queue is often implemented as aheap, which is a kind of tree.
Notable linear collections include:
Some collections are interpreted as a sort of function: given an input, the collection yields an output.
Notable associative collections include:
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 itsindicator function.
As an abstract data type, collection does not prescribe an implementation, thoughtype theory describesimplementation considerations.
Some collection types are provided asprimitive data types in a language, such as lists, while more complex collection types are implemented ascomposite data types in libraries, sometimes in a language'sstandard library. Examples include:
java.utilICollection andIReadOnlyCollection interfaces and implementations such asList<T>.Vec<T>[2] andHashMap<K, V>[3] structs) in thestd::collections namespace.[4]Collections are implemented as TYPEs. As with any programmer-defined type, you must first define the type; then you can declare instances of that type.