OOP
Data Structures
Dynamic data structures
 Grow and shrink at execution time
 Several types
•
•
•
•
Linked lists
Stacks
Queues
Binary trees
1
Dipartimento di Automatica e Informatica - Politecnico di Torino Silvano Rivoira, 2004
OOP
Recursive data types
 Self-referential class
– Contains instance variable referring to object of same class
class Node {
private int data;
private Node nextNode; // reference to next linked node
}
• Member nextNode is a link
– nextNode “links” a Node object to another Node object
15
10
2
Dipartimento di Automatica e Informatica - Politecnico di Torino Silvano Rivoira, 2004
OOP
Linked Lists (1)
 Linked list
–
–
–
–
Linear collection of self-referential class instances (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
3
Dipartimento di Automatica e Informatica - Politecnico di Torino Silvano Rivoira, 2004
OOP
Linked Lists (2)
firstNode
H
lastNode
D
...
Q
4
Dipartimento di Automatica e Informatica - Politecnico di Torino Silvano Rivoira, 2004
OOP
Linked Lists (3)
(a)
firstNode
7
11
new Listnode
12
(b)
firstNode
7
11
new Listnode
12
Graphical representation of operation insertAtFront.
5
Dipartimento di Automatica e Informatica - Politecnico di Torino Silvano Rivoira, 2004
OOP
Linked Lists (4)
(a)
firstNode
12
(b)
lastNode
7
firstNode
12
11
lastNode
7
11
new Listnode
5
new Listnode
5
Graphical representation of operation insertAtBack.
6
Dipartimento di Automatica e Informatica - Politecnico di Torino Silvano Rivoira, 2004
OOP
Linked Lists (5)
(a)
firstNode
12
(b)
lastNode
7
11
firstNode
12
5
lastNode
7
11
5
removeItem
Graphical representation of operation removeFromFront.
7
Dipartimento di Automatica e Informatica - Politecnico di Torino Silvano Rivoira, 2004
OOP
Linked Lists (6)
(a)
firstNode
12
(b)
lastNode
7
firstNode
12
11
current
7
5
lastNode
11
5
removeItem
Graphical representation of operation removeFromBack.
8
Dipartimento di Automatica e Informatica - Politecnico di Torino Silvano Rivoira, 2004
OOP
Linked Lists (7)
1
2
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// List.java
// ListNode and List class declarations.
package lists;
// class to represent one node in a list
class ListNode {
// package access members; List can access these directly
Object data;
Self-referential
ListNode nextNode;
// create a ListNode that refers to object
ListNode( Object object )
{
this( object, null );
}
class
ListNode contains data
and link to nextNode
// create ListNode that refers to Object and to next ListNode
ListNode( Object object, ListNode node )
{
data = object;
nextNode = node;
}
Dipartimento di Automatica e Informatica - Politecnico di Torino Silvano Rivoira, 2004
9
OOP
Linked Lists (8)
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
// return reference to data in node
Object getObject()
{
return data; // return Object in this node
}
// return reference to next node in list
ListNode getNext()
{
return nextNode; // get next node
}
} // end class ListNode
// class List declaration
public class List {
private ListNode firstNode;
private ListNode lastNode;
private String name; // string like "list" used in printing
// construct empty List with "list" as the name
public List()
{
this( "list" );
}
Dipartimento di Automatica e Informatica - Politecnico di Torino Silvano Rivoira, 2004
10
OOP
Linked Lists (9)
51
52
53
54
55
56
57
58
59
60
61
62
64
65
66
67
68
69
70
71
72
73
74
75
76
// construct an empty List with a name
public List( String listName )
{
name = listName;
firstNode = lastNode = null;
}
// insert Object at front of List
public void insertAtFront( Object insertItem )
{
if ( isEmpty() ) // firstNode and lastNode refer to same object
firstNode = lastNode = new ListNode( insertItem );
else // firstNode refers to new node
firstNode = new ListNode( insertItem, firstNode );
}
// insert Object at end of List
public void insertAtBack( Object insertItem )
{
if ( isEmpty() ) // firstNode and lastNode refer to same Object
firstNode = lastNode = new ListNode( insertItem );
else // lastNode's nextNode refers to new node
lastNode = lastNode.nextNode = new ListNode( insertItem );
}
Dipartimento di Automatica e Informatica - Politecnico di Torino Silvano Rivoira, 2004
11
OOP
Linked Lists (10)
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
// remove first node from List
public Object removeFromFront() throws EmptyListException
{
if ( isEmpty() ) // throw exception if List is empty
throw new EmptyListException( name );
Object removedItem = firstNode.data; // retrieve data being removed
// update references firstNode and lastNode
if ( firstNode == lastNode )
firstNode = lastNode = null;
else
firstNode = firstNode.nextNode;
return removedItem; // return removed node data
} // end method removeFromFront
12
Dipartimento di Automatica e Informatica - Politecnico di Torino Silvano Rivoira, 2004
OOP
Linked Lists (11)
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
121
// remove last node from List
public Object removeFromBack() throws EmptyListException
{
if ( isEmpty() ) // throw exception if List is empty
throw new EmptyListException( name );
Object removedItem = lastNode.data; // retrieve data being removed
// update references firstNode and lastNode
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;
lastNode = current; // current is new lastNode
current.nextNode = null;
}
return removedItem; // return removed node data
} // end method removeFromBack
Dipartimento di Automatica e Informatica - Politecnico di Torino Silvano Rivoira, 2004
13
OOP
Linked Lists (12)
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
146
147
149
// determine whether list is empty
public boolean isEmpty()
{
return firstNode == null; // return true if List is empty
}
// output List contents
public void print()
{
if ( isEmpty() ) {
System.out.println( "Empty " + name );
return;
}
System.out.print( "The " + name + " is: " );
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;
}
System.out.println( "\n" );
}
} // end class List
Dipartimento di Automatica e Informatica - Politecnico di Torino Silvano Rivoira, 2004
14
OOP
Linked Lists (13)
1
2
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// EmptyListException.java
// Class EmptyListException declaration.
package lists;
public class EmptyListException extends RuntimeException {
// no-argument constructor
public EmptyListException()
{
this( "List" );
// call other EmptyListException constructor
}
// constructor
public EmptyListException( String name )
{
super( name + " is empty" ); // call superclass constructor
}
} // end class EmptyListException
15
Dipartimento di Automatica e Informatica - Politecnico di Torino Silvano Rivoira, 2004
OOP
Linked Lists (14)
1
2
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// ListTest.java
// ListTest class to demonstrate List capabilities.
import lists.*;
public class ListTest {
public static void main( String args[] )
{
List list = new List(); // create the List container
// objects to store in list
Boolean bool = Boolean.TRUE;
Character character = new Character( '$' );
Integer integer = new Integer( 34567 );
String string = "hello";
// insert references to objects in list
list.insertAtFront( bool );
list.print();
list.insertAtFront( character );
list.print();
list.insertAtBack( integer );
list.print();
list.insertAtBack( string );
list.print();
16
Dipartimento di Automatica e Informatica - Politecnico di Torino Silvano Rivoira, 2004
OOP
Linked Lists (15)
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
46
47
48
49
50
51
52
54
// remove objects from list; print after each removal
try {
Object 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();
} // end try block
// catch exception if remove is attempted on an empty List
catch ( EmptyListException emptyListException ) {
emptyListException.printStackTrace();
}
}
} // end class ListTest
Dipartimento di Automatica e Informatica - Politecnico di Torino Silvano Rivoira, 2004
17
OOP
Linked Lists (16)
The list is: true
The list is: $ true
The list is: $ true 34567
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
18
Dipartimento di Automatica e Informatica - Politecnico di Torino Silvano Rivoira, 2004
OOP
Stacks (1)
Stack
 Constrained version of a linked list
