Summary of Abstract Data types

Overview

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

Read the introduction if you are new to ADTs.

Definitions

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: \(\Theta(1)\)

      • insert/delete by index: \(\Theta(n)\) to maintain order, \(\Theta(1)\) if order is not important

      • find by value: \(\Theta(n)\)

    • linked list

      • get/set by index: \(\Theta(n)\)

      • insert/delete by pointer: \(\Theta(1)\)

      • insert/delete by index: \(\Theta(n)\)

      • find by value: \(\Theta(n)\)

  • Stack ADT

    • partially filled array \(\Theta(1)\) (add/remove at the end)

    • linked list \(\Theta(1)\)

  • Queue/Deque ADT

    • circular partially filled array \(\Theta(1)\)

    • linked list \(\Theta(1)\)

  • Priority Queue ADT

    • heap \(\Theta(\log n)\)

    • sorted array

      • add \(\Theta(n)\)

      • remove \(\Theta(1)\)

    • unsorted array

      • add \(\Theta(1)\)

      • remove \(\Theta(n)\)

  • Map/Set ADT

    • hash table \(\Theta(1)\) (when healthy)

    • balanced binary search tree \(\Theta(\log n)\)