Data Structure Pattern

An Data Structure Pattern is a pattern of a data structure.

• AKA: Abstract Data Type, ADT.
• Context:
  • It can (typically) define common Data Operations (such as a push operation).
  • It can range from being a Simple ADT to being a Complex ADT.
  • It can be referenced by a Data Structure.
  • It can be supported by a Software Library.
  • …
• Example(s):
  • a Scalar Data Structure Pattern.
  • a Queue Data Structure Pattern.
  • a Collection Data Structure Pattern for an collection data structure.
  • a Dictionary Data Structure Pattern for a Dictionary Data Structure.
  • a Graph Data Structure Pattern for a graph data structure.
  • an Array Data Structure Pattern.
  • a Hash Data Structure Pattern.
  • a Linked List Data Structure Pattern.
  • …
• Counter-Example(s):
  • an Algorithm Pattern.
• See: Data Model, Object Oriented Data Model, Entity-Relationship Model.

---

---

References

2013

• http://en.wikipedia.org/wiki/Abstract_data_type
  • In computer science, an abstract data type (ADT) is a mathematical model for a certain class of data structures that have similar behavior; or for certain data types of one or more programming languages that have similar semantics. An abstract data type is defined indirectly, only by the operations that may be performed on it and by mathematical constraints on the effects (and possibly cost) of those operations.

    For example, an abstract stack could be defined by three operations: push, that inserts some data item onto the structure, pop, that extracts an item from it (with the constraint that each pop always returns the most recently pushed item that has not been popped yet), and peek, that allows data on top of the structure to be examined without removal. When analyzing the efficiency of algorithms that use stacks, one may also specify that all operations take the same time no matter how many items have been pushed into the stack, and that the stack uses a constant amount of storage for each element.

    Abstract data types are purely theoretical entities, used (among other things) to simplify the description of abstract algorithms, to classify and evaluate data structures, and to formally describe the type systems of programming languages. However, an ADT may be implemented by specific data types or data structures, in many ways and in many programming languages; or described in a formal specification language. ADTs are often implemented as modules: the module's interface declares procedures that correspond to the ADT operations, sometimes with comments that describe the constraints. This information hiding strategy allows the implementation of the module to be changed without disturbing the client programs.

    The term abstract data type can also be regarded as a generalised approach of a number of algebraic structures, such as lattices, groups, and rings. This can be treated as part of the subject area of artificial intelligence. The notion of abstract data types is related to the concept of data abstraction, important in object-oriented programming and design by contract methodologies for software development

2012

• http://en.wikibooks.org/wiki/A-level_Computing/AQA/Problem_Solving,_Programming,_Operating_Systems,_Databases_and_Networking/Programming_Concepts/Abstract_data_types_and_data_structures
  • In Computer Science an abstract data type (ADT) is a mathematical model for a certain data types or structures. This doesn't mean that the ADTs can't be programmed, but that we must first understand them mathematically before we can implement them. ADTs are generally complex things that you have functions and procedures to interface with.

• (Elkner et al., 2012) ⇒ Jeffrey Elkner, Allen B. Downey, and Chris Meyers. (20120. “How to Think Like a Computer Scientist - Learning with Python (2nd edition)." - 19.1 - Abstract Data Types”.
  • QUOTE: The data types you have seen so far are all concrete, in the sense that we have completely specified how they are implemented. For example, the Card class represents a card using two integers. As we discussed at the time, that is not the only way to represent a card; there are many alternative implementations.

    An abstract data type, or ADT, specifies a set of operations (or methods) and the semantics of the operations (what they do), but it does not not specify the implementation of the operations. That’s what makes it abstract.

    Why is that useful?

    1. It simplifies the task of specifying an algorithm if you can denote the operations you need without having to think at the same time about how the operations are performed.
    2. Since there are usually many ways to implement an ADT, it might be useful to write an algorithm that can be used with any of the possible implementations.
    3. Well-known ADTs, such as the Stack ADT in this chapter, are often implemented in standard libraries so they can be written once and used by many programmers.
    4. The operations on ADTs provide a common high-level language for specifying and talking about algorithms.
  • When we talk about ADTs, we often distinguish the code that uses the ADT, called the client code, from the code that implements the ADT, called the provider code.

---