• Add and remove nodes only to and from the top of the
stack (Last In First Out)
• Push method adds node to top of stack
• Pop method removes node from top of stack
19
Dipartimento di Automatica e Informatica - Politecnico di Torino Silvano Rivoira, 2004
OOP
Stacks (2)
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
// Stack.java
// Class Stack declaration with composed List object.
package lists;
public class Stack {
private List stackList;
// construct stack
public Stack ()
{
stackList = new List( "stack" );
}
// add object to stack
public void push( Object object )
{
stackList.insertAtFront( object );
}
// remove object from stack
public Object pop() throws EmptyListException
{
return stackList.removeFromFront();
}
Method push adds
node to top of stack
Method pop removes
node from top of stack
20
Dipartimento di Automatica e Informatica - Politecnico di Torino Silvano Rivoira, 2004
OOP
Stacks (3)
26
27
28
29
30
31
32
33
34
35
36
37
38
// determine if stack is empty
public boolean isEmpty()
{
return stackList.isEmpty();
}
// output stack contents
public void print()
{
stackList.print();
}
} // end class Stack
21
Dipartimento di Automatica e Informatica - Politecnico di Torino Silvano Rivoira, 2004
OOP
Stacks (4)
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
// StackTest.java
// Class StackTest.
import lists.*;
public class StackTest {
public static void main( String args[] )
{
Stack stack = new Stack ();
// 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();
Create stack
Create values (Objects)
to store in stack
Insert values in stack
Dipartimento di Automatica e Informatica - Politecnico di Torino Silvano Rivoira, 2004
22
OOP
Stacks (5)
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// remove items from stack
try {
Object removedObject = null;
Remove object from stack
while ( true ) {
removedObject = stack.pop(); // use pop method
System.out.println( removedObject.toString() + " popped" );
stack.print();
}
}
// catch exception if stack is empty when item popped
catch ( EmptyListException emptyListException ) {
emptyListException.printStackTrace();
}
}
} // end class StackTest
23
Dipartimento di Automatica e Informatica - Politecnico di Torino Silvano Rivoira, 2004
OOP
Stacks (6)
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
lists.EmptyListException: stack is empty
at lists.List.removeFromFront(List.java:82)
at lists.Stack.pop(Stack.java:22)
at StackTest.main(StackTest.java:33)
24
Dipartimento di Automatica e Informatica - Politecnico di Torino Silvano Rivoira, 2004
OOP
Queues (1)
Queue
 Similar to a supermarket checkout line
