Transcript ppt version - University of Pittsburgh

Lec.12 (Chapter 12) Dynamic
Data Structures
Jiang (Jen) ZHENG
June 13th, 2005
Outline
 Preview of Data Structure
 How to us those data structures
 How to implement those data structures
 What tools to know and use in order to implement those
data structures
 What Java provide to us and we can use the features
 Dynamic Data Structure
 Basic Data Structure in Java
 List: ArrayList, LinkedList
 Stack
 More on CS0445 …
CS401/COE401 Summer 2005.Department of
Computer Science.University of
Pittsburgh.Lecture 12
2
Preview of Data Structure
 The way to store and retrieve information.
 Basic Data Structures:






Array
Linked List
Stack
Queue
Tree
…
CS401/COE401 Summer 2005.Department of
Computer Science.University of
Pittsburgh.Lecture 12
3
Preview of Data Structures
 In Data Structures, we want to learn,
understand and be able to utilize many of the
data structures that are fundamental to
computer science


Data structures such as vectors, stacks,
queues, linked-lists and trees are used
throughout computer science
We should understand these from a user's
point of view:

What are these data structures and how do I use
them in my programs?
CS401/COE401 Summer 2005.Department of
Computer Science.University of
Pittsburgh.Lecture 12
4
Preview of Data Structures
 We also want to understand implementation
issues related to these data structures, and to
see how they can be implemented in the Java
programming language


Data structures can be implemented in various
ways, each of which has implications (ex: runtime differences, code complexity, modifiability)
We should understand these data structures from
an implementer's point of view:

How can these data structures be effectively
implemented?
CS401/COE401 Summer 2005.Department of
Computer Science.University of
Pittsburgh.Lecture 12
5
Preview of Data Structures
 We also want to understand and utilize
programming ideas and techniques utilized in
data structure implementation

Object-oriented programming, dynamic
memory utilization, recursion and other
principles must be understood in order to
effectively implement data structures

What tools must I know and be able to use in
order to implement data structures?
CS401/COE401 Summer 2005.Department of
Computer Science.University of
Pittsburgh.Lecture 12
6
Preview of Data Structures
 We also want to learn more of the Java
programming language and its features, and
to become more proficient at programming
with it


Java is a very large language with extensive
capabilities
As your programming skills improve, you can
utilize more of these capabilities effectively

Since I am working with Java, how well can I
learn and use the language and its features?
CS401/COE401 Summer 2005.Department of
Computer Science.University of
Pittsburgh.Lecture 12
7
Dynamic Data Structure
 The data structure can expand and contract
during computation





Linked list
Queue
Stack
Vector
…
CS401/COE401 Summer 2005.Department of
Computer Science.University of
Pittsburgh.Lecture 12
8
List In Java
 Example: Consider the idea of a List:


Ordered (by position), indexable collection of data
In Java this is an interface – with some methods
as shown:

void add(int index, Object element)
 Add a new object at the specified index

int indexOf(Object o)
 Find the object and return its index

Object get(int index)
 Return the object at the specified index

Object remove(int index)
 Remove (and return) the object at the specified index
CS401/COE401 Summer 2005.Department of
Computer Science.University of
Pittsburgh.Lecture 12
9
List in Java
 Classes Implement the List interface
 ArrayList: Resizable-array implementation of the List
interface
 LinkedList: Use a linked list of nodes as the underlying
Head data structure to implementation of the List interface


Vector: The Vector class implements a growable array of
objects
See Java API.CS401/COE401 Summer 2005.Department of
10
Computer Science.University of
Pittsburgh.Lecture 12
List in Java

Each implementation has advantages and
disadvantages

Ex: Advantage of ArrayList
 get(i) can be done in one step, since we just go to
that index in the array
 In a LinkedList we must follow references down the
list

Ex: Advantage of LinkedList
 add(i, obj) requires only creating a new object and
linking it correctly
 In an ArrayList we must shift all of the items from i
down a spot in order to make "room" at index i
CS401/COE401 Summer 2005.Department of
Computer Science.University of
Pittsburgh.Lecture 12
11
List in Java

Ex: See ex27.java


Note that the operations work for both ArrayList
and LinkedList, using the List interface
However, the implementations and efficiencies of
the operations differ
 More in CS 0445!
CS401/COE401 Summer 2005.Department of
Computer Science.University of
Pittsburgh.Lecture 12
12
Stack in Java
 Stack class is a subclass of Vector
 Methods implemented





Boolean empty()
Object peek()
Object pop()
Object push(Object item)
int search(Object o)
 Preview of Stack if needed
 See API
CS401/COE401 Summer 2005.Department of
Computer Science.University of
Pittsburgh.Lecture 12
13
More on CS0445
 In CS 0445 you will see these and other
implementation ideas in detail
CS401/COE401 Summer 2005.Department of
Computer Science.University of
Pittsburgh.Lecture 12
14
Garbage Collection
 In C, C++: memory is freed explicitly by the
programmer when certain data structures are
no longer needed.
 In Java: the computer automatically figures
out when an object is no longer needed and
removes it – Garbage Collection.


Reference Counting: when the count goes to
zero, the object can be collected.
Mark and sweep garbage collection: any
object not marked is garbage and can be
recycled.
CS401/COE401 Summer 2005.Department of
Computer Science.University of
Pittsburgh.Lecture 12
15
Creating and Using Package
 Creating Package


Add a package statement to the top of each
class in the package. Ex. package tio;
Compile the java files. Ex. javac tio/java.*
 Using Package


import tio.*; to import all the classes from a
package.
import tio.Concole; to import the specific class.
CS401/COE401 Summer 2005.Department of
Computer Science.University of
Pittsburgh.Lecture 12
16