| Contents [0/5] |
| Abstract Data Type (ADT) [1/5] |
| Data structure [2/5] |
| Data structures in Java [3/5] |
| Data structures from DS 1 [4/5] |
| Order of growth [5/5] |
(Click here for one slide per page)
| Abstract Data Type (ADT) [1/5] |
An Abstract Data Type (ADT) specifies
For example, a stack (think of a stack of plates) includes the operations to :
s
| Data structure [2/5] |
A data structure provides code to implement an ADT.
The most important choice is how to store data.
For stack, we will look at two choices:
The way we choose to store the data affects the performance of the operations!
| Data structures in Java [3/5] |
Abstract data types are implemented as data structures.
Data structures are realized in Java using classes.
We hold the data associated with a data structure using fields (aka member variables or instance variables).
Fields are different from local variables, which are stored in methods.
We often use generics to re-use the implementation of a data structure and its operations across multiple data types.
| Data structures from DS 1 [4/5] |
| Order of growth [5/5] |
| Name | Function | Intuition |
|---|---|---|
| Constant | O(1) | Data independent |
| Logarithmic | O(lg(n)) | Iteratively cut in half |
| Linear | O(n) | Iterate once for each item |
| Linearithmic | O(n * lg(n)) | Nested iteration: once linear, once logarithmic |
| Quadratic | O(n^2) | Nested iteration: twice linear |
| Cubic | O(n^3) | Nested iteration: three times linear |
| Exponential | O(2^n) | Combinations |
| Factorial | O(n!) | Permutations |
Image from 8 time complexities that every programmer should know by Adrian Mejia