Transcript Data Structures - Calvin College

Data Structures
Chapter 12
Chapter Contents
Chapter Objectives
12.1 Introductory Example: Counting Internet Addresses
12.2 The ArrayList and LinkedList Classes
12.3 Example: A Stack Application and Class
12.4 Example: A Queue Class
12.5 An Introduction to Trees
Part of the Picture: Data Structures
12.6 Graphical/Internet Java: A PolygonSketcher Class
Chapter Objectives
 Study
the Java collection classes,
ArrayList and LinkedList
 Show how to build collection classes
 Study the stack and queue structures
 Learn about linked structures
 linked lists and binary trees
 Implement
and use linked structures
 Discover how collection classes are used
in graphical programming
Review Arrays

An array stores a sequence of values
type [] anArray = new type [ capacity ];

Drawback:
– capacity of array fixed
– must know max number of values at compile
time
– either the program runs out of space or
wastes space

Solution: collection classes
– capacity can grow and shrink as program runs
12.1 Introductory Example:
Counting Internet Addresses

Internet TCP/IP addresses provide for two
names for each computer
– A host name, meaningful to humans
– an IP address, meaningful to computers

Problem:
– network administrator needs to review file of IP
addresses using a network gateway

Solution:
– read file of addresses
– keep track of addresses and how many times each
address shows up in the file
Class AddressCounter
Note source code, Figure 12.1
 Attributes

– maximum message length
– address
– count

Methods
–
–
–
–
–
constructor
comparison method, equals()
count incrementer
accessors for address, count
to-string converter for output
Class GatewayUsageCounter
Note source code, Figure 12.2
 Purpose

– counts IP addresses using an array list
Receives name of text file from args[0]
 Action:

– reads IP address from file
– prints listing of IP addresses and access
count for each

Note use of ArrayList class
– can grow or shrink as needed
12.2 The ArrayList and
LinkedList Classes
Collection classes provide capability to
grow and shrink as needed
 Categories of collection classes

– Lists: store collection of items, some of
which may be the same
– Sets: store collection of items with no
duplicates
– Maps: store collections of pairs, each
associates a key with an object

Note List methods, table 12.1
ArrayList Class

Implements the List using an array
– by using an Object array, can store any
reference type
– cannot directly store primitive types
– can indirectly store such values by using
instances of their wrapper types

Consider the declaration:
ArrayList addressSequence = newArrayList();
AddressSeqeunce
size
array
0

Adding to addressSequence

The command
addressSequence.add(anAddressCounter);
– appends anAddressCounter object to the
sequence

The
Update size
system
attributewill
of thethen
ArrayList
AddressSeqeunce
size
…
array
10
128.159.4.201
Make first element
Allocate
thetoarray
point
the
AddressCounter
[0] [1] [2] . . . [m-1]
Updating addressSequence

Consider the command
((AddressCounter)
addressSequence.get(index)).incrementCount();
// assume index == 1
Cast it as an
AddressCounter
object
AddressSeqeunce
size
Increment
Gets this
object the count
attribute
array
[0] [1] [2] . . . [m-1]
2
128.159.4.2011, 1
123.111.222.333, 12
Enlarging the
AddressSequence Array

When allocated array is full, adding
another element forces replacing array
with larger one
– new array of n > m allocated
– values from old array copied into new array
– old array replaced by new one
AddressSeqeunce
size
array
[0] [1] [2] . . . [n-1]
2
128.159.4.2011, 1
123.111.345.444, 1
123.111.222.333, 1
ArrayList Drawback

Problems arise from using an array
– values can be added only at back of
ArrayList
– to insert a value and "shift" others after it
requires extensive copying of values
– similarly, deleting a value requires shifting

We need a slightly different structure to
allow simple insertions and deletions
– the LinkedList class will accomplish this
The LinkedList Class

