> For the complete documentation index, see [llms.txt](https://alexgrischuk.gitbook.io/wiki/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://alexgrischuk.gitbook.io/wiki/coding/ds.md).

# Data Structures

## What is a Data Structure?

A **data structure** (DS) is a way of organizing data so that it can be used effectively.

## Abstract Data Types vs. Data Structures

An **abstract data type** (ADT) is an abstraction of the data structure which provides only the interface to which a data structure must adhere to.

The interface doest not give any specific details about how something should be implemented or in what programming language.

## Examples

| Abstraction (ADT) |   Implementation (DS)   |
| :---------------: | :---------------------: |
|        List       |      Dynamic Array      |
|                   |       Linked List       |
|       Queue       | Linked List based Queue |
|                   |    Array based Queue    |
|                   |    Stack based Queue    |
|        Map        |         Tree Map        |
|                   |  Hash Map / Hash Table  |
|      Vehicle      |        Golf Cart        |
|                   |         Bicycle         |

## Runtime Complexity

Describes the performance of the algorithm. Ref [Time complexity](https://en.wikipedia.org/wiki/time_complexity)

## Big O

* `N / O(n)` - 'linear' runtime
* `N^2` / `(n\*n)` / `O(n^2)` - N-square or quadratic runtime