Collection Data Structure Pattern

From GM-RKB
(Redirected from Container ADT)
Jump to navigation Jump to search

A Collection Data Structure Pattern is a data structure pattern that supports the Put Operation and the Get Operation.

References

2013

  • (Wikipedia, 2013) ⇒ http://en.wikipedia.org/wiki/Collection_(abstract_data_type) Retrieved:2013-12-1.
    • In computer science, a collection or container 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 (type theory) for type theory discussion.

      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.

      A fixed-size 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. Variable-sized arrays are generally considered collections, and fixed-size arrays may likewise considered a collection, albeit with limitations.

1997

  • (Skiena, 1997) ⇒ Steven S. Skiena. (1997). “The Algorithm Design Manual." - "Fundamental Data Types - Containers”. Springer-Verlag. ISBN:0387948600
    • Containers are abstract data types that hold stuff. They don't do much more than hold it so that it can be retrieved later. Still, they are critical to the functioning of society. We will use the term container to denote a data structure that permits storage and retrieval of data items independently of content. The two fundamental operations of any container are:
      • Put(C,x): Insert a new data item x into the container C.
      • Get(C): Retrieve the next item from the container C. Different types of containers support different retrieval orders, based on insertion order or position.
    • Containers are typically most useful when they will contain only a limited number of items and when the retrieval order is predefined or irrelevant. The most popular type of containers are:
      • Stacks: Supports retrieval in last in, first out order (LIFO). Stacks are simple to implement, and very efficient. Indeed, stacks are probably the right container to use when the retrieval order doesn't matter at all, as when processing batch jobs. The put and get operations for stacks are usually called push and pop.
      • Queues: Supports retrieval in first in, first out order (FIFO). FIFO may seem the fairest way to control waiting times. However, for many applications, data items have infinite patience. Queues are trickier to implement than stacks and are appropriate only for applications (like certain simulations) where the order is important. The put and get operations for queues are usually called enqueue and dequeue.
      • Tables: Supports retrieval by position, so that put and get each accept an index as an argument. Tables are naturally implemented using arrays.
    • Each of these containers can be implemented using either arrays or linked lists. With the exception of tables, the choice of lists versus tables probably doesn't matter very much. The key issue is whether an upper bound on the size of the container is known in advance, thus permitting a statically allocated array. Using arrays, put and get can be implemented in constant time per operation for each of the containers.
Retrieved from "http://www.gabormelli.com/RKB/index.php?title=Collection_Data_Structure_Pattern&oldid=808156"