4. Abstract Data Types

0.0(0)
studied byStudied by 3 people
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
Card Sorting

1/13

encourage image

There's no tags or description

Looks like no tags are added yet.

Study Analytics
Name
Mastery
Learn
Test
Matching
Spaced

No study sessions yet.

14 Terms

1
New cards

abstract data type

An abstract data type (or ADT) defines some kind of data and the operations that can be performed on it.

It is a pure interface, with no mention of an implementation—that’s what makes it abstract.

2
New cards

ADTs vs Data structures

ADTs are concerned with the what: what data is stored, and what we can do with this data.

Data structures are concerned with the how: how is that data stored, and how do we actually implement our desired methods to operate on this data?

3
New cards

5 famous ADTs

  • set

  • multiset

  • list

  • map

  • iterable

  • (and stack and queue we will learn lolz)

4
New cards

Set

  • Data: a collection of unique elements

  • Operations: get size, insert a value (without introducing duplicates), remove a specified value, check membership

5
New cards

Multiset

  • Data: a collection of elements (possibly with duplicates)

  • Operations: same as Set, but the insert operation allows duplicates

6
New cards

List

  • Data: an ordered sequence of elements

  • Operations: access element by index, insert a value at a given index, remove a value at a given index

7
New cards

Map

  • Data: a collection of key-value pairs, where each key is unique and associated with a single value

  • Operations: lookup a value for a given key, insert a new key-value pair, remove a key-value pair, update the value associated with a given key

8
New cards

Iterable

  • Data: a collection of values (may or may not be unique)

  • Operations: iterate through the elements of the collection one at a time.

9
New cards

correspondance between ADTS and data structures

there is NOT a one-to-one correspondence between ADTs and data structures

  • A single ADT can be implemented by many different data structures

    • python list, dict are data structures

  • each data structure can be used to implement multiple ADTs.

    • The Python list can be used to implement not just the List ADT, but each of the other above ADTs as well.

10
New cards

Stack ADT

  • Data: a collection of items

  • Operations: determine whether the stack is empty, add an item (push), remove the most recently-added item (pop)

<ul><li><p>Data: a collection of items</p></li><li><p>Operations: determine whether the stack is empty, add an item (<em>push</em>), remove the most recently-added item (<em>pop</em>)</p></li></ul>
11
New cards

Queue ADT

  • Data: a collection of items

  • Operations: determine whether the queue is empty, add an item (enqueue), remove the least recently-added item (dequeue)

<ul><li><p>Data: a collection of items</p></li><li><p>Operations: determine whether the queue is empty, add an item (<em>enqueue</em>), remove the least recently-added item (<em>dequeue</em>)</p></li></ul>
12
New cards

user-defined exception

we define our own type of error by making a subclass of a built-in class called Exception.

overriding the inherited __str__ method in our class

raise EmptyStackError

<p><span>we define our own type of error by making a subclass of a built-in class called </span><code>Exception. </code></p><p><span>overriding the inherited </span><code>__str__</code><span> method in our class</span></p><p>raise EmptyStackError</p>
13
New cards

normal flow of control in a program

pushing a stack frame whenever a function is called, and popping the current (top) stack frame when we reach a return or reach the end of the function/method.

14
New cards

Exceptions interrupt the normal flow of control

immediately, the function ends and its stack frame is popped, sending the exception back to the caller, which in turn ends immediately, sending the exception back to its caller, and so on until the stack is empty