# Data Structures

## Data types & data structures

A data type is an abstract interface that defines of a set of possible values along with their allowed behavior.

A data structure is a concrete implementation of a data type.

In an object-oriented language like Java, a data type could be represented as an **interface**. A data structure could be a **class** that implements the data type’s public interface.

## (Some) Fundamental data structures

- Record (struct)
- Array
- Linked list
- Binary search tree
- Hash table
- Heap
- Graph

## (Some) Abstract data types

Type | Common underlying data structures |
---|---|

List | Array , linked list |

Bag | Array, linked list |

Stack | Linked list |

Queue | Linked list |

Deque | Linked list |

Priority queue | Heap |

Set | Hash table, binary search tree |

Dictionary (Map) | Hash table, binary search tree |