Abstract data structures

Abstract data types

In computer science, an abstract data type (ADT) is a model for data types where a data type is defined by its behavior 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).

The reason we use abstract structures is because they efficiently use memory based on the design of the data stored in them. With very large amounts of data or very frequently changing data, the data structure can make a huge difference in the efficiency (run time) of your computer program.

In more common language, an abstract data structure is a collection of related data items that a stored together in a clear, structured form.

Some types of abstract data structures

Assessed by the IB

1. static and dynamic data structure

1. arrays
2. two-dimensional arrays
3. stack
4. queue
5. linked list
6. tree
7. binary tree
8. collections
9. recursion

NOT Assessed by the IB, but you should know them

1. lists
2. dictionaries
3. sets
4. tuple
5. enum
6. struct
7. char
8. vector

Basic operations of data structures

I found this excellent slide from Simon Allardice.

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.

Standards

• Identify a situation that requires the use of recursive thinking.
• Identify recursive thinking in a specified problem solution.
• Trace a recursive algorithm to express a solution to a problem.

• Describe the characteristics of a two- dimensional array.
• Construct algorithms using two- dimensional arrays.
• Describe the characteristics and applications of a stack.

• Construct algorithms using the access methods of a stack.
• Describe the characteristics and applications of a queue.
• Construct algorithms using the access methods of a queue.
• Explain the use of arrays as static stacks and queues.
• Describe the features and characteristics of a dynamic data structure.
• Describe how linked lists operate logically.
• Sketch linked lists (single, double and circular).
• Describe the characteristics and applications of a collection.
• Construct algorithms using the access methods of a collection.
• Discuss the need for sub-programmes and collections within programmed solutions.
• Construct algorithms using pre-defined sub-programmes, one-dimensional arrays and/or collections.

• Describe how trees operate logically (both binary and non-binary).
• Define the terms: parent, left-child, right-child, subtree, root and leaf.
• State the result of inorder, postorder and preorder tree traversal.
• Sketch binary trees.
• Define the term dynamic data structure.
• Compare the use of static and dynamic data structures.
• Suggest a suitable structure for a given situation.

Produce a plan, simulation or model.

Provide an answer from a number of possibilities. Recognize and state briefly a distinguishing fact or feature.

Follow and record the action of an algorithm.

Give a detailed account or picture of a situation, event, pattern or process.

Develop information in a diagrammatic or logical form.

Give a detailed account including reasons or causes.

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

Offer a considered and balanced review that includes a range of arguments, factors or hypotheses. Opinions or conclusions should be presented clearly and supported by appropriate evidence.

Give the precise meaning of a word, phrase, concept or physical quantity.

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

Propose a solution, hypothesis or other possible answer.