Collection (computing)

Collection (computing)

In computer science, 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 table (or array) is usually not considered a collection because it holds a fixed number of items, although tables/arrays commonly play a role in the implementation of collections.

Some different kinds of collections are lists, sets, bags (or multisets), trees and graphs. An enumerated type may be either a list or a set.

Contents

Lists

In a list, the order of data items is significant. Duplicate data items are permitted. Examples of operations on lists are searching for an item in the list and determining its location (if it is present), removing an item from the list, adding an item at a specific location, etc. If the principal operations on the list are to be the addition of items at one end and the removal of items at the other, it will generally be called a queue or FIFO. If the principal operations are the addition and removal of items at just one end, it will be called a stack or LIFO. In both cases, 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 items is of great importance.

Sets

In a set, the order of data items is of no consequence, but duplicate items are not permitted. Examples of operations on sets are the addition and removal of items and searching for an item in the set. Some languages support sets directly. In others, sets can be implemented by a hash table with dummy values; only the keys are used in representing the set.

Bags

A "bag" or multiset, is like a set - the order of data items is of no consequence. But in this case, duplicate items are permitted. Examples of operations on bags are the addition and removal of items and determining how many of a particular item are present in the bag. Bags can be transformed into lists by the action of sorting.

Associative arrays

An associative array or "lookup table" acts like a dictionary, providing a "value" (like a definition) in response to a lookup on a "key" (like a word). The "value" might be a reference to a compound data structure. A hash table is usually an efficient implementation.

Trees

In a tree, a 'root' data item has associated with it some number of data items which in turn have associated with them some number of other items in what is frequently viewed as parent-child relationships. Every 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. A tree used for sorting operations is usually called a heap. Tree collections are also used to store data that is presented in a tree-like manner, such as menu systems and files in directories on a data storage system.

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 the 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, 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.

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, 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.

See also

External links


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Collection — For works entitled The Collection, see The Collection (disambiguation). Collection or Collections may refer to: Collection (computing), the abstract concept of collections in computer science Collection (payment), the actions of a creditor… …   Wikipedia

  • History of computing hardware — Computing hardware is a platform for information processing (block diagram) The history of computing hardware is the record of the ongoing effort to make computer hardware faster, cheaper, and capable of storing more data. Computing hardware… …   Wikipedia

  • Pointer (computing) — This article is about the programming data type. For the input interface (for example a computer mouse), see Pointing device. Pointer a pointing to the memory address associated with variable b. Note that in this particular diagram, the computing …   Wikipedia

  • Wikipedia:Reference desk/Computing — The Wikipedia Reference Desk covering the topic of computing. Computing #eee #f5f5f5 #eee #aaa #aaa #aaa #00f #36b #000 #00f computing Wikipedia:Reference de …   Wikipedia

  • Kernel (computing) — A kernel connects the application software to the hardware of a computer In computing, the kernel is the main component of most computer operating systems; it is a bridge between applications and the actual data processing done at the hardware… …   Wikipedia

  • List of books on the history of computing — Early popularizations (not written as history) = *Edmund Callis Berkeley, Giant Brains, or Machines That Think , 1949, John Wiley Sons, ISBN 0 471 06996 5 A contemporary book about computers. *Wallace J. Eckert and Rebecca Jones, Faster, Faster:… …   Wikipedia

  • List of computing and IT abbreviations — This is a list of computing and IT acronyms and abbreviations. Contents: 0–9 A B C D E F G H I J K L M N O P Q R S T U V W X Y …   Wikipedia

  • Legal aspects of computing — Part of a series on the Legal aspects of computing Major topics File sharing Legal aspects of hyperlinking and framing Lesser or historical topics Spamming …   Wikipedia

  • Hacker (computing) — In computing, hacker has several meanings: [cite web|url=http://webzone.k3.mah.se/k3jolo/HackerCultures/origins.htm|title=webzone.k3.mah.se/k3jolo/HackerCultures/origins.htm ] * A community of enthusiast computer programmers and systems designers …   Wikipedia

  • Decentralized computing — is the allocation of resources, both hardware and software, to each individual workstation, or office location. In contrast, centralized computing exists when the majority of functions are carried out, or obtained from a remote centralized… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”