Transcript Abstract Data Types (ADTs)

Abstract Data Types
many slides taken from Mike Scott, UT Austin
CS 307 Fundamentals of
Computer Science
1
Data Structures
Data structure is a representation of data
and the operations allowed on that data.
CS 307 Fundamentals of
Computer Science
2
Abstract Data Types
In Object Oriented Programming data and
the operations that manipulate that data are
grouped together in classes
Abstract Data Types (ADTs) or data
structures or collections store data and allow
various operations on the data to access and
change it
CS 307 Fundamentals of
Computer Science
3
Why Abstract?
Specify the operations of the data structure
and leave implementation details to later
– in Java use an interface to specify operations
many, many different ADTs
– picking the right one for the job is an important
step in design
– "Get your data structures correct first, and the
rest of the program will write itself."
-Davids Johnson
High level languages often provide built in
ADTs,
– the C++ STL, the Java standard library
CS 307 Fundamentals of
Computer Science
4
The Core Operations
Every Collection ADT should provide a way to:
– add an item
– remove an item
– find, retrieve, or access an item
Many, many more possibilities
–
–
–
–
is the collection empty
make the collection empty
give me a sub set of the collection
and on and on and on…
Many different ways to implement these items each
with associated costs and benefits
CS 307 Fundamentals of
Computer Science
5
Implementing ADTs
when implementing an ADT the operations
and behaviors are already specified
– think Java interface
Implementer’s first choice is what to use as
the internal storage container for the
concrete data type
– the internal storage container is used to hold the
items in the collection
– often an implementation of an ADT
– initially slim pickings for choice of storage
containers: arrays anyone?
CS 307 Fundamentals of
Computer Science
6
The Grand Tour
Why study ADTs?
Why reimplement some of them?
How many of you will actually go out and
create your own linked list ADT from scratch?
Remember, the primary goal is to learn how
to learn how to use and create ADTs
– also learn the behavior of some of the more
conventional ADTs
CS 307 Fundamentals of
Computer Science
7
Bags and Sets
Simplest ADT is a Bag
– items can be added, removed, accessed
– no implied order to the items
– duplicates allowed
Set
– same as a bag, except duplicate elements not
allowed
– union, intersection, difference, subset
CS 307 Fundamentals of
Computer Science
8
Lists
Items have a position in this Collection
– Random access or not?
Array Lists
– internal storage container is native array
Linked Lists
public class Node
{ private Object data;
private Node next;
first
}
CS 307 Fundamentals of
Computer Science
last
9
Stacks
Collection with access only to the last
element inserted
Data4
Last in first out
Data3
insert/push
Data2
remove/pop
Data1
top
make empty
CS 307 Fundamentals of
Computer Science
Top
10
Queues
Collection with access only to the item that
has been present the longest
Last in last out or first in first out
enqueue, dequeue, front
priority queues and deque
Front
Data1
CS 307 Fundamentals of
Computer Science
Back
Data2
Data3
Data4
11
Stacks and Queues in the
Java Collection API
No queue in the Java collections ADT
Stack extends Vector (which is almost
exactly like ArrayList)
– Hmmm?
One reason the Java Collections Library is
often said to be broken
no Queue in Collection API
CS 307 Fundamentals of
Computer Science
12
Trees
Similar to a linked list
public class TreeNode
{ private Object data;
private TreeNode left;
private TreeNode right;
}
CS 307 Fundamentals of
Computer Science
Root
13
Other Types of Trees
Binary Search Trees
– sorted values
Heaps
– sorted via a different algorithm
AVL and Red-Black Trees
– binary search trees that stay balanced
Splay Trees
B Trees
CS 307 Fundamentals of
Computer Science
14
HashTables
Take a key, apply function
f(key) = hash value
store data or object based on hash value
Sorting O(N), access O(1) if a perfect hash
function and enough memory for table
how deal with collisions?
CS 307 Fundamentals of
Computer Science
15
Other ADTs
Maps
– a.k.a. Dictionary
– Collection of items with a key and associated
values
– similar to hash tables, and hash tables often
used to implement Maps
Graphs
– Nodes with unlimited connections between other
nodes
Sparse vectors and sparse matrices
CS 307 Fundamentals of
Computer Science
16
The Java Collection
Interface
boolean isEmpty()
int size()
boolean add(Object x)
boolean contains(Object x)
boolean remove(Object x)
void clear()
Object[] toArray()
Iterator iterator()
CS 307 Fundamentals of
Computer Science
17
Generic Containers
ADTs or Collection classes should be
generic
– only write them once, hold lots or all types of
data
– Java achieves genericity through inheritance and
polymorphism
ADTs have an internal storage container
– What is storing the stuff,
– implementation vs. abstraction
– in Java, usually holds Objects. Why?
CS 307 Fundamentals of
Computer Science
18
CS 307 Fundamentals of
Computer Science
19
Example
ArrayList
Class ArrayList
java.util
java.lang.Object
|
+--java.util.AbstractCollection
|
+--java.util.AbstractList
|
+--java.util.ArrayList
All Implemented Interfaces:
Cloneable, Collection, List, Serializable
void add(int index, Object element)
Inserts the specified element at the specified position in this list.
boolean add(Object o)
Appends the specified element to the end of this list.
void clear()
Removes all of the elements from this list.
boolean contains(Object elem)
Returns true if this list
contains the specified element.
int indexOf(Object elem)
Searches for the first occurence of the given argument, testing for
equality using the equals method.
boolean isEmpty()
Tests if this list has no elements.
Object set(int index, Object element)
Replaces the element at the specified position in this list with the
specified element.
size()
intFundamentals
CS 307
of
Returns
the
number of elements in this list.
Computer Science
20