Java程序辅导

Introductory Programming In Java
Comp6700/Comp2140
Week 8, 2016
Henry Gardner/ Alexei Khorev/ Charles Martin
Mid semester exam results released
Please see us if you feel you need help or feedback
Next week – short week: make up lab on Friday (3-5pm)
Following week is MSE#2 (no regular labs)
Expect content to include class structure and inheritance and 
collections and other stuff (more information next week)
Draft Assignment 2 released on Friday
Assignment 1 being marked – complete end of next week?
BEWARE … THE SECOND PART OF SEMESTER 
GOES FAST
How are you coping……?
2
Data Structures in the Java Collections Framework
Interfaces and implementations
Linked lists versus arrays
Other Data Structures: Queues, stacks, doubly-linked lists
Sets, maps (briefly)
Collection Traversal - iterators
https://docs.oracle.com/javase/8/docs/technotes/guides/
collections/index.html
Alexei lectures A1 and A2
This week’s Henry lecture
3
https://docs.oracle.com/javase/8/docs/technotes/guides/
collections/overview.html
A collection is an object that represents a group of 
objects
A collections framework is a unified architecture for 
representing and manipulating collections, enabling 
collections to be manipulated independently of 
implementation details. 
 Interfaces and default implementations
Implementations in Java Collections Framework are 
highly optimised (including parallel implementations)
Collections Framework Overview
4
5(Look at interfaces “Iterable” and “Collection”)
Simulation of a “library” of “book” objects.
A list of books implements a “list” interface.
Books can be stored as an
Array
ArrayList
Linked List
Interface and implementation example
6
For example:
Nodes contain objects with data together with a link to 
the “next” node.
The first node (“header node”) is special. It is easy to 
add extra nodes here.
It is pretty easy to delete or insert new nodes into the 
middle of the list
What is a “linked list”
7
8
9
A simple interface
10
See “BookListWithLL.java”
11
The Library.java example shows that the BookList interface can be 
implemented by quite different data structures.
“Complexity”
Arraylist
Linked List
ArrayLists are generally preferred unless you expect a lot of 
resizing. 
12
Note that you can have a doubly linked list (Java’s 
“LinkedList” class)
13
Stacks, Queues, Trees…
Queues and stacks are very popular interfaces. Both are widely 
used in systems level programming (for managing memory and 
processes) as well as in other applications.
A Stack is a “last in first out” (LIFO) collection type which can be 
implemented by adding (with a push method) and extracting (with a 
pop method) from the head of a list.
Other data structures
14
A Queue is a “first in first out” (FIFO) type which can be 
implemented by adding objects (with an enqueue method) to the 
head of a list and by extracting them (with a dequeue method) from 
its tail.
15
Sets disallow duplicate elements; like “bags of data”
Implemented using a hash table in the “HashSet” class. Very fast, 
O(1), operations to add data and test whether an object is contained 
in that set. See SetTest.java
“SortedSet” extends “Set” and implements the “Comparable” 
interface. The elements of the set can be ranked, partitioned and 
compared. It is implemented using a binary tree as the data 
structure
Other collections – sets and maps
16
Maps represent a correspondence between two collections, a 
collection of “keys” and a collection of “values”. There are no 
duplicate keys (they form a set).
Maps do not implement the Collection interface
A model of the mathematical abstraction of a function
17
Bulk operations
Conversion to arrays
Other operations of the Collection interface
18
The idea is to return an Iterator object which can systematically 
enumerate every element in the collection in a particular order. 
The order might not be straightforward in the case of some data-
structures (Sets, Trees etc..)
The Iterator interface , implemented by this object, defines 
simple methods for getting the next element in the collection 
This iterator is a separate object which is returned by the  
iterator() factory-method. Any collection which implements the 
Iterable interface must have such a method.
For example: BookListIterator.java
Iterators
19
Nice and neat ways to “hide the iterator”:
See 
http://docs.oracle.com/javase/1.5.0/docs/guide/language/foreach.html
Replace
By
But note that for-each loops can be unsafe if you are modifying the 
collection (deleting elements) along the way.
For each loops
20