Transcript CS201 Slides12

Chapter 12: Data Structures
Presentation slides for
Java Software Solutions
Foundations of Program Design
Third Edition
by John Lewis and William Loftus
Java Software Solutions is published by Addison-Wesley
Presentation slides are copyright 2002 by John Lewis and William Loftus. All rights reserved.
Instructors using the textbook may use and modify these slides for pedagogical purposes.
Data Structures
 Now we explore some convenient techniques for
organizing and managing information
 Chapter 12 focuses on:
•
•
•
•
•
•
collections
Abstract Data Types (ADTs)
dynamic structures and linked lists
queues and stacks
non-linear data structures
predefined collection classes
2
Collections
 A collection is an object that serves as a repository for
other objects
 A collection usually provides services such as adding,
removing, and otherwise managing the elements it
contains
 Sometimes the elements in a collection are ordered,
sometimes they are not
 Sometimes collections are homogeneous, sometimes the
are heterogeneous
Abstract Data Types
 Collections can be implemented in many different ways
 An abstract data type (ADT) is an organized collection of
information and a set of operations used to manage that
information
 The set of operations defines the interface to the ADT
 As long as the ADT fulfills the promises of the interface, it
doesn't really matter how the ADT is implemented
 Objects are a perfect programming mechanism to create
ADTs because their internal details are encapsulated
4
Abstraction
 Our data structures should be abstractions
 That is, they should hide unneeded details
 We want to separate the interface of the structure from its
underlying implementation
 This helps manage complexity and makes it possible to change
the implementation without changing the interface
What do we mean by “makes it possible to change the
implementation without changing the interface“?
Why is changing the implementation without changing the
interface desirable?
5
What about a stack?
Is a stack an Abstract Data Type (ADT) with a collection of data
and operations that are allow on the data?
How many operations can we legally perform to manipulate a stack?
push & pop
Do we care about how these operations are implemented?
We only care about the what, not about the how!
A set of operations defines the interface to the ADT.
What are they for a stack?
Static vs. Dynamic Structures
 A static data structure has a fixed size
This meaning is different from the meaning of the
static modifier (variable shared among all instances of a class)
 Arrays are static; once you define the number of
elements it can hold, the number doesn’t change
 A dynamic data structure grows and shrinks at execution
time as required by its contents
 A dynamic data structure is implemented using links
7
Object References
 Recall that an object reference is a variable that stores
the address of an object
 A reference also can be called a pointer
 References often are depicted graphically:
student
John Smith
40725
3.58
8
References as Links
 Object references can be used to create links between
objects
 Suppose a Student class contains a reference to
another Student object
John Smith
40725
3.57
Jane Jones
58821
3.72
Note Jane’s null pointer.
9
References as Links
 References (pointers) can be used to create a variety of
linked structures, such as a linked list:
studentList
info
info
info
info
next
next
next
null
Figure 12.1
A linked list
10
Intermediate Nodes
 The objects being stored should not be concerned with
the details of the data structure in which they may be
stored
 For example, the Student class should not have to store
a link to the next Student object in the list
 Instead, we can use a separate node class with two
parts:
• 1) a reference to an independent object and
• 2) a link to the next node in the list
 The internal representation becomes a linked list of
nodes
11
Magazine Collection
 Let’s explore an example of a collection of Magazine
objects
 The collection is managed by the MagazineList class,
which has an private inner class called MagazineNode
 Because the inner class MagazineNode is private to
MagazineList, the MagazineList methods can directly
access MagazineNode data without violating encapsulation
 1st - see MagazineRack.java (page 641)
 2nd - see Magazine.java (page 644)
 3rd - see MagazineList.java (page 642)
Fig. 12.2 – inserting new node into list
 A method called insert could be defined to place a
node anywhere in the list, for example to keep it sorted
Inserting a node into the middle of a list
list
info
info
info
info
next
next
next
null
info
next
insert this new node
Fig. 12.3 - deleting a node from a list
 A method called delete could be defined to remove a
node from the list
Deleting a node from a list
list
info
info
info
info
info
next
next
next
next
null
What must we be careful of when deleting a node?
(Hint: what could we lose?)
Fig 12.4 - doubly linked list
 It may be convenient to implement as list as a doubly
linked list, with next and previous references
A doubly linked list
list
info
info
info
info
info
next
null
next
next
next
null
prev
prev
prev
prev
What is contents of the first nodes “prev” pointer ?
What does a doubly linked list allow ?
15
Fig. 12.5 - list with front & rear references
 It may be convenient to use a separate header node, with a
count and references to both the front and rear of the list
header node
count: 4
list
list with front and rear references
front
rear
info
info
info
info
next
next
next
null
What will this structure allow to occur quicker
than without “rear” pointer?
16
Other Dynamic List Implementations
 A linked list can be circularly linked -last node in the list points to the first node in the list
 If the linked list is doubly linked, the first node in the list also
points to the last node in the list
Discuss example implementing priority control of resource
allocation
– i.e., CPU time sharing via circular queue
Dynamic Implementations
The representation should facilitate
the intended operations and should
make them easy to implement.
Classic Data Structures
 Classic linear data structures include queues and stacks
 Classic nonlinear data structures include trees, binary
