Abstract data structures

From Computer Science Wiki
Jump to: navigation, search
Abstract data types[1]

In computer science, an abstract data type (ADT) is a mathematical model for data types where a data type is defined by its behavior (semantics) from the point of view of a user of the data, specifically in terms of possible values, possible operations on data of this type, and the behavior of these operations. This contrasts with data structures, which are concrete representations of data, and are the point of view of an implementer, not a user.

Formally, an ADT may be defined as a "class of objects whose logical behavior is defined by a set of values and a set of operations"; this is analogous to an algebraic structure in mathematics. What is meant by "behavior" varies by author, with the two main types of formal specifications for behavior being axiomatic (algebraic) specification and an abstract model; these correspond to axiomatic semantics and operational semantics of an abstract machine, respectively. Some authors also include the computational complexity ("cost"), both in terms of time (for computing operations) and space (for representing values).[2]

In more common language, a data structure is just some arrangement of data that we've built into an orderly arrangement.

Some types of abstract data structures

  1. arrays
  2. stack
  3. queue
  4. linked list
  5. tree
  6. binary tree
  7. collections
  8. lists
  9. dictionaries
  10. sets
  11. tuple

We might use recursion to move through an abstract data structure.

Basic operations of data structures

I found this excellent slide from Simon Allardice.

Basic operations of arrays.png

Comparison of different data structures

Data Structure Strengths Weaknesses
arrays Inserting and deleting elements, iterating through the collection Sorting and searching, Inserting and deleting - especially if you are inserting and deleting at the beginning or the end of the array
linked list direct indexing, Easy to create and use direct access, searching and sorting
stack and queue designed for LIFO / FIFO direct access, searching and sorting
binary tree speed of insertion and deletion, speed of access, maintaining sorted order some overhead


  • Fixed structures are faster / smaller
  • When you are considering if you should use an abstract data structure, you should ask yourself: what holds the most data and what holds the most frequently changed data?

Comparison of static vs dynamic data structures

This comparison is used from our computer science textbook.

Static data structure Dynamic data structure
Inefficient as memory is allocated that may not be needed. Efficient as the amount of memory varies as needed.
Fast access to each element of data as the memory location is fixed when the program is written. Slower access to each element as the memory location is allocated at run-time.
Memory addresses allocated will be contiguous so quicker to access. Memory addresses allocated may be fragmented so slower to access.
Structures are a fixed size, making them more predictable to work with. For example, they can contain a header. Structures vary in size so there needs to be a mechanism for knowing the size of the current structure.
The relationship between different elements of data does not change. The relationship between different elements of data will change as the program is run.

Choosing which data structure to use

This graphic is used with tremendous gratitude from Dartford Grammar School Computer Science Department.

Choosing a data type flow chart.png

Standards

  • IdentifyProvide an answer from a number of possibilities. Recognize and state briefly a distinguishing fact or feature. a situation that requires the use of recursive thinking.
  • IdentifyProvide an answer from a number of possibilities. Recognize and state briefly a distinguishing fact or feature. recursive thinking in a specified problem solution.
  • TraceFollow and record the action of an algorithm. a recursive algorithm to express a solution to a problem.
  • DescribeGive a detailed account or picture of a situation, event, pattern or process. the characteristics of a two- dimensional array.
  • ConstructDevelop information in a diagrammatic or logical form. algorithms using two- dimensional arrays.
  • DescribeGive a detailed account or picture of a situation, event, pattern or process. the characteristics and applications of a stack.
  • ConstructDevelop information in a diagrammatic or logical form. algorithms using the access methods of a stack.
  • DescribeGive a detailed account or picture of a situation, event, pattern or process. the characteristics and applications of a queue.
  • ConstructDevelop information in a diagrammatic or logical form. algorithms using the access methods of a queue.
  • ExplainGive a detailed account including reasons or causes. the use of arrays as static stacks and queues.
  • DescribeGive a detailed account or picture of a situation, event, pattern or process. the features and characteristics of a dynamic data structure.
  • DescribeGive a detailed account or picture of a situation, event, pattern or process. how linked lists operate logically.
  • SketchRepresent by means of a diagram or graph (labelled as appropriate). The sketch should give a general idea of the required shape or relationship, and should include relevant features. linked lists (single, double and circular).
  • DescribeGive a detailed account or picture of a situation, event, pattern or process. how trees operate logically (both binary and non-binary).
  • DefineGive the precise meaning of a word, phrase, concept or physical quantity. the terms: parent, left-child, right-child, subtree, root and leaf.
  • StateGive a specific name, value or other brief answer without explanation or calculation.Give a specific name, value or other brief answer without explanation or calculation. the result of inorder, postorder and preorder tree traversal.
  • SketchRepresent by means of a diagram or graph (labelled as appropriate). The sketch should give a general idea of the required shape or relationship, and should include relevant features. binary trees.
  • DefineGive the precise meaning of a word, phrase, concept or physical quantity. the term dynamic data structure.
  • Compare the use of static and dynamic data structures.
  • SuggestPropose a solution, hypothesis or other possible answer. a suitable structure for a given situation.

References

  1. http://www.flaticon.com/
  2. https://en.wikipedia.org/wiki/Abstract_data_type