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 before/after index/value

    • delete by index/value

    • find by value

    • update by index

    • get

    • length

  • Stack ADT

    • push

    • pop

    • peek/top

    • isEmpty

  • Queue ADT

    • enqueue

    • dequeue

    • peek

    • isEmpty

  • Deque ADT

    • enqueue front

    • enqueue back

    • dequeue front

    • dequeue back

    • peek front

    • peek back

    • isEmpty

  • Priority Queue ADT

    • enqueue

    • dequeue

    • peek

    • isEmpty

  • Map ADT

    • set a key-value pair, a.k.a. put

    • delete by key

    • find by key

    • update a value by key (can be merged with set)

    • length

  • Set ADT

    • insert

    • delete

    • find

    • length

implementations

  • List ADT

    • partially filled array

      • get/set by index: \(O(1)\)

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

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

    • linked list

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

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

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

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

  • Stack ADT

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

    • linked list \(O(1)\)

  • Queue/Deque ADT

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

    • linked list \(O(1)\)

  • Priority Queue ADT

    • heap \(O(\log n)\)

    • sorted array

      • add \(O(n)\)

      • remove \(O(1)\)

    • unsorted array

      • add \(O(1)\)

      • remove \(O(n)\)

  • Map/Set ADT

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

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