Given
LinkedList alist = new LinkedList();
. . .
aList.add(new(integer(88));
aList.add(new(integer(77));
aList.add(new(integer(66));
aList
head
size
tail
3
Resulting object
shown at left
88
77
66
Linked List Containers
Attributes:
aList
head size
tail
3
•link
to first item in the list
Nodes:
•size
of the3list
•Contain
handles
•link to
lasttoitem
the list
•link
nextinnode
•link to previous node
88
77
66
•link to stored object
•Links to next and
previous make it a
doubly linked list
Variations on Linked Lists
Lists can be linked doubly as shown
 Lists can also be linked in one direction
only

– attribute would not need link to tail
– node needs forward link and pointer to data
only
– last item in list has link set to null

Lists can be circularly linked
– last node has link to first node
Using a LinkedList

Solve the IP address counter to use
LinkedList

Note source code, Figure 12.3
– receives text file via args[0]
– reads IP addresses from file
– prints listing of distinct IP addresses and
number of times found in file
Using a LinkedList

Given the command
LinkedList addressSequence = new LinkedList();

Uses the LinkedList constructor to
build an empty list
addressSequence
head

size
tail
0

Adding to the Linked List

Results of command for first add
addressSequence.add(anAddressCounter);
addressSequence
head
size
tail
0
•Successive adds
• create more nodes
and data values
•adjust links


123.111.345.444, 1
Accessing Values in a Linked List

Must use the .get method
((AddressCounter)
addresssSequence.get(index)).incrementCount();
A LinkedList has no array with an index
to access an element
 get method must …

– begin at head node
– iterate through index nodes to find match
– return reference of object in that node

Command then does cast and
incrementCount()
Accessing Values in a Linked List

To print successive values for the output
for (int i = 0; i < addressSequence.size(); i++)
System.out.println(addressSequence.get(i));
get(i) starts at
size method
first node, iterates
i times to reach
desired node
determines limit of loop
counter
•Note that each get(i) must pass over the
same first i-1 nodes previously accessed
•This is inefficient
Accessing Values in a Linked List

An alternative, more efficient access algorithm
ListIterator it =
addressSequence.listIterator();
while (it.hasNext())
System.out.println( it.next());
A ListIterator is an object that iterates
across the values in a list
 The next() method does the following:

1. save handle to current node's object
2. advances iterator to next node using successor
attribute
3. returns handle saved in step 1, so object pointed to can
be output
Inserting Nodes Anywhere in a
Linked List

Recall problem with ArrayList
– can add only at end of the list
– linked list has capability to insert nodes anywhere

We can say
addressSequence.add(n, new anAddressCounter);
Which will …
– build a new node
– update head and tail links if required
– update node handle links to place new node to be nth
item in the list
– allocates memory for the data item
Choosing the Proper List
Algorithm Efficiency

"Time-efficiency" is not a real-time issue
– rather an issue of how many steps an
algorithm requires

Linear time
– time proportional to n
– referred to as O(n), "order n"

Constant time
– expressed as O(1)
Demonstration of Efficiency
Note sample program ListTimer, Figure
12.4, demonstrates performance
 Observations

– appending to either ArrayList or
LinkedList structures takes negligible
time
– far more time-consuming to access middle
value in a LinkedList than an ArrayList
– far more time consuming to insert values into
an ArrayList than a LinkedList
Conclusions on Efficiency

If problem involves many accesses to
interior of a sequence
– sequence should be stored in an ArrayList

If problems involves many insertions,
deletions not at end
– sequence should be stored in LinkedList

If neither of these is the case
– it doesn't matter which is used
12.3 Example: a Stack
Application and Class
Consider an algorithm which converts
from a base 10 number system to another
number system.
 To convert from 95ten to base eight:
Use repeated
0
division by
1 3 7eight
8 1 remainder 1
eight, taking
remainders
8 11 remainder 3
in reverse
8
95
remainder
7
order

Need for a Stack
The remainders are generated in the
opposite order that they must be output
 If we were able to …

– generate them
– hold on to them as generated
– access (display) them in the
reverse order
1
THEN we have used a stack
137
3
7
Stack Container
A stack is maintained Last-In-First-Out
(not unlike a stack of plates in a
cafeteria)
 Standard operations

– isEmpty(): returns true or false
– top(): returns copy of value at top of stack
(without removing it)
– push(v): adds a value v at the top of the
stack
– pop(): removes and returns value at top
Number Base Conversion
Algorithm
1.
2.
Create an empty stack to hold numbers
Repeat following while number != 0
Calculate remainder = number % base
b) Push remainder onto stack of remainders
c) Replace number = number / base
a)
3.
4.
Declare result as an empty String
While stack not empty do the following:
Remove remainder from top of stack
b) Convert remainder to base equivalent
c) Concatenate base equivalent to result
a)
5.
Return result
Implementing a Stack Class

