Transcript Wojciech Bieniecki

Advanced
Java Programming
Lecture 3
Introduction to Collections
dr inż. Wojciech Bieniecki
[email protected]
http://wbieniec.kis.p.lodz.pl
1
Introduction
http://docs.oracle.com
A collection (containter) - an object that groups multiple elements into a single
unit. Collections are used to store, retrieve, operate, and communicate
aggregated data.
Typically, they represent data items that form a natural group, such as:
- poker hand (a collection of cards),
- mail folder (a collection of letters),
- telephone directory (a mapping of names to phone numbers).
Collection implementations in early versions of the Java platform included Vector,
Hashtable and array. They did not contain a collections framework.
2
Introduction
http://docs.oracle.com
Collections framework - a unified architecture for representing and manipulating
collections. Collections frameworks contain the following:
Interfaces – abstract data types that represent collections. Interfaces allow collections to
be manipulated independently of the details of their representation. Interfaces generally
form a hierarchy.
Implementations – concrete implementations of the collection interfaces – reusable data
structures.
Algorithms – methods that perform computations (searching, sorting, iteration) on objects
that implement collection interfaces.
Algorithms are polymorphic – the same method can be used on many different
implementations of the appropriate collection interface. In essence, algorithms are
reusable functionality.
Apart from the Java Collections Framework, the best-known examples of collections
frameworks are the C++ Standard Template Library (STL) and Smalltalk's collection
hierarchy. Historically, collections frameworks have been quite complex, which gave them a
reputation for having a steep learning curve. We believe that the Java Collections
Framework breaks with this tradition, as you will learn for yourself in this chapter.
3
Introduction
http://docs.oracle.com
A collections framework is a unified architecture for representing and manipulating
collections. All collections frameworks contain the following:
Interfaces: These are abstract data types that represent collections. Interfaces allow
collections to be manipulated independently of the details of their representation. In
object-oriented languages, interfaces generally form a hierarchy.
Implementations: These are the concrete implementations of the collection interfaces. In
essence, they are reusable data structures.
Algorithms: These are the methods that perform useful computations, such as searching
and sorting, on objects that implement collection interfaces. The algorithms are said to
be polymorphic: that is, the same method can be used on many different implementations
of the appropriate collection interface. In essence, algorithms are reusable functionality.
4
Introduction
http://docs.oracle.com
Advantages of the Java Collections Framework
May reduce programming effort
-provides useful high-level data structures and algorithms
Increases program speed and quality:
-high-performance, high-quality implementations of useful data structures and algorithms
-A possibility to replace an individual implementation
-You may concentrate to programs' quality and performance.
Allows interoperability among unrelated APIs
Reduces effort to learn and to use new APIs:
- Many APIs naturally take collections on input and furnish them as output.
Reduces effort to design new APIs
Fosters software reuse
New data structures that conform to the standard collection interfaces are by nature
reusable. The same goes for new algorithms that operate on objects that implement these
5
interfaces.
Java collections (obsolete)
Java.util.Vector
An array of objects.
This is a list of objects with array functions
Main operations:
add(object) – add the object at the end of the list
add(index, object) – add the object to the list after the object pointed
by index
set(index, element) – replaces the object in the index
get(index) – returns the object from the index
indexOf(obiex) – searches of the first occurence of the object
6
Java collections (obsolete)
Java.util.Hashtable
The dictionary of the objects.
It can associate pairs: key (word) with any object.
Main operations:
put(napis, obiekt) – add a pair to the array
get(napis) – returns the object pointed by the key
Hashtable c = new Hashtable();
c.put("black", Color.black);
c.put("blue", Color.blue);
c.put("red", Color.red);
c.put("yellow", Color.yellow);
c.put("white", Color.white);
Color c = (Color) ht.get("blue");
7
Java collections (obsolete)
Java.util.Stack
A stack of the objects.
Main operations:
empty() – is the stack empty?
peek() – returns the object from the to without popping it
pop() – pops the object from the top
push(object) – throws the object on the top
search(object) – returns the index of the object if it exists on the
stack
8
Lists
System.out.println("=====lists=====\n");
ArrayList a1 = new ArrayList();
a1.add("dog");
a1.add("cat");
a1.add("dog");
System.out.println(a1);
List a2 = new ArrayList();
a2.add("wardrobe");
a2.add("table");
a2.add("wardrobe");
System.out.println(a2);
Collection a3 = new ArrayList();
a3.add("brother");
a3.add("sister");
a3.add("brother");
System.out.println(a3);
Each list will have three elements - the repetitions are allowed.
9
Sets
System.out.println("\n=====sets=====\n");
HashSet b1 = new HashSet();
b1.add("dog");
b1.add("cat");
b1.add("dog");
System.out.println(b1);
Set b2 = new HashSet();
b2.add("wardrobe");
b2.add("table");
b2.add("wardrobe");
System.out.println(b2);
Collection b3 = new HashSet();
b3.add("brother");
b3.add("sister");
b3.add("brother");
System.out.println(b3);
Each list will have the two elements - the repetitions are not allowed.
10
Maps (associative arrays)
System.out.println("\n=====associations=====\n");
HashMap c1 = new HashMap();
c1.put("dog","Baton");
c1.put("cat","Fruzia");
c1.put("dog","Fucha");
System.out.println(c1);
Map c2 = new HashMap();
c2.put("brother","Maciek");
c2.put("sister","Marta");
c2.put("brother","Marcin");
System.out.println(c2);
cat Fruzia, dog Fucha
sister Marta, brother Marcin
11
Maps (different keys)
System.out.println("\n=====mappings for diff. keys =====\n");
HashMap d1 = new HashMap();
d1.put("Baton","dog");
d1.put("Fruzia","cat");
d1.put("Fucha","dog");
System.out.println(d1);
Map d2 = new HashMap();
d2.put("Maciek","brother");
d2.put("Marta","sister");
d2.put("Marcin","brother");
System.out.println(d2);
Fruzia cat, Baton dog, Fucha dog
Maciek brother, Marta sister, Marcin brother
12
Use of iterator
public class Dog
{
private int nr;
Dog(int i)
{
nr = i;
}
void print()
{
System.out.print
("Dog-"+nr+", ");
}
public String toString()
{
return "Doggy-" + nr ;
}
public class Cat
{
private int nr;
Cat(int i)
{
nr = i;
}
void print()
{
System.out.print("Cat-"+nr+", ");
}
public String toString()
{
return "Kitty-" + nr ;
}
}
}
13
Use of iterator
ArrayList cats = new ArrayList();
for(int i = 0; i < 4; i++) cats.add(new Cat(i));
cats.add(new Dog(0));
for(int i = 0; i < cats.size(); i++)
System.out.print(cats.get(i) + ", ");
System.out.println("");
System.out.println("1===========================");
try{
for(int i = 0; i < cats.size(); i++)
((Cat)cats.get(i)).print();
}catch(Exception e) {}`
1===========================
Cat-0, Cat-1, Cat-2, Cat-3
14
Use of iterator
System.out.println("2===========================");
ArrayList dogs = new ArrayList();
for(int i=0; i<6;i++)
dogs.add(new Dog(i));
Iterator w = dogs.iterator();
while(w.hasNext())
((Dog)w.next()).print();
System.out.println("");
System.out.println("3===========================");
ListIterator from3 = dogs.listIterator(3);
while(from3.hasNext())
((Dog)from3.next()).print();
System.out.println("");
2===========================
Dog-0, Dog-1, Dog-2, Dog-3, Dog-4, Dog-5
3===========================
Dog-3, Dog-4, Dog-5
15
Use of iterator
System.out.println("4===========================");
dogs.add(1,new Dog(10));
Iterator w1 = dogs.iterator();
while(w1.hasNext())
((Dog)w1.next()).print();
System.out.println("5===========================");
dogs.set(5,new Dog(25));
Iterator w2 = dogs.iterator();
while(w2.hasNext())
((Dog)w2.next()).print();
System.out.println("");
4===========================
Dog-0, Dog-10, Dog-1, Dog-2, Dog-3, Dog-4, Dog-5
5===========================
Dog-0, Dog-10, Dog-1, Dog-2, Dog-3, Dog-25, Dog-5
16
New Java Collections
(interface hierarchy)
Interfaces
Hash tables
Set
HashSet
Resizable
arrays
Trees
Linked lists
TreeSet
LinkedHashSet
List
ArrayList
LinkedList
Queue
ArrayDequeue
Dequeue
Map
HashMap
TreeMap
Hash tables
+ Linked lists
LinkedHashMap
17
Old and new collections
(set not included)
18
Interfaces
Collection - the root of the collection hierarchy.
Represents any group of objects
Used to pass collections around and to manipulate them when maximum generality is
desired.
Set - a collection that stores unique elements.
It models the mathematical set abstraction and is used to represent sets.
List – an ordered collection.
Lists can contain duplicate elements.
It models the mathematical concept of finite sequence.
The lists are doubly linked
Queue — a collection used to hold multiple elements prior to processing.
A Queue provides additional insertion, extraction, and inspection operations.
Queues typically, order elements in a FIFO (first-in, first-out) manner.
The head of the queue is the element that would be removed by a call to remove or poll.
In a FIFO queue, all new elements are inserted at the tail of the queue.
19
Interfaces
Map
An object that maps keys to values.
A Map cannot contain duplicate keys; each key can map to at most one value.
The next two core collection interfaces are merely sorted versions of Set and Map
SortedSet
A set that maintains its elements in ascending order.
Several additional operations are provided to take advantage of the ordering.
Sorted sets are used for naturally ordered sets, such as word lists and membership rolls.
SortedMap
A Map that maintains its mappings in ascending key order.
This is the Map analog of SortedSet.
Sorted maps are used for naturally ordered collections of key/value pairs, such as
dictionaries and telephone directories.
20
Traversing Collections
for-each Construct
for (Object o : collection)
System.out.println(o);
Iterators
An Iterator is an object that enables you to traverse through a collection and to remove
elements from the collection selectively, if desired.
Use Iterator instead of the for-each construct when you need to:
- Remove the current element. The for-each construct hides the iterator, so you cannot call
remove.
- Iterate over multiple collections in parallel.
static void filter(Collection<?> c)
{
for (Iterator<?> it = c.iterator(); it.hasNext(); )
if (!cond(it.next()))
it.remove();
}
21
Collection operations
containsAll — returns true if the target Collection contains all of the elements in the
specified Collection.
addAll — adds all of the elements in the specified Collection to the target Collection.
removeAll — removes from the target Collection all of its elements that are also contained
in the specified Collection.
retainAll — removes from the target Collection all its elements that are not also contained
in the specified Collection. That is, it retains only those elements in the target Collection
that are also contained in the specified Collection.
clear — removes all elements from the Collection.
toArray – allows the contents of a Collection to be translated into an array. The simple
form with no arguments creates a new array of Object. The more complex form allows the
caller to provide an array or to choose the runtime type of the output array.
Object[] a = c.toArray();
String[] a = c.toArray(new String[0]);
22