trees, graphs, and digraphs
Fig. 12.6 – a queue data structure
 A queue is similar to a list but adds items only to the rear
of the list and removes them only from the front
 It is called a FIFO data structure: First-In, First-Out
 Analogy: a line of people at a movie ticket window
enqueue
last item in,
last item out
dequeue
first item in,
first item out
20
Queues
 We can define the operations for a queue
• enqueue - add an item to the rear of the queue
• dequeue (or serve) - remove an item from the front of the queue
• empty - returns true if the queue is empty
 As with our linked list example, by storing generic
Object references, any object can be stored in the
queue
 Queues often are helpful in simulations or any situation in
which items get “backed up” while awaiting processing
(Jobs waiting their turn to be processed.)
21
Queues
 A queue can be represented by a singly-linked list.
Operationrs:
enqueue – add an item to rear
dequeue – remove an item from front
empty – returns true if queue is empty
Is it more efficient if the references point from front to the rear?
Two
representations
of same queue
queue
rear
info4
info3
info2
front
info1
null
next
next
next
info4
info3
info2
info1
next
rear
next
next
null
front
queue
Queues
 A queue can be represented by an array
 What may happen as queue grows via enqueue with no
immediately occurring dequeues?
0
1
2
3
4
5
Stacks
 A stack ADT is also linear, like a list or a queue
 Items are added and removed from only one end of a
stack
 It is therefore LIFO: Last-In, First-Out
 Analogies:
• a stack of plates in a cupboard
• a stack of bills to be paid
• a stack of hay bales in a barn
24
Fig. 12.7 – stack data structure
Stacks often are drawn vertically:
push
pop
 last item in, first item out
 first item in, last item out
25
Stacks
 Some stack operations:
• push - add an item to the top of the stack
• pop - remove an item from the top of the stack
• peek (or top) - retrieves the top item without removing it
• empty - returns true if the stack is empty
 A stack can be represented by a singly-linked list; it doesn’t
matter whether the references point from the top toward the
bottom or vice versa
 A stack can be represented by an array, but the new item
should be placed in the next available place in the array rather
than at the end of the array
(What can happen with an array implementation?)
26
Stacks
 The java.util package contains a Stack class
 Like ArrayList operations, the Stack operations
operate on Object references
 See (not during class) Decode.java (page 649) which
reverses the strings in a message.
 The words in the message are separated by a single
space. The Stack class is used to push the characters of
the word onto the stack and then pops the characters out
in reverse order.
Decode.java
Decode.java reverses the strings in a message
reverse a string
push
5
tramS
3
2
1
4
S
m
a
r
t
pop
1
2
Smart
3
4
5
Fig 12.8 - Trees
 A tree is a non-linear data structure that consists of a root
node and potentially many levels of additional nodes that form
a hierarchy
 Nodes that have no children are called leaf nodes
 Non-root and non-leaf nodes are called internal nodes
root node
imagine an upside
down tree
internal
nodes
A tree data structure
leaf nodes
Tree can represent inheritance relationship between classes.
Organization chart represented
via a tree data structure
root node
president
VP
mgr
VP
VP
mgr
VP
mgr
mgr
leaf nodes
Binary Trees
 A binary tree is defined recursively. Either it is empty (the
base case) or it consists of a root and two subtrees, each
of which is a binary tree
 Binary trees and trees typically are represented using
references as dynamic links, though it is possible to use
fixed representations like arrays
root node
leaf nodes
Fig. 12.9 - graph
 A graph is a non-linear structure (also called a network)
 Unlike a tree or binary tree, a graph does not have a root – no
primary entry point.
 Any node can be connected to any other node by an edge
 Can have any number of edges and nodes
 Analogy: the highway system connecting cities on a map
a graph data structure
Fig. 12.10 - digraphs
 Each edge of directed graph or digraph has a specific direction
denoted by arrows.
 Edges with direction sometimes are called arcs
 Analogy #1: airline flights between airports (see below)
 Analogy #2: Solution to a problem (on board – miles on arcs)
C
F
E
D
a directed graph
P
L
J
B
Y
A
X
N
R
W
S
airline routes represented via digraph
What else could be provided?
Graphs and Digraphs
Both graphs and digraphs can be represented using
dynamic links or using arrays.
As always, the representation should
facilitate the intended operations and
make them convenient to implement
Collection Classes
 The Java standard library contains several classes that represent
collections, often referred to as the Java Collections API.
(API  Application
Programmer Interface)
 Java Collections API supports the organization and management of data.
 Their underlying implementation is implied in the class names such as
ArrayList and LinkedList
 Several interfaces are used to define operations on the collections, such as
List, Set, SortedSet, Map, and SortedMap
Set – a collection of items with no duplicates.
Map – group of items that can be referenced by a
key value.
Summary
 Chapter 12 has focused on:
•
•
•
•
•
•
collections
Abstract Data Types (ADTs)
dynamic structures and linked lists
queues and stacks
non-linear data structures
predefined collection classes