liveBook · Manning

Abstract data type

As explained in Advanced Algorithms and Data Structures

An abstract data type is a specification of a type's possible values, operations, computational complexities, outputs, and side effects without prescribing its storage representation.

An abstract data type (ADT) specifies a type’s possible values, permitted operations, computational complexities, outputs, and side effects without prescribing storage or physical-memory details. A data structure is the concrete implementation of that specification: its data representation plus the algorithms that manipulate it. The ADT serves users; the implementation serves implementers. section 1.1.1 section 1.4

Define an ADT as a contract before choosing its representation:

  • Specify the API, including each operation’s inputs and outputs. section 1.1.2
  • Describe high-level behavior and the guarantees visible to clients. section 1.1.2 section 2.4
  • State invariants when internal properties must remain true to preserve the contract. section 2.4
  • Choose a data model and algorithms, then analyze operation performance. section 1.1.2 section 2.4

Priority queue and heap

A priority queue ADT exposes operations such as top, peek, insert, remove, update, and size, while guaranteeing that the returned top element has the highest current priority. A heap is one concrete implementation, using an array and algorithms that preserve its invariants; a sorted list is another possible implementation. Clients can rely on the contract without depending on the representation. section 2.4

Table 2.1 API and contract for priority queue (view table figure)

Abstract data structure: Priority queue

API

 
class PriorityQueue {
  top() → element
  peek() → element
  insert(element, priority)
  remove(element)
  update(element, newPriority)
  size() → int
}

Contract with client

The top element returned by the queue is always the element with highest priority currently stored in the queue

The API-and-contract table makes the separation between client-visible behavior and implementation choices explicit. section 2.4

How Advanced Algorithms and Data Structures covers it

How deep it goes
Defines APIs, behavior, invariants, data models, algorithms, and performance, but stops short of formal axioms or physical representation details.
Examples
Uses static arrays, priority queues, sorted priority queues, and string containers to contrast specifications with concrete implementations.
What it assumes
Assumes basic data-structure and algorithm vocabulary while defining API, contract, invariants, and abstraction from first principles.
What you can do after
Evaluate/understand data-structure alternatives by separating required behavior from representation, algorithms, invariants, and operation performance.
How it connects
Connects abstract data types with APIs, data structures, algorithms, invariants, priority queues, heaps, arrays, lists, and trees.
Cover of Advanced Algorithms and Data Structures
liveBookmanning.com
Read Advanced Algorithms and Data Structures on liveBook Get the book at manning.com

Also explained in

Compare how 4 books explain abstract data type →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Advanced Algorithms and Data Structures. The section links point to the parts of the book it draws on.