Transcript Chapter 19 – Data Structures

• Final Exam
– Date: Aug 27th
– Time: 9:00am – 12:00pm
– Location: TEL 0014
Data Structures
• Outline
– Introduction
Self-Referential Classes
Dynamic Memory Allocation
Linked Lists
Stacks
Queues
Trees
Introduction
• Dynamic data structures
– Grow and shrink at execution time
– Several types
•
•
•
•
Linked lists
Stacks
Queues
Binary trees
– Not dynamic? Arrays
Self-Referential Classes
• Self-referential class
– Contains instance variable referring to object of same class
class Node {
private int data;
private Node nextNode;
// constructors and methods ...
}
• Member nextNode is a link
– nextNode “links” a Node object to another Node object
Self-Referential Classes (cont.)
15
10
Two self-referential class objects linked together.
Dynamic Memory Allocation
• Dynamic memory allocation
– Obtain more memory at execution time to store new objects
• Operator new
– Release memory used by objects when no longer needed
Linked Lists
• Linked list
–
–
–
–
Linear collection of self-referential classes (nodes)
Connected by reference links
Nodes can be inserted and deleted anywhere in linked list
Last node is set to null to mark end of list
Linked Lists (cont.)
firstNode
H
lastNode
D
...
A graphical representation of a linked list.
Q
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// List.java
// Class ListNode and class List definitions
// class to represent one node in a list
class ListNode {
// package access members; List can access these directly
Object data;
ListNode nextNode;
// constructor to create a ListNode that refers to object
ListNode( Object object )
{
this( object, null );
}
// constructor to create ListNode that refers to Object
// and to next ListNode in List
ListNode( Object object, ListNode node )
{
data = object;
nextNode = node;
}
// return Object in this node
Object getObject()
{
return data;
}
List.java
Self-referential class
Lines 6-10
ListNode contains data
and link to nextNode
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
// get next node
ListNode getNext()
{
return nextNode;
}
}
// end class ListNode
// class List definition
public class List {
private ListNode firstNode;
private ListNode lastNode;
private String name; // String like "list" used in printing
// construct an empty List with a name
public List( String string )
{
name = string;
firstNode = lastNode = null;
}
List.java (Part 2)
Reference
Lineto42first
node in linked list
Line 43
Reference to last
node
Linein50linked list
Lines 64-65
First and last nodes in
empty list are null
// construct empty List with "list" as the name
public List()
{
this( "list" );
}
// Insert Object at front of List. If List is empty,
// firstNode and lastNode will refer to same object.
// Otherwise, firstNode refers to new node.
public synchronized void insertAtFront( Object insertItem )
{
if ( isEmpty() )
firstNode = lastNode = new ListNode( insertItem );
If list is empty, the first and
last node should refer to the
newly inserted node
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
else
firstNode = new ListNode( insertItem, firstNode );
}
// Insert Object at end of List. If List is empty,
// firstNode and lastNode will refer to same Object.
// Otherwise, lastNode's nextNode refers to new node.
public synchronized void insertAtBack( Object insertItem )
{
if ( isEmpty() )
firstNode = lastNode = new ListNode( insertItem );
else
lastNode = lastNode.nextNode =
new ListNode( insertItem );
}
// remove first node from List
public synchronized Object removeFromFront()
throws EmptyListException
{
Object removeItem = null;
// throw exception if List is empty
if ( isEmpty() )
throw new EmptyListException( name );
// retrieve data being removed
removeItem = firstNode.data;
// reset the firstNode and lastNode references
if ( firstNode == lastNode )
firstNode = lastNode = null;
If list is not empty, the first
List.java
node should
refer to(Part
the 3)
newly inserted node
Line 68
76-77
If list Lines
is empty,
the first and
last node should refer to the
newly
Lines
inserted
80-81node
Lines
91-92the last
If list is
not empty,
node should refer to the
newly inserted node
If list is empty, removing a
node causes an exception
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
else
firstNode = firstNode.nextNode;
// return removed node data
return removeItem;
List.java (Part 4)
}
Line 102
// Remove last node from List
public synchronized Object removeFromBack()
throws EmptyListException
{
Object removeItem = null;
// throw exception if List is empty
if ( isEmpty() )
throw new EmptyListException( name );
Lines 131-137
If list is empty, removing a
node causes an exception
// retrieve data being removed
removeItem = lastNode.data;
// reset firstNode and lastNode references
if ( firstNode == lastNode )
firstNode = lastNode = null;
else {
// locate new last node
ListNode current = firstNode;
// loop while current node does not refer to lastNode
while ( current.nextNode != lastNode )
current = current.nextNode;
If list is not
empty, the second-to-last
node becomes the last node
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
// current is new lastNode
lastNode = current;
current.nextNode = null;
}
List.java (Part 5)
// return removed node data
return removeItem;
Lines 162-165
}
// return true if List is empty
public synchronized boolean isEmpty()
{
return firstNode == null;
}
// output List contents
public synchronized void print()
{
if ( isEmpty() ) {
System.out.println( "Empty " + name );
return;
}
System.out.print( "The " + name + " is: " );
Traverse list and print node values
ListNode current = firstNode;
// while not at end of list, output current node's data
while ( current != null ) {
System.out.print( current.data.toString() + " " );
current = current.nextNode;
}
167
168
169
170
167
168
169
170
System.out.println( "\n" );
}
}
// end class List
System.out.println( "\n" );
}
}
// end class List
List.java (Part 6)
1
2
3
4
5
6
7
8
9
10
11
12
13
// EmptyListException.java
// Class EmptyListException definition
public class EmptyListException extends RuntimeException {
// initialize an EmptyListException
public EmptyListException( String name )
{
super( "The " + name + " is empty" );
}
}
// end class EmptyListException
EmptyListExcepti
on.java
Lines 5-13
Exception thrown when
program attempts to remove
node from empty list
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// ListTest.java
// Class ListTest
ListTest.java
public class ListTest {
// test class List
public static void main( String args[] )
{
List list = new List(); // create the List container
// create objects to store in List
Boolean bool = Boolean.TRUE;
Character character = new Character( '$' );
Integer integer = new Integer( 34567 );
String string = "hello";
// use List insert methods
list.insertAtFront( bool );
list.print();
list.insertAtFront( character );
list.print();
list.insertAtBack( integer );
list.print();
list.insertAtBack( string );
list.print();
// use List remove methods
Object removedObject;
Line 13
Lines
Create linked
list 16-19
Lines 22-29
Create values
(Objects) to store
in linked-list nodes
Insert values in linked list
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
// remove objects from list; print after each removal
try {
removedObject = list.removeFromFront();
System.out.println(
removedObject.toString() + " removed" );
list.print();
removedObject = list.removeFromFront();
System.out.println(
removedObject.toString() + " removed" );
list.print();
removedObject = list.removeFromBack();
System.out.println(
removedObject.toString() + " removed" );
list.print();
removedObject = list.removeFromBack();
System.out.println(
removedObject.toString() + " removed" );
list.print();
}
// process exception if List is empty when attempt is
// made to remove an item
catch ( EmptyListException emptyListException ) {
emptyListException.printStackTrace();
}
}
}
// end method main
// end class ListTest
ListTest.java
(Part 2)
Lines 36-54
Remove values
from linked list
The list is: true
The list is: $ true
The list is: $ true 34567
ListTest.java
(Part 3)
The list is: $ true 34567 hello
$ removed
The list is: true 34567 hello
true removed
The list is: 34567 hello
hello removed
The list is: 34567
34567 removed
Empty list
Program Output
Linked Lists (cont.)
(a)
firstNode
7
11
new ListNode
12
(b)
firstNode
7
11
new ListNode
12
The insertAtFront operation.
Linked Lists (cont.)
(a)
firstNode
12
(b)
lastNode new ListNode
7
firstNode
12
11
5
lastNode new ListNode
7
11
5
A graphical representation of the insertAtBack operation.
Linked Lists (cont.)
(a)
firstNode
12
(b)
lastNode
7
11
firstNode
12
5
lastNode
7
11
5
removeItem
A graphical representation of the removeFromFront operation.
Linked Lists (cont.)
(a)
firstNode
12
(b)
lastNode
7
firstNode
12
11
current
7
5
lastNode
11
5
removeItem
A graphical representation of the removeFromBack operation.
Synchronized Methods
• keyword
– synchronized in method declaration
E.g. public synchronized void insertAtFront( Object insertItem )
– Prevent thread interference and memory consistency errors
• When one thread is executing a synchronized method for an object,
all other threads that invoke synchronized methods for the same
object block (suspend execution) until the first thread is done with
the object.
• Establishes a happens-before relationship with any subsequent
invocation of a synchronized method for the same object. (changes
to the state of the object are visible to all threads)
Stacks
• Stack
– Constrained version of a linked list
• Add and remove nodes only to and from the top of the stack
– Push method adds node to top of stack
– Pop method removes node from top of stack
– A stack is referred to as a last-in, first-out (LIFO) data
structure.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// StackInheritance.java
// Derived from class List
public class StackInheritance extends List {
// construct stack
public StackInheritance()
{
super( "stack" );
}
// add object to stack
public synchronized void push( Object object )
{
insertAtFront( object );
}
StackInheritance inherits
StackInheritance
from List, because
a stack is a
.java
constrained version of a linked list
Line 5
Lines 14-17
Method push adds
Lines 20-23
node to top of stack
// remove object from stack
public synchronized Object pop() throws EmptyListException
{
return removeFromFront();
}
}
// end class StackInheritance
Method pop removes
node from top of stack
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// StackInheritanceTest.java
// Class StackInheritanceTest
StackInheritance
Test.java
public class StackInheritanceTest {
// test class StackInheritance
public static void main( String args[] )
{
StackInheritance stack = new StackInheritance();
Line 13
Create stack
Lines 16-19
Lines 22-29
// create objects to store in the stack
Boolean bool = Boolean.TRUE;
Character character = new Character( '$' );
Integer integer = new Integer( 34567 );
String string = "hello";
// use push method
stack.push( bool );
stack.print();
stack.push( character );
stack.print();
stack.push( integer );
stack.print();
stack.push( string );
stack.print();
// remove items from stack
try {
// use pop method
Object removedObject = null;
Create values (Objects)
to store in stack
Insert values in stack
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
while ( true ) {
removedObject = stack.pop();
System.out.println( removedObject.toString() +
" popped" );
stack.print();
}
}
// catch exception if stack empty when item popped
catch ( EmptyListException e) {
System.err.println(“\n” + e.toString());
}
}
}
// end method main
// end class StackInheritanceTest
Remove value from stack
StackInheritance
Test.java
(Part 2)
Line 38
The stack is: true
The stack is: $ true
The stack is: 34567 $ true
The stack is: hello 34567 $ true
hello popped
The stack is: 34567 $ true
34567 popped
The stack is: $ true
$ popped
The stack is: true
true popped
Empty stack
EmptyListException: The stack is empty
StackInheritance
Test.java
(Part 3)
Program Output
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// StackComposition.java
// Class StackComposition definition with composed List object
public class StackComposition {
private List stackList;
Demonstrate how to create
stack via composition
// construct stack
public StackComposition()
{
stackList = new List( "stack" );
}
// add object to stack
public synchronized void push( Object object )
{
stackList.insertAtFront( object );
}
Lines 5-6
Lines 15-18
Lines 21-24
Method push adds
node to top of stack
// remove object from stack
public synchronized Object pop() throws EmptyListException
{
return stackList.removeFromFront();
}
// determine if stack is empty
public synchronized boolean isEmpty()
{
return stackList.isEmpty();
}
StackComposition
.java
Method pop removes
node from top of stack
32
33
34
35
36
37
38
// output stack contents
public synchronized void print()
{
stackList.print();
}
}
// end class StackComposition
StackComposition
.java (Part 2)
Queues
• Queue
– Similar to a supermarket checkout line
– Nodes inserted only at tail (back)
• Method enqueue
– Nodes removed only from head (front)
• Method dequeue
– A queue is referred to as first-in, first-out (FIFO) data
structure.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// QueueInheritance.java
// Class QueueInheritance extends class List
QueueInheritance
.java
public class QueueInheritance extends List {
Lines 16-19
// construct queue
public QueueInheritance()
{
super( "queue" );
}
// add object to queue
public synchronized void enqueue( Object object )
{
insertAtBack( object );
}
Lines 22-25
Method enqueue adds
node to top of stack
// remove object from queue
public synchronized Object dequeue() throws EmptyListException
{
return removeFromFront();
}
}
// end class QueueInheritance
Method dequeue
removes node from
top of stack
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// QueueInheritanceTest.java
// Class QueueInheritanceTest
QueueInheritance
Test.java
public class QueueInheritanceTest {
// test class QueueInheritance
public static void main( String args[] )
{
QueueInheritance queue = new QueueInheritance();
Line 13
Create queue
Lines 16-19
Lines 22-29
// create objects to store in queue
Boolean bool = Boolean.TRUE;
Character character = new Character( '$' );
Integer integer = new Integer( 34567 );
String string = "hello";
// use enqueue
queue.enqueue(
queue.print();
queue.enqueue(
queue.print();
queue.enqueue(
queue.print();
queue.enqueue(
queue.print();
Create values (Objects)
to store in queue
method
bool );
character );
integer );
string );
// remove objects from queue
try {
// use dequeue method
Object removedObject = null;
Insert values in queue
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
while ( true ) {
removedObject = queue.dequeue();
System.out.println( removedObject.toString() +
" dequeued" );
queue.print();
}
}
// process exception if queue empty when item removed
catch ( EmptyListException emptyListException ) {
emptyListException.printStackTrace();
}
}
}
// end method main
// end class QueueInheritanceTest
The queue is: true
The queue is: true $
The queue is: true $ 34567
The queue is: true $ 34567 hello
true dequeued
The queue is: $ 34567 hello
Remove value from queue
QueueInheritance
Test.java (Part 2)
Line 38
$ dequeued
The queue is: 34567 hello
34567 dequeued
The queue is: hello
hello dequeued
Empty queue
EmptyListException: The queue is empty
at List.removeFromFront(List.java:92)
at QueueInheritance.dequeue(QueueInheritance.java:24)
at QueueInheritanceTest.main(QueueInheritanceTest.java:38)
QueueInheritance
Test.java (Part 3)
Trees
• Tree
– Non-linear, two-dimensional data structure
• (unlike linked lists, stacks and queues)
– Nodes contain two or more links
– Root node is the first node
– Each link refers to a child
•
•
•
•
Left child is the first node in left subtree
Right child is the first node in right subtree
Children of a specific node is siblings
Nodes with no children are leaf nodes
Trees (cont.)
• Binary search tree
– Special ordering of nodes
• Values in left subtrees are less than values in right subtrees
– Inorder traversal
• Traverse left subtree, obtain node value, traverse right
subtree
– Preorder traversal
• Obtain node value, traverse left subtree, traverse right
subtree
– Postorder traversal
• Traverse left subtree, traverse right subtree, obtain node
value
Trees (cont.)
B
A
D
C
A graphical representation of a binary tree.
Trees (cont.)
47
25
77
11
43
7 17
31 44
65
68
A binary search tree containing 12 values.
93
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// Tree.java
// Definition of class TreeNode and class Tree.
Tree.java
// class TreeNode definition
class TreeNode {
Lines 11-13
// package access members
TreeNode leftNode;
int data;
TreeNode rightNode;
Lines 27-35
Left and right children
// initialize data and make this a leaf node
public TreeNode( int nodeData )
{
data = nodeData;
leftNode = rightNode = null; // node has no children
}
// insert TreeNode into Tree that contains nodes;
// ignore duplicate values
public synchronized void insert( int insertValue )
{
// insert in left subtree
if ( insertValue < data ) {
// insert new TreeNode
if ( leftNode == null )
leftNode = new TreeNode( insertValue );
// continue traversing left subtree
else
leftNode.insert( insertValue );
If value of inserted
node is less than value
of tree node, insert
node in left subtree
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
// insert in right subtree
else if ( insertValue > data ) {
// insert new TreeNode
if ( rightNode == null )
rightNode = new TreeNode( insertValue );
// continue traversing right subtree
else
rightNode.insert( insertValue );
}
}
}
// end method insert
// end class TreeNode
// class Tree definition
public class Tree {
private TreeNode root;
// construct an empty Tree of integers
public Tree()
{
root = null;
}
// Insert a new node in the binary search tree.
// If the root node is null, create the root node here.
// Otherwise, call the insert method of class TreeNode.
public synchronized void insertNode( int insertValue )
{
if ( root == null )
root = new TreeNode( insertValue );
(Part 2)
If value Tree.java
of inserted node
is greater than value of
Lines
tree node,
insert39-48
node in
right subtree
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
else
root.insert( insertValue );
}
Tree.java (Part 3)
// begin preorder traversal
public synchronized void preorderTraversal()
{
preorderHelper( root );
}
Lines 83-96
// recursive method to perform preorder traversal
private void preorderHelper( TreeNode node )
{
if ( node == null )
return;
// output node data
System.out.print( node.data + " " );
// traverse left subtree
preorderHelper( node.leftNode );
// traverse right subtree
preorderHelper( node.rightNode );
}
// begin inorder traversal
public synchronized void inorderTraversal()
{
inorderHelper( root );
}
Preorder traversal – obtain
data, traverse left subtree,
then traverse right subtree
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
// recursive method to perform inorder traversal
private void inorderHelper( TreeNode node )
{
if ( node == null )
return;
// traverse left subtree
inorderHelper( node.leftNode );
// output node data
System.out.print( node.data + " " );
// traverse right subtree
inorderHelper( node.rightNode );
Tree.java (Part 4)
Lines 105-118
Inorder traversal
– traverse
Lines 127-140
left subtree, obtain data, then
traverse right subtree
}
// begin postorder traversal
public synchronized void postorderTraversal()
{
postorderHelper( root );
}
// recursive method to perform postorder traversal
private void postorderHelper( TreeNode node )
{
if ( node == null )
return;
// traverse left subtree
postorderHelper( node.leftNode );
// traverse right subtree
postorderHelper( node.rightNode );
Postorder traversal – traverse
left subtree, traverse right
subtree, then obtain data
138
139
140
141
142
// output node data
System.out.print( node.data + " " );
}
}
// end class Tree
Tree.java (Part 5)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// TreeTest.java
// This program tests class Tree.
TreeTest.java
// Class TreeTest definition
public class TreeTest {
Lines 17-22
// test class Tree
public static void main( String args[] )
{
Tree tree = new Tree();
int value;
Line 26
Line 30
System.out.println( "Inserting the following values: " );
// insert 10 random integers from 0-99 in tree
for ( int i = 1; i <= 10; i++ ) {
value = ( int ) ( Math.random() * 100 );
System.out.print( value + " " );
Insert 10 random
integers in tree
tree.insertNode( value );
}
// perform preorder traveral of tree
System.out.println ( "\n\nPreorder traversal" );
tree.preorderTraversal();
// perform inorder traveral of tree
System.out.println ( "\n\nInorder traversal" );
tree.inorderTraversal();
Traverse binary tree via
preorder algorithm
Traverse binary tree via
inorder algorithm
32
33
34
35
36
37
38
// perform postorder traveral of tree
System.out.println ( "\n\nPostorder traversal" );
tree.postorderTraversal();
System.out.println();
}
}
Traverse binary tree via
postorder algorithm
TreeTest.java
(Part 2)
// end class TreeTest
Line 34
Inserting the following values:
39 69 94 47 50 72 55 41 97 73
Preorder traversal
39 69 47 41 50 55 94 72 73 97
Inorder traversal
39 41 47 50 55 69 72 73 94 97
Postorder traversal
41 55 50 47 73 72 97 94 69 39