1 of 10

Abstract Data Type

Discussion 6

2 of 10

Abstract Data Type

Abstract Data Type (ADT) is a mathematical model of a certain class of data structures that have similar behavior; an ADT is defined only by its operations, not by its implementations.

3 of 10

Understand Abstract

Car

Ferrari 458

Abstract

Implementation

Four wheels

Can carry passengers

Need a driver to drive it

Has an internal combustion engine

...

4 of 10

List

  • insert(item, position)
    • put item in the list at position.
  • get(position)
    • return item in the list at position.
  • size()
    • return the number of items in the list.

5 of 10

Set

  • add(item)
    • put item in the set. NO DUPLICATES.
  • contains(item)
    • return whether or not item is in the set.
  • items()
    • return a list of all items in some arbitrary order.

6 of 10

Stack

  • push(item)
    • put item onto the stack.
  • pop()
    • remove and return the MOST RECENTLY put item.
  • isEmpty()
    • return whether the stack is empty.

7 of 10

Queue

  • enqueue(item)
    • put item onto the queue.
  • dequeue()
    • remove and return the LEAST RECENTLY put item.
  • isEmpty()
    • return whether the queue is empty.

8 of 10

Map

  • put(key, value)
    • put key in the map and associate it with the value, if key already exists, replace its existing value with the given value.
  • get(key)
    • return value associated with the key.
  • keys()
    • return a list of all keys in some arbitrary order.

9 of 10

ADTs are Tools

Scissors, Knife, Axe, Saw

Task: Cut a piece of paper in half...

Choose the right tool!

10 of 10

Worksheet

Keep the same philosophy

​

let’s start the worksheet