(First In First Out)
 Nodes inserted only at tail (back)
• Method enqueue
 Nodes removed only from head (front)
• Method dequeue
25
Dipartimento di Automatica e Informatica - Politecnico di Torino Silvano Rivoira, 2004
OOP
Queues (2)
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
// Queue.java
// Class Queue.
package lists;
public class Queue {
private List queueList;
// construct queue
public Queue()
{
queueList = new List( "queue" );
}
// add object to queue
public void enqueue( Object object )
{
queueList.insertAtBack( object );
}
// remove object from queue
public Object dequeue() throws EmptyListException
{
return queueList.removeFromFront();
}
Method enqueue adds
node to top of stack
Method dequeue
removes node from
top of stack
26
Dipartimento di Automatica e Informatica - Politecnico di Torino Silvano Rivoira, 2004
OOP
Queues (3)
26
27
28
29
30
31
32
33
34
35
36
37
38
// determine if queue is empty
public boolean isEmpty()
{
return queueList.isEmpty();
}
// output queue contents
public void print()
{
queueList.print();
}
} // end class Queue
27
Dipartimento di Automatica e Informatica - Politecnico di Torino Silvano Rivoira, 2004
OOP
Queues (4)
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
// QueueTest.java
// Class QueueTest.
import lists.*;
public class QueueTest {
public static void main( String args[] )
{
Queue queue = new Queue();
// 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 queue
Create values (Objects)
to store in queue
method
bool );
character );
integer );
Insert values in queue
string );
28
Dipartimento di Automatica e Informatica - Politecnico di Torino Silvano Rivoira, 2004
OOP
Queues (5)
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// remove objects from queue
try {
Object removedObject = null;
Remove value from queue
while ( true ) {
removedObject = queue.dequeue(); // use dequeue method
System.out.println( removedObject.toString() + " dequeued" );
queue.print();
}
}
// process exception if queue is empty when item removed
catch ( EmptyListException emptyListException ) {
emptyListException.printStackTrace();
}
}
} // end class QueueTest
29
Dipartimento di Automatica e Informatica - Politecnico di Torino Silvano Rivoira, 2004
OOP
Queues (6)
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
$ dequeued
The queue is: 34567 hello
34567 dequeued
The queue is: hello
hello dequeued
Empty queue
lists.EmptyListException: queue is empty
at lists.List.removeFromFront(List.java:88)
at lists.Queue.dequeue(Queue.java:23)
at QueueTest.main(QueueTest.java:33)
30
Dipartimento di Automatica e Informatica - Politecnico di Torino Silvano Rivoira, 2004
OOP
Trees (1)
Binary tree
 Non-linear, two-dimensional data structure
• (unlike linked lists, stacks and queues)
 Nodes contain two 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 are siblings
Nodes with no children are leaf nodes
31
Dipartimento di Automatica e Informatica - Politecnico di Torino Silvano Rivoira, 2004
OOP
Trees (2)
level 0
B
level 1
tree
height
A
D
C
level 2
level 3
 Balanced trees
 for every node the heights of left and right subtrees differ at
most of 1
 the height of a balanced tree with n nodes is O(log2 n)
