3 of 57

Interfaces vs. Implementation

In class:

Developed ALists and SLLists.
Created an interface List61B.

Modified AList and SLList to implement List61B.
List61B provided default methods.

In projects:

Developed ArrayDeque and LinkedListDeque.
Created an interface Deque.

Modified AD and LLD to implement Deque.

List61B

AList

SLList

Deque

Array

Deque

LinkedList

Deque

datastructur.es

4 of 57

Interfaces vs. Implementation

With DisjointSets, we saw a much richer set of possible implementations.

DisjointSets

ListOfSetsDS

QuickFindDS

QuickUnionDS

WeightedQuickUnionDS

datastructur.es

5 of 57

Abstract Data Types

An Abstract Data Type (ADT) is defined only by its operations, not by its implementation.

Deque ADT:

addFirst(Item x);
addLast(Item x);
boolean isEmpty();
int size();
printDeque();
Item removeFirst();
Item removeLast();
Item get(int index);

Deque

Array

Deque

LinkedList

Deque

ArrayDeque and LinkedList Deque are implementations of the Deque ADT.

datastructur.es

6 of 57

Another example of an ADT: The Stack

The Stack ADT supports the following operations:

push(int x): Puts x on top of the stack.
int pop(): Removes and returns the top item from the stack.

insertBack()

getBack()

get(int i)

deleteBack()

push(int x)

pop()

datastructur.es

7 of 57

The Stack ADT: yellkey.com/?

The Stack ADT supports the following operations:

push(int x): Puts x on top of the stack.
int pop(): Removes and returns the top item from the stack.�

Which implementation do you think would result in faster overall performance?

Linked List
Array

insertBack()

getBack()

get(int i)

deleteBack()

push(int x)

pop()

datastructur.es

8 of 57

The Stack ADT: yellkey.com/?

The Stack ADT supports the following operations:

push(int x): Puts x on top of the stack.
int pop(): Removes and returns the top item from the stack�

Which implementation do you think would result in faster overall performance?

Linked List
Array

Both are about the same. No resizing for linked lists, so probably a lil faster.

insertBack()

getBack()

get(int i)

deleteBack()

push(int x)

pop()

datastructur.es

9 of 57

The GrabBag ADT: yellkey.com/?

The GrabBag ADT supports the following operations:

insert(int x): Inserts x into the grab bag.
int remove(): Removes a random item from the bag.
int sample(): Samples a random item from the bag (without removing!)
int size(): Number of items in the bag.

Which implementation do you think would result in faster overall performance?

Linked List
Array

insertBack()

getBack()

get(int i)

deleteBack()

remove()

insert(int x)

sample()

size(int i)

datastructur.es

10 of 57

The GrabBag ADT: yellkey.com/?

The GrabBag ADT supports the following operations:

insert(int x): Inserts x into the grab bag.
int remove(): Removes a random item from the bag.
int sample(): Samples a random item from the bag (without removing!)
int size(): Number of items in the bag.

Which implementation do you think would result in faster overall performance?

Linked List
Array

insertBack()

getBack()

get(int i)

deleteBack()

remove()

insert(int x)

sample()

size(int i)

datastructur.es

11 of 57

Abstract Data Types in Java

One thing I particularly like about Java is the syntax differentiation between abstract data types and implementations.

Note: Interfaces in Java aren’t purely abstract as they can contain some implementation details, e.g. default methods.

Example: List<Integer> L = new ArrayList<>();

List

ArrayList

Linked

List

datastructur.es

12 of 57

Collections

Among the most important interfaces in the java.util library are those that extend the Collection interface (btw interfaces can extend other interfaces).

Lists of things.
Sets of things.
Mappings between items, e.g. jhug’s grade is 88.4, or Creature c’s north neighbor is a Plip.

Maps also known as associative arrays, associative lists (in Lisp), symbol tables, dictionaries (in Python).

Collection

List

Set

Map

datastructur.es

13 of 57

Map Example

Maps are very handy tools for all sorts of tasks. Example: Counting words.

Map<String, Integer> m = new TreeMap<>();

String[] text = {"sumomo", "mo", "momo", "mo",

"momo", "no", "uchi"};

for (String s : text) {

int currentCount = m.getOrDefault(s, 0);

m.put(s, currentCount + 1);

}

m = {}

text = ["sumomo", "mo", "momo", "mo", \

"momo", "no", "uchi"]

for s in text:

current_count = m.get(s, 0)

m[s] = current_count + 1

Python equivalent

sumomo	1
mo	2
momo	2
no	1
uchi	1

datastructur.es

14 of 57

Java Libraries

The built-in java.util package provides a number of useful:

Interfaces: ADTs (lists, sets, maps, priority queues, etc.) and other stuff.
Implementations: Concrete classes you can use.

Today, we’ll learn the basic ideas behind the TreeSet and TreeMap.

Collection

List

Set

Map

ArrayList

Linked

List

TreeSet

HashSet

TreeMap

HashMap

datastructur.es

15 of 57

Binary Search Trees

datastructur.es

16 of 57

Analysis of an OrderedLinkedListSet<Character>

In an earlier lecture, we implemented a set based on unordered arrays. For the order linked list set implementation below, name an operation that takes worst case linear time, i.e. Θ(N).

size

contains

add

iterator

sent

size

datastructur.es

17 of 57

Analysis of an OrderedLinkedListSet<Character>

In an earlier lecture, we implemented a set based on unordered arrays. For the order linked list set implementation below, name an operation that takes worst case linear time, i.e. Θ(N).

size

contains

add

iterator

sent

size

datastructur.es

18 of 57

Optimization: Extra Links