Collection (abstract data type)

In computer programming, 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 types, and does not prescribe a specific implementation as a concrete data structure, though often there is a conventional choice (see Container for type theory discussion). Examples of collections include lists, sets, multisets, trees and graphs. 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. 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; stacks; queues; priority queues; double-ended queues; double-ended priority queues. List (abstract data type) 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 or FIFO. If the principal operations are the addition and removal of data items at just one end, it will be called a stack 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.