Note use of Stack class in source code,
Figure 12.6, implementation in Figure 12.7

Implemented with LinkedList attribute
variable to store values
– this is a "has-a" relationship, the Stack
has a LinkedList
– contrast the "is-a" relationship
Java's Stack Class
Java has a Stack class which extends
the Vector class
 Author notes implementation as a
subclass of Vector provides inheritance
of methods inappropriate for a Stack

– suggests this violates rule of thumb for use
of the extends
– Vector contains messages not appropriate
that should not be used in Stack
12.4 Example: Building a Queue
Class

In a queue,
– new values are always added at the front or
head of the list
– values are removed from the opposite end of
the list, the rear or tail

Examples of queues
– checkout at supermarket
– vehicles at toll booth
– ticket line at movies

Queue exhibits First-In-First-Out
behavior
Queues in a Computer System

When a process (program) requires a
certain resource
– printer
– disk access on a network
– characters in a keyboard buffer

Queue Manipulation Operations
– isEmpty(): returns true or false
– first(): returns copy of value at front
– add(v): adds a new value at rear of queue
– remove(): removes, returns value at front
Implementing a Queue Class

Implement as a LinkedList attribute
value
– insertions and deletions from either end are
efficient, occur in constant O(1) time
– good choice

Implement as an ArrayList attribute
– poor choice
– adding values at one end, removing at other
end require multiple shifts
Implementing a Queue Class

Build a Queue from scratch
– build a linked structure to store the queue
elements

Attributes required
– handle for the head node
– handle for tail node
– integer to store number of values in the
queue
– use SinglyLinkedNode class, source code,
Figure 12.8
Queue Structure
aQueue
myHead
mySize myTail
n
...
value0
value1
...
valuen-1
Queue Class Methods

Constructor
– set myHead, myTail to null
– set mySize to zero

isEmpty()
– return results of comparison mySize == 0

front()
– return myHead.getValue()
// unless empty
Queue Class Methods

add()
– create new node, update attribute variables
– if queue is empty, must also update myHead

remove()
– must check if class not empty
otherwise …
– save handle to first object
– adjust head to refer to node
– update mySize
Note source code for
whole class, Figure 12.9
12.5 An Introduction to Trees

We seek a way to organized a linked
structure so that …
– elements can be searched more quickly than
in a linearly linked structure
– also provide for easy insertion/deletion
– permit access in less than O(n) time

Recall binary search strategy
– look in middle of list
– keep looking in middle of subset above or
below current location in list
– until target value found
Visualize Binary Search
13
28
35
49
62
66
Drawn as a binary tree
49
28
13
66
35
62
80
80
Tree Terminology

A tree consists of:
–
–
–
–
finite collection of nodes
non empty tree has a root node
root node has no incoming links
every other node in the tree can be reached from
the root by unique sequence of links
49
28
Leaf nodes
66
Sibling nodes
Parent
and
13
35
62
80
child nodes
Applications of Trees

Genealogical tree
– pictures a person's descendants and
ancestors

Game trees
– shows configurations possible in a game such
as the Towers of Hanoi problem

Parse trees
– used by compiler to check syntax and
meaning of expressions such as 2 * ( 3 + 4 )
Examples of Binary Trees
Each node has at most two children
 Useful in modeling processes where a
test has only two possible outcomes

– true or false
– coin toss, heads or tails
Each unique path can be described by the
sequence of outcomes
 Can be applied to decision trees in expert
systems of artificial intelligence

Implementing Binary Trees

Binary tree represented by multiply
linked structure
– each node has two links and a handle to the
data
– one link to left child, other to the right
myValue
Value
myLeftChild
myRightChild
Implementing Binary Trees

