7 ADTs and Implementations

1. List ADT

Constraint: ordered sequence, position-based, duplicates allowed.

Behaviors: add, remove, search, access by index, size.

Implementations

  • Array

    • access: Θ(1)

    • search: Θ(n)

    • insert/remove at middle/front: Θ(n)

    • insert/remove at end: Θ(1) amortized

  • Linked list

    • access by index: Θ(n)

    • search: Θ(n)

    • insert/remove at front or known node: Θ(1)

    • insert/remove by position search: Θ(n)

2. Stack ADT

Constraint: LIFO.

Behaviors: push, pop, top, empty.

Implementations

  • Array: push/pop/top = Θ(1) amortized / Θ(1) / Θ(1)

  • Linked list: push/pop/top = Θ(1) / Θ(1) / Θ(1)

  • Wrapper class: same as wrapped structure

3. Queue ADT

Constraint: FIFO.

Behaviors: enqueue, dequeue, peek, empty.

Implementations

  • Linked list (front + rear):

    • enqueue: Θ(1)

    • dequeue: Θ(1)

    • peek: Θ(1)

  • Circular array:

    • enqueue: Θ(1)

    • dequeue: Θ(1)

    • peek: Θ(1)

4. Deque ADT

Constraint: insert/remove at both ends.

Behaviors: push front, push rear, pop front, pop rear, peek front/rear, size.

Implementations

  • Doubly linked list: all end operations Θ(1)

  • Circular array: all end operations Θ(1)

5. Map ADT

Constraint: unique keys, each key maps to a value.

Behaviors: put, get, remove, contains.

Implementations

  • Hash table:

    • put/get/remove/contains: Θ(1) average, Θ(n) worst

  • BST:

    • put/get/remove/contains: Θ(log n) average, Θ(n) worst

6. Set ADT

Constraint: unique elements only, no duplicates.

Behaviors: add, remove, contains.

Implementations

  • Hash table:

    • add/remove/contains: Θ(1) average, Θ(n) worst

  • BST:

    • add/remove/contains: Θ(log n) average, Θ(n) worst

7. Priority Queue ADT

Constraint: removal is by priority, not FIFO.

Behaviors: insert, remove highest/lowest priority, peek, empty.

Implementations

  • Heap:

    • insert: Θ(log n)

    • remove priority item: Θ(log n)

    • peek: Θ(1)

  • Sorted array:

    • insert: Θ(n)

    • remove priority item: Θ(1) if priority end is chosen well

    • peek: Θ(1)

  • Unsorted array:

    • insert: Θ(1)

    • remove priority item: Θ(n)

    • peek: Θ(n)

Quick view

ADT

Constraint

Common implementations

List

ordered, positional

array, linked list

Stack

LIFO

array, linked list

Queue

FIFO

linked list, circular array

Deque

both ends active

doubly linked list, circular array

Map

unique key → value

hash table, BST

Set

unique elements

hash table, BST

Priority Queue

priority order

heap, sorted array, unsorted array