******************************
Summary of Abstract Data types
******************************

Overview
========
This document summarized all ADTs covered in typical data structures and
algorithms courses.

Read the :doc:`introduction <adt-intro>` if you are new to ADTs.

Definitions
===========

.. glossary::

  List ADT
    A collection of elements, each identified by an index. The index of the
    first element is 0, the index of the second element is 1, and so on.

  Stack ADT
    A collection of elements. The last element added is the first element
    removed (LIFO).

  Queue ADT
    A collection of elements. The first element added is the first element
    removed (FIFO).

  Deque ADT
    A collection of elements. The element to be removed is either the first
    element added (FIFO) or the last element added (LIFO).

  Priority Queue ADT
    A collection of elements, each with an associated priority. The element
    removed is the one with the highest/lowest priority.

  Map ADT
    A collection of key-value pairs, where each key is unique.

  Set ADT
    A collection of unique elements.

Behaviors
=========
+ List ADT

  - insert at any position
  - delete
  - search
  - access by index
  - update by index
  - get size

+ Stack ADT

  - push
  - pop
  - peek/top
  - is empty

+ Queue ADT

  - enqueue
  - dequeue
  - peek
  - is empty

+ Deque ADT

  - enqueue front
  - enqueue back
  - dequeue front
  - dequeue back
  - peek front
  - peek back
  - is empty

+ Priority Queue ADT

  - enqueue
  - dequeue
  - peek
  - is empty

+ Map ADT

  - set a key-value pair, a.k.a. put
  - delete by key
  - get a value by key
  - update a value by key
  - is empty

+ Set ADT

  - insert
  - delete
  - contains/search
  - is empty

implementation Details
======================
+ List ADT

  * partially filled array

    - get/set by index: :math:`\Theta(1)`
    - insert/delete by index: :math:`\Theta(n)` to maintain order, :math:`\Theta(1)` if
      order is not important
    - find by value: :math:`\Theta(n)`

  * linked list

    - get/set by index: :math:`\Theta(n)`
    - insert/delete by pointer: :math:`\Theta(1)`
    - insert/delete by index: :math:`\Theta(n)`
    - find by value: :math:`\Theta(n)`

+ Stack ADT

  * partially filled array :math:`\Theta(1)` (add/remove at the end)
  * linked list :math:`\Theta(1)`

+ Queue/Deque ADT

  * circular partially filled array :math:`\Theta(1)`
  * linked list :math:`\Theta(1)`

+ Priority Queue ADT

  * heap :math:`\Theta(\log n)`
  * sorted array

    - add :math:`\Theta(n)`
    - remove :math:`\Theta(1)`

  * unsorted array

    - add :math:`\Theta(1)`
    - remove :math:`\Theta(n)`

+ Map/Set ADT

  * hash table :math:`\Theta(1)` (when healthy)
  * balanced binary search tree :math:`\Theta(\log n)`