Declaration of BinaryTreeNode class
public class BinaryTreeNode
{
Pointers to
// … methods go here
succeeding nodes
// Attributes
private BinaryTreeNode
myLeftChild, myRightChild;
private Object myValue;
}
Handle to stored value
Implementing Binary Trees
BinaryTreeNode is only one of the
attributes of a BinaryTree class
 Also need an attribute that keeps track of
the number of nodes in the tree

public class BinaryTree extends Object
{
// … methods
private BinaryTreeNode myRoot;
private int
mySize;
}
Visualizing a BinaryTree
aBTree
myRoot
mySize
3
46


63
17


Binary Search Trees
Search Algorithm
1. Initialize a handle currentNode to the
node containing the root
2. Repeatedly do the following:
If target_item < currentNode.myValue
set currentNode = currentNode.leftChild
If target_item > currentNode.myValue
set currentNode = currentNode.rightChild
Else
terminate repetition because target_item
has been found
Tree Traversals
A traversal is moving through the binary tree,
visiting each node exactly once

for now order not important
–

Traverse Algorithm
Visit the root and process its contents
2. Traverse the left subtree
1.
1. visit its root, process
2. traverse left sub-sub tree
3. traverse right sub-sub tree
3.
Traverse the right subtree
1.
…
Tree Traversal is Recursive
If the binary tree is empty then
do nothing
Else
L: Traverse the left subtree
N: Visit the root
R: Traverse the right subtree
The "anchor"
The inductive step
Traversal Order
Three possibilities for inductive step …
 Left subtree, Node, Right subtree
the inorder traversal

Node, Left subtree, Right subtree
the preorder traversal

Left subtree, Right subtree, Node
the postorder traversal
Constructing Binary Search
Trees
Repeatedly insert elements into a BST that is
initially empty
 Descend tree, looking for place to insert the
item

– Set parentNode = currentNode
– change currentNode to its left or right child
– if value being inserted is not in the tree,
currentNode will eventually become null and …
– parentNode will indicate the parent of a new node
to contain the value
12.6 Graphical/Internet Java:
A PolygonSketcher
This will illustrate usage of container
class to store graphical data
 The program will use the mouse to draw a
closed geometric figure called a polygon
 The program should distinguish between

– mouse clicks: connect current (x,y) to
previous (x,y) with a line segment
– dragging the mouse: "rubber banding" the
line segment
Behavior
PolygonSketcher
Undo
Clear
Complete
Quit
Design

To support the "repeated undo" feature
– need a LIFO structure, suggests a stack

To the support the "complete" command
button
– need capability to access first point where
user clicked mouse
– this suggests not a stack

We create our own PointList class
– gives push() and pop() capabilities
– also allows access to value at other end
Coding

To represent mouse-click points
– int array for x-coordinates
– int array for matching y-coordinates
– total number of points
Note PointList class declaration,
Figure 12.11
 Methods

– pushPoint() // two versions
– popPoint() // returns a point
– accessor methods
The SketchPanel Class

Class needs listener methods
– MouseListener interface listens for button
events, handles the events
– MouseMotionListener interface listens for mouse
movements, handles them

Our sketcher will override methods …
– mousePressed()
– mouseDragged()

Other methods we need:
Note source code
in Figure 12.12
– eraseLastLine() for the Undo button
– eraseAllLines() for the Clear button
– completePolygon() for the Complete button
PolygonSketcher Class

Builds the GUI
– including a central SketchPanel
Listens for mouse button clicks
 When button click events happen

– actionPerformed() method sends
appropriate messages to the SketchPanel

Note source code, Figure 12.13
Part of the Picture:
Data Structures

Java provides standard classes
– ArrayList
– LinkedList
Standard classes used to solve variety of
problems
 Wise use of these data structures simply
solutions to many problems
 Attention should be given to efficiency
of structure for particular task at hand

Other Data Structures

Set interface implemented by HashSet
and TreeSet classes

Map interface implemented by TreeMap
and HashTable classes

Collections class
– variety of utility methods for manipulating
collections