32
Dipartimento di Automatica e Informatica - Politecnico di Torino Silvano Rivoira, 2004
OOP
Search Trees (1)
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
33
Dipartimento di Automatica e Informatica - Politecnico di Torino Silvano Rivoira, 2004
OOP
Search Trees (2)
47
25
11
7
17
77
43
31 44
65
93
68
34
Dipartimento di Automatica e Informatica - Politecnico di Torino Silvano Rivoira, 2004
OOP
Search Trees (3)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// Tree.java
// Declaration of class TreeNode and class Tree.
package lists;
// class TreeNode declaration
class TreeNode {
// package access members
TreeNode leftNode, rightNode;
int data;
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
}
35
Dipartimento di Automatica e Informatica - Politecnico di Torino Silvano Rivoira, 2004
OOP
Search Trees (4)
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
47
// insert a new node in the node subtree; ignore duplicate values
public void insert( int insertValue )
{
If value of inserted
// insert in left subtree
node is less than value
if ( insertValue < data ) {
// insert new TreeNode
if ( leftNode == null )
leftNode = new TreeNode( insertValue );
of tree node, insert
node in left subtree
else // continue traversing left subtree
leftNode.insert( insertValue );
}
// insert in right subtree
else if ( insertValue > data ) {
If value of inserted node
is greater than value of
tree node, insert node in
right subtree
// insert new TreeNode
if ( rightNode == null )
rightNode = new TreeNode( insertValue );
else // continue traversing right subtree
rightNode.insert( insertValue );
}
} // end method insert
} // end class TreeNode
Dipartimento di Automatica e Informatica - Politecnico di Torino Silvano Rivoira, 2004
36
OOP
Search Trees (5)
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
// class Tree declaration
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
public void insertNode( int insertValue )
{
if ( root == null )
root = new TreeNode( insertValue ); // create the root node here
else
root.insert( insertValue ); // call the insert method
}
// begin preorder traversal
public void preorderTraversal()
{
preorderHelper( root );
}
Dipartimento di Automatica e Informatica - Politecnico di Torino Silvano Rivoira, 2004
37
OOP
Search Trees (6)
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
// recursive method to perform preorder traversal
private void preorderHelper( TreeNode node )
{
if ( node == null )
return;
System.out.print( node.data + " " ); // output node data
preorderHelper( node.leftNode );
// traverse left subtree
preorderHelper( node.rightNode );
// traverse right subtree
}
// begin inorder traversal
public void inorderTraversal()
{
inorderHelper( root );
}
Preorder traversal – obtain
data, traverse left subtree,
then traverse right subtree
// recursive method to perform inorder traversal
private void inorderHelper( TreeNode node )
{
if ( node == null )
return;
Inorder traversal –traverse
left subtree, obtain data,
then traverse right subtree
inorderHelper( node.leftNode );
// traverse left subtree
System.out.print( node.data + " " ); // output node data
inorderHelper( node.rightNode );
// traverse right subtree
}
Dipartimento di Automatica e Informatica - Politecnico di Torino Silvano Rivoira, 2004
38
OOP
Search Trees (7)
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
// begin postorder traversal
public void postorderTraversal()
{
postorderHelper( root );
}
// recursive method to perform postorder traversal
private void postorderHelper( TreeNode node )
{
if ( node == null )
return;
Postorder traversal – traverse
left subtree, traverse right
subtree, then obtain data
postorderHelper( node.leftNode );
// traverse left subtree
postorderHelper( node.rightNode );
// traverse right subtree
System.out.print( node.data + " " ); // output node data
}
} // end class Tree
39
Dipartimento di Automatica e Informatica - Politecnico di Torino Silvano Rivoira, 2004
OOP
Search Trees (8)
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
// TreeTest.java
// This program tests class Tree.
import lists.*;
public class TreeTest {
public static void main( String args[] )
{
Tree tree = new Tree();
int value;
System.out.println( "Inserting the following values: " );
// insert 10 random integers (0-99) in tree
for ( int i = 1; i <= 10; i++ ) {
value = ( int ) ( Math.random() * 100 );
System.out.print( value + " " );
tree.insertNode( value );
}
Insert 10 random
integers from 0 to
99 in tree
System.out.println ( "\n\nPreorder traversal" );
tree.preorderTraversal(); // perform preorder traversal of tree
System.out.println ( "\n\nInorder traversal" );
tree.inorderTraversal(); // perform inorder traversal of tree
40
Dipartimento di Automatica e Informatica - Politecnico di Torino Silvano Rivoira, 2004
OOP
Search Trees (9)
26
27
28
29
30
31
32
System.out.println ( "\n\nPostorder traversal" );
tree.postorderTraversal(); // perform postorder traversal of tree
System.out.println();
}
} // end class TreeTest
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
41
Dipartimento di Automatica e Informatica - Politecnico di Torino Silvano Rivoira, 2004
OOP
Searching in binary search trees
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// recursive method to perform searching
public Treenode treeSearch( TreeNode node, int searchValue )
{
if ( node == null )
return null;
if ( searchValue == node.data )
return node;
if ( searchValue < node.data )
return treeSearch( node.left, searchValue);
// search in left subtree
else
return treeSearch( node.right, searchValue ); // search in right subtree
}
complexity: O(height)
balanced trees  complexity: O(log2 n)
42
Dipartimento di Automatica e Informatica - Politecnico di Torino Silvano Rivoira, 2004