Data Structure + Abstract Data Type

Abstract data types and data structures are sometimes used interchangeably, the line between them can be blurry.

Resources

• https://www.bigocheatsheet.com/
• https://opendatastructures.org/newhtml/ods/latex/index.html

Abstract Data Types (ADTs)

• Stack
• Queue
• Deque
• Priority Queue
• Dictionary
• Set
• Sequence

An Abstract Data Type (ADT) is just mathematical entity. It is understandable by looking only at its API (not the code underneath)

ADTs define the operations:

• Each operation has
  • A signature $\to$ describes the params + the type of the returned value
  • A pre-condition (logic statement) $\to$ specifies what is assumed to be true before the operation may be applied
  • A post-condition (logic statement) $\to$ describes the value / effect of the operation

Also see Program Specification for SE212 definition of these things.

Data Structures (DS)

• Array
• Linked List
• Hash Table
• Graph
• Binary Tree
• Binary Search Tree
• B-Tree
• Bitset
• Tuple

A data structure is used to implement ADTs. They are more concrete

• Connote the idea of the underlying implementation that may not be discernable from the API alone

Related

• Struct
• Dynamic Set