Transcript Powerpoint Slides

Dynamic Data Structures and
Generics
Chapter 10
Chapter 10
1
Reminders
• Project 6 due Nov 03 @ 10:30 pm
• Project 5 grades released (or by tonight):
regrade requests due by next Friday
• Exam 2: handed back next week, solution
discussed next week
Chapter 10
2
Introduction
• A data structure is a construct used to
organize data in a specific way.
• An array is a static data structure.
• Dynamic data structures can grow and shrink
while a program is running.
• Vectors and linked data structures are
dynamic.
Chapter 10
3
Introduction to Vectors, cont.
• Vectors serve the same purposes as arrays,
but can change in length while a program is
running.
• This added flexibility comes at a price:
– Vectors are less efficient than arrays.
– The base type of a vector must be a class
type rather than a primitive type. (Automatic
boxing and unboxing make this requirement less
significant than it used to be.)
Chapter 10
4
Using Vectors
• The definition of class Vector must be
imported.
import java.util.*;
• to create and name a vector
Vector<String> v = new Vector<String>(20);
– The vector v stores objects of class String
and has an initial capacity of 20.
• Don’t need to specify the class type
Vector v = new Vector(20);
- Can store any kind of object
Chapter 10
5
Using Vectors, cont.
– When more capacity is needed, the system
allocates more memory automatically.
– If the initial capacity was sufficient, the
code is more efficient.
• In this example, the base type is type String.
– Any class can be used as the base type.
– But, wrapper classes MUST be used for
primitive types.
Chapter 10
6
Adding, Getting, and Setting
Values
• to add an element
v.addElement(“Hello!”);
• to get the value of an element
String temp = v.elementAt(index);
• to change the value of an existing element
v.setElementAt(“Hi, Mom!”, index);
*** element must already exist to use setElementAt ***
Chapter 10
7
addElement vs. insertElementAt
• Remember that add element always adds an element at the end of the
Vector. If the Vector v currently contains:
“A”
“B”
“C”
“D”
size = 4
• After v.addElement(“E”):
“A”
“B”
“C”
“D”
“E”
size = 5
• If we had done v.insertElementAt(“E”,2) instead of the
addElement line above:
“A”
“B”
“E”
“C”
“D”
size = 5
• Finally, if we had done v.insertElementAt(“E”,4) instead of
the two lines above, it would be the same as calling
v.addElement(“E”):
“A”
“B”
“C”
“D”
“E”
Chapter 10
size = 5
8
setElementAt vs. insertElementAt
• setElementAt changes an existing element while
insertElementAt inserts a new element. The index
parameter of setElementAt must be less than the size
of the vector.
• Example: Our original Vector v:
“A”
“B”
“C”
“D”
size = 4
• After v.setElementAt(“E”,2):
“A”
“B”
“E”
“D”
size = 4
• After v.insertElementAt(“E”,2): (Instead of line
above)
“A”
“B”
“E”
“C”
“D”
Chapter 10
size = 5
9
Size and Indices
• to learn the maximum capacity of the vector
int maxSize = v.capacity();
• To learn the size of the vector
int howMany = v.size();
• The indices range from 0 to v.size()-1.
Chapter 10
10
Chapter 10
11
Introduction to Linked Data
Structures
• A linked data structure is a collection of
objects (called nodes), each containing data
and a (potential) reference to (at least) one
other node.
Chapter 10
12
Linked Lists
• The predefined LinkedList class is part of the
java.util package.
• Nevertheless, to learn how linked data
structures work, we’ll construct a simplified
example of a linked list.
Chapter 10
13
Linked Lists, cont.
Chapter 10
14
Linked Lists, cont.
• Each node is an object of a class that has (at
least) two instance variables:
– the data
– the link.
Chapter 10
15
Chapter 10
16
Moving Down a Linked List
Chapter 10
17
Adding a Node at the Start
Chapter 10
18
Inner Classes
• An inner class is a class defined within
another class.
Chapter 10
19
Defining an Inner Class
public class OuterClass
{
OuterClass_Instance_Variables
OuterClass_Methods
private class InnerClass
{
InnerClass_Instance_Variables
InnerClass_Methods
}
}
Chapter 10
20
Access to Members
• The inner and outer classes’ methods have
access to each other’s methods and instance
variables, even when they are declared
private.
Chapter 10
21
Node Inner Classes
• By making the node class an inner class, data
structure classes become self-contained.
• Further, the accessor and mutator methods of
the inner class can be eliminated since
instance variables of an inner class are
accessible directly.
Chapter 10
22
Chapter 10
23
Chapter 10
24
Iterators
• With a collection of objects, such as the
nodes of a linked list, we often need to “step
through” all the objects to perform some
action on each object.
• An iterator allows us to “step through” a
collection of objects.
Chapter 10
25
Iterators, cont.
• The loop control variable of a for loop
functions as an iterator for an array.
for (int i = 0; i < a.length, i++)
process a[i];
Chapter 10
26
Iterators, cont.
• Similarly, an instance variable capable of
referencing a node, can serve the same
purpose as the loop control variable in a for
loop.
• Another instance variable capable of
referencing a node can “follow behind” to
provide access to the previous node.
Chapter 10
27
Advancing to the Next Node
Chapter 10
28
Adding a Node
Chapter 10
29
Deleting a Node
Chapter 10
30
Variations on a Linked List
• A reference to the last node in a linked list
can be useful.
…
public ListNode head;
public ListNode tail;
…
• A linked list can contain (or reference) any
kind of data.
Chapter 10
31
Variations on a Linked List,
cont.
• A linked list can contain different kinds of
objects
private class ListNode
{
private Object data;
private ListNode link;
...
}
Chapter 10
32
Variations on a Linked List,
cont.
• An additional reference can be added to
reference the previous node, producing a
doubly-linked list.
private class ListNode
{
private Object data;
private ListNode next;
private ListNode previous;
...
}
Chapter 10
33
Variations on a Linked List,
cont.
Chapter 10
34
Variations on a Linked List,
cont.
• The last node in a singly-linked list can
reference the first node, producing a
circularly-linked list.
• The last node in a doubly-linked list can
reference the first node with its next
reference, and the first node can reference
the last node with its previous reference,
producing a doubly-circularly-linked list.
Chapter 10
35
Introduction to Generics
• Java 5.0 allows definitions, called generics,
that include parameters for types.
• Generics can be subtle and full of pitfalls.
• We provide an introduction to generics.
• Serious programming with generics is
presented in more advanced texts.
Chapter 10
36
Generic Basics
• Classes and methods can have a type
parameter.
• Any class type can be substituted for the type
parameter, producing a specific class type or
method.
Chapter 10
37
Generic Basics, cont.
• class Sample<T>
Chapter 10
38
Generic Basics, cont.
• A class definition with a type parameter is
stored in a file and compiled just like any
other class.
• When used in code a class type must be
specified so that it can be substituted for the
type parameter.
Chapter 10
39
Generic Basics, cont.
• example
Sample<String> o1 = new Sample<String>();
o1.setData(“Hello”);
Sample<Species> o2 = new Sample<Species>();
Species s = new Species();
<code to set the data for object s>
o2.setData(s);
Chapter 10
40
Generic Basics, cont.
• You cannot substitute a primitive type for a
type parameter.
• You must instead use a class type.
Chapter 10
41
Chapter 10
42
Chapter 10
43
Chapter 10
44
Generic Constructor
• The class name in a parameterized class
definition has a type parameter attached.
• But, a generic constructor name has no type
parameter and the type parameter is not used
in the heading of the constructor definition.
public LinkedList()
not
public LinkedList<e>() // ILLEGAL
Chapter 10
45
Summary
• You have become familiar with vectors.
• You have learned about linked data structures
in Java.
• You have learned how to manipulate linked
lists.
• You have learned to use inner classes in
defining linked data structures
Chapter 10
46
Summary, cont.
• You have learned about iterators.
• You have learned about generics (parameters
for types).
Chapter 10
47