Object-Oriented Programming

Using Java
Java Collections Framework

Quan Thai Ha

HUS
April 2, 2024
 Presentation Outline

1 Java Collection Framework

2 Lists

3 Sets

4 Queues

5 Maps

6 Collections and Iterators

7 Algorithms

1 64
Java Collections Framework

Although we can use an array as a container to store a group of elements of the same type
(primitives or references). The array, however, does not support so-called dynamic
allocation - it has a fixed length which cannot be changed once allocated. Furthermore,
array is a simple linear structure. Many applications may require more complex data
structure such as linked list, stack, hash table, set, or tree.
In Java, dynamically allocated data structures (such as ArrayList, LinkedList, Vector, Stack,
HashSet, HashMap, Hashtable) are supported in a unified architecture called the
Collection Framework, which mandates the common behaviors of all the classes.
A collection, as its name implied, is simply a container object that holds a collection of
objects. Each item in a collection is called an element. A framework, by definition, is a set
of interfaces that force you to adopt some design practices. A well-designed framework can
improve your productivity and provide ease of maintenance.
The collection framework provides a unified interface to store, retrieve and manipulate the
elements of a collection, regardless of the underlying actual implementation. This allows
the programmers to program at the interface specification, instead of the actual
implementation.
2 64
Java Collections Framework

The Java Collection Framework (JCF) is a set of classes and interfaces implementing
commonly reusable data structures.
The JCF (package [Link]) provides
▶ A set of interfaces defining functionalities;
▶ Abstract classes for shared code aggregation;
▶ Implementation classes implementing functionalities;
▶ Algorithms (such as sorting and searching).

3 64
Key Concepts

Resizable Array
Linked List
Balanced Tree
Hash Table

4 64
Resizable Array ∼O(n)

5 64
Linked List ∼O(n)

6 64
Balanced Tree ∼O(log(n))

A binary tree is balanced if, for each node it holds that, the number of inner nodes in the left
subtree and the number of inner nodes in the right subtree differ by at most 1.
A binary tree is balanced if for any two leaves the difference of the depth is at most 1.

7 64
Hash Table ∼O(1)

8 64
Interfaces

9 64
Implementations

10 64
Internals

11 64
Iterable and Iterator Interfaces

The Iterable interface ([Link]) is the root interface of the Java collection
framework. Iterable, literally, means that "can be iterated".
Technically, it means that an Iterator can be returned. Iterable objects (objects
implementing the iterable interface) can be used with the for-each loop.

1 p u b l i c i n t e r f a c e I t e r a b l e <T> {
I t e r a t o r <T> i t e r a t o r ( ) ;
3 }

5 L i s t < O b j e c t > l i s t = new A r r a y L i s t < O b j e c t > ( ) ;

for ( Object obj : l i s t ) {
7 / / do s o m e t h i n g ;
}

12 64
Iterable and Iterator Interfaces

The Iterator interface extracts the traversal behaviour of a collection into a separate object
called an iterator. This Iterator object can then be used to traverse through all the elements
of the associated collection.
[Link]

p u b l i c i n t e r f a c e I t e r a t o r <T> {
2 b o o l e a n hasNext ( ) ;
T next ( ) ;
4 v o i d remove ( ) ;
}
6
A r r a y L i s t < O b j e c t > l i s t = new A r r a y L i s t < O b j e c t > ( ) ;
8 f o r ( I t e r a t o r < Object > i t = l i s t . i t e r a t o r ( ) ; i t . hasNext ( ) ; ) {
Object obj = i t . next ( ) ;
10 / / do s o m e t h i n g
}

13 64
Collections Interface

The hierarchy of the interfaces and the commonly-used implementation classes in the
Collections Framework is as shown below:

14 64
Collections Interface

Group of elements (references to objects).

It is not specified whether they are

▶ Ordered / not ordered;
▶ Duplicated / not duplicated.

Common constructors
▶ Collection();
▶ Collection(Collection c).

15 64
Collection Interface

/ / I n t e r f a c e j a v a . u t i l . C o l l e c t i o n <E>
2 / / Basic Operations
a b s t r a c t i n t size ( ) ; / / R e t u r n s t h e number o f e l e m e n t s
4 a b s t r a c t b o o l e a n isEmpty ( ) ; / / R e t u r n s t r u e i f t h e r e i s no e l e m e n t

6 / / " I n d i v i d u a l Element " Operations

a b s t r a c t b o o l e a n add ( E e l e m e n t ) ; / / Add t h e g i v e n e l e m e n t
8 a b s t r a c t b o o l e a n remove ( O b j e c t e l e m e n t ) ;
a b s t r a c t b o o l e a n contains ( O b j e c t e l e m e n t ) ;
10
/ / " Bulk " ( m u t a b l e ) O p e r a t i o n s
12 a b s t r a c t v o i d clear ( ) ; / / Removes a l l t h e e l e m e n t s
a b s t r a c t b o o l e a n addAll ( C o l l e c t i o n < ? e x t e n d s E> c ) ;
14 a b s t r a c t b o o l e a n removeAll ( C o l l e c t i o n <? > c ) ;
a b s t r a c t b o o l e a n retainAll ( C o l l e c t i o n <? > c ) ;
16
/ / Array Operations
18 a b s t r a c t O b j e c t [ ] toArray ( ) ; / / C o n v e r t t o an O b j e c t a r r a y

16 64
Presentation Outline

1 Java Collection Framework

2 Lists

3 Sets

4 Queues

5 Maps

6 Collections and Iterators

7 Algorithms

17 64
List Interface

A List<E> models a resizable linear array, which supports numerical indexed access, with
index starts from 0. Elements in a list can be retrieved and inserted at a specific index
position based on an int index. It can contain duplicate elements. It can contain null
elements. You can search a list, iterate through its elements, and perform operations on a
selected range of values in the list.

18 64
List additional methods

/ / Methods i n h e r i t e d from I n t e r f a c e j a v a . l a n g . I t e r a b l e <E>

2 a b s t r a c t I t e r a t o r <E> iterator ( ) ;

4 / / Methods i n h e r i t e d from I n t e r f a c e j a v a . u t i l . C o l l e c t i o n <E>

a b s t r a c t i n t size ( ) ;
6 a b s t r a c t b o o l e a n isEmpty ( ) ;
a b s t r a c t b o o l e a n add ( E e l e m e n t ) ;
8 a b s t r a c t b o o l e a n remove ( O b j e c t o b j ) ;
a b s t r a c t b o o l e a n contains ( O b j e c t o b j ) ;
10 a b s t r a c t v o i d clear ( ) ;

12 / / I n t e r f a c e j a v a . u t i l . L i s t <E>
/ / Operations at a s p e c i f i e d index p o s i t i o n
14 a b s t r a c t v o i d add ( i n t i n d e x , E e l e m e n t ) ; // add a t i n d e x
a b s t r a c t E set ( i n t i n d e x , E e l e m e n t ) ; // replace at index
16 a b s t r a c t E get ( i n t i n d e x ) ; // r e t r i e v e a t i n d e x w i t h o u t remove
a b s t r a c t E remove ( i n t i n d e x ) ; // remove a t i n d e x
18 a b s t r a c t i n t indexOf ( O b j e c t o b j ) ;

19 64
ArrayList

ArrayList is an implementation of the List interface. The list automatically grows if elements
exceed initial size. ArrayList has a numeric index.
Elements are accessed by index.
Elements can be inserted based on index.
Elements can be overwritten.

L i s t < I n t e g e r > p a r t L i s t = new A r r a y L i s t < > ( ) ;

2 p a r t L i s t . add ( new I n t e g e r ( 1 1 1 1 ) ) ;
p a r t L i s t . add ( new I n t e g e r ( 2 2 2 2 ) ) ;
4 p a r t L i s t . add ( new I n t e g e r ( 3 3 3 3 ) ) ;
p a r t L i s t . add ( new I n t e g e r ( 4 4 4 4 ) ) ; / / A r r a y L i s t a u t o grows
6
System . o u t . p r i n t l n ( " F i r s t P a r t : " + p a r t L i s t . g e t ( 0 ) ) ; / / F i r s t item
8 p a r t L i s t . add ( 0 , new I n t e g e r ( 5 5 5 5 ) ) ; / / I n s e r t an i t e m by i n d e x

20 64
Autoboxing and Unboxing

Autoboxing and Unboxing simplifies the syntax. It produces cleaner, easier-to-read code.

p u b l i c c l a s s AutoBox {
2 p u b l i c s t a t i c v o i d main ( S t r i n g [ ] a r g s ) {
I n t e g e r i n t O b j e c t = new I n t e g e r ( 1 ) ;
4 int intPrimitive = 2;

6 Integer tempInteger ;
int tempPrimitive ;
8
t e m p I n t e g e r = new I n t e g e r ( i n t P r i m i t i v e ) ;
10 tempPrimitive = intObject . intValue ( ) ;

12 tempInteger = i n t P r i m i t i v e ; / / Auto box

tempPrimitive = intObject ; / / Auto unbox
14 }
}

21 64
Iterate over an ArrayList

1 public class GenericArrayList {

p u b l i c s t a t i c v o i d main ( S t r i n g [ ] a r g s ) {
3 L i s t < I n t e g e r > p a r t L i s t = new A r r a y L i s t < > ( ) ;
p a r t L i s t . add ( new I n t e g e r ( 1 1 1 1 ) ) ;
5 p a r t L i s t . add ( new I n t e g e r ( 2 2 2 2 ) ) ;
p a r t L i s t . add ( new I n t e g e r ( 3 3 3 3 ) ) ;
7
I t e r a t o r < Integer > elements = p a r t L i s t . i t e r a t o r ( ) ;
9 while ( elements . hasNext ( ) ) {
I n t e g e r partNumberObject = elements . next ( ) ;
11 i n t partNumber = p a r t N u m b e r O b j e c t . i n t V a l u e ( ) ;

13 System . o u t . p r i n t l n ( " P a r t number : " + partNumber ) ;

}
15 }
}

22 64
List Initialization

/ ∗ Plain , simple , long ∗ /

2 L i s t < I n t e g e r > l i s t = new A r r a y L i s t < I n t e g e r > ( ) ;
l i s t . add ( 1 4 ) ;
4 l i s t . add ( 7 3 ) ;
l i s t . add ( 1 8 ) ;
6 ...

8 / ∗ More compact v e r s i o n ( m u t a b l e ) ∗ /
L i s t < I n t e g e r > l i s t = new A r r a y L i s t < > ( A r r a y s . a s L i s t ( 1 4 , 7 3 , 1 8 ) ) ;
10 L i s t < I n t e g e r > l i s t = new A r r a y L i s t < > ( L i s t . o f ( 1 4 , 7 3 , 1 8 ) ) ;

12 / ∗ More compact v e r s i o n ( immutable ) ∗ /

List < Integer > l i s t = L i s t . of (14 , 73 , 18) ;

23 64
List Implementations

Decoupling references from actual

objects allows to change
implementation (and related 1 List<Car> g a r a g e = new LinkedList<Car > ( ) ;
/ / List<Car> g a r a g e = new ArrayList<Car > ( ) ;
performance!) by changing a single 3
line of code! garage . add ( new Car ( ) ) ;
5 garage . add ( new SelfDrivingCar ( ) ) ;
garage . add ( new SelfDrivingCar ( ) ) ;
ArrayList implements List 7 garage . add ( new Car ( ) ) ;
▶ get(index) -> Constant time
9 f o r ( Car c a r : g a r a g e ) {
▶ add(index, obj) -> Linear time c a r . turnOn ( ) ;
11 }
LinkedList implements List, Queue
▶ get(index) -> Linear time
▶ add(index, obj) -> Linear time (but
more lightweight)

24 64
List Implementations

25 64
List Implementations

26 64
Presentation Outline

1 Java Collection Framework

2 Lists

3 Sets

4 Queues

5 Maps

6 Collections and Iterators

7 Algorithms

27 64
Set Interface

The Set<E> interface models a mathematical set, where no duplicate elements are allowed
(e.g., playing cards). It may contain a single null element.
Contains no methods other than those inherited from Collection.

28 64
Set Interface

The main difference between List and Set in Java is that List is an ordered collection, which
allows duplicates, whereas Set is an unordered collection, which does not allow duplicates.

A Set is an interface that contains only unique elements.

A Set has no index.
Duplicate elements are not allowed.
You can iterate through elements to access them.
TreeSet provides sorted implementation.

29 64
Set Implementations

HashSet implements Set

▶ Hash tables as internal data structure (fast!)
▶ Insertion order not preserved

LinkedHashSet extends HashSet

▶ Insertion order preserved

TreeSet implements SortedSet (an extension of Set)

▶ R-B trees as internal data structure (provide ordering)
▶ User definable internal ordering TreeSet(Comparator c)
▶ Slow when compared to hash-based implementations

30 64
Set Example

1 A r r a y L i s t < S t r i n g > l i s t = new A r r a y L i s t < > (

L i s t . o f ( " N i c o l a " , " Agata " , " M a r z i a " , " Agata " )
3 );
System . o u t . p r i n t l n ( l i s t ) ;
5 / / [ N i c o l a , Agata , Marzia , Agata ]

7 Set<String> hashSet = new HashSet<>(list);

System . o u t . p r i n t l n ( h a s h S e t ) ;
9 / / [ Marzia , N i c o l a , Agata ]

11 Set<String> linkedHashSet = new LinkedHashSet<>(list);

System . o u t . p r i n t l n ( l i n k e d H a s h S e t ) ;
13 / / [ N i c o l a , Agata , M a r z i a ]

15 Set<String> treeSet = new TreeSet<>(list);

System . o u t . p r i n t l n ( t r e e S e t ) ;
17 / / [ Agata , Marzia , N i c o l a ]

31 64
Set Example

1 p u b l i c c l a s s SetExample {
p u b l i c s t a t i c v o i d main ( S t r i n g [ ] a r g s ) {
3 S e t s e t = new T r e e S e t < > ( ) ;
s e t . add ( " one " ) ;
5 s e t . add ( " two " ) ;
s e t . add ( " t h r e e " ) ;
7 s e t . add ( " t h r e e " ) ; / / n o t added , o n l y u n i q u e

9 f o r ( S t r i n g item : s e t ) {
System . o u t . p r i n t l n ( " I t e m : " + i t e m ) ;
11 }
}
13 }

32 64
TreeSet Internal Ordering

Depending on the constructor used, SortedSet implementations can use different orderings.

TreeSet()
▶ Natural ascending ordering
▶ Elements must implement the Comparable Interface.

TreeSet(Comparator c)
▶ Ordering is defined by the Comparator c.

33 64
Presentation Outline

1 Java Collection Framework

2 Lists

3 Sets

4 Queues

5 Maps

6 Collections and Iterators

7 Algorithms

34 64
Queue Interface

A queue is a collection whose elements are added and removed in a specific order, typically
in a first-in-first-out (FIFO) manner. A deque (pronounced "deck") is a double-ended queue
that elements can be inserted and removed at both ends (head and tail) of the queue.

35 64
Queue additional methods

1 / / I n t e r f a c e j a v a . u t i l . Queue <E>
/ / I n s e r t i o n a t t h e end o f t h e queue
3 a b s t r a c t b o o l e a n add ( E e ) ; / / throws IllegalStateException if no space is currently available
a b s t r a c t b o o l e a n offer ( E e ) ; / / returns true if the element was added to this queue, else false
5
/ / E x t r a c t e l e m e n t a t t h e head o f t h e queue
7 a b s t r a c t E remove ( ) ; / / throws NoSuchElementException if this queue is empty
a b s t r a c t E poll ( ) ; / / returns the head of this queue, or null if this queue is empty
9
/ / I n s p e c t i o n ( r e t r i e v e t h e e l e m e n t a t t h e head , b u t d o e s n o t remove )
11 a b s t r a c t E element ( ) ; / / throws NoSuchElementException if this queue is empty
a b s t r a c t E peek ( ) ; / / returns the head of this queue, or null if this queue is empty

36 64
Queue Implementations

LinkedList implements List, Queue

▶ Insertion order conserved.
▶ Head is the first element of the list
▶ FIFO (First-In-First-Out) policy

PriorityQueue implements Queue

▶ Internal ordering policy. Default is natural ascending ordering, if defined. Can be modified by
implementing the Comparable interface.

37 64
Queue Example

A r r a y L i s t < I n t e g e r > l i s t = new A r r a y L i s t < > ( L i s t . o f ( 3 , 1 , 2 ) ) ;

2 Queue < I n t e g e r > f i f o = new LinkedList< I n t e g e r > ( l i s t ) ;
Queue < I n t e g e r > pqueue = new PriorityQueue< I n t e g e r > ( l i s t ) ;
4
System . o u t . p r i n t l n ( f i f o . peek ( ) ) ; // 3
6 System . o u t . p r i n t l n ( pqueue . peek ( ) ) ; // 1

38 64
PriorityQueue or TreeSet?

Similarities
▶ Both provide O(log(N)) time complexity for adding, removing, and searching elements.
▶ Both provide elements in sorted order.

Differences
▶ TreeSet is a Set and doesn’t allow a duplicate element, while PriorityQueue is a queue and
doesn’t have such restriction.
▶ Another key difference between TreeSet and PriorityQueue is iteration order, though you can
access elements from the head in a sorted order e.g. head always give you lowest or highest
priority element depending upon your Comparable or Comparator implementation but
iterator returned by PriorityQueue doesn’t provide any ordering guarantee.

39 64
Presentation Outline

1 Java Collection Framework

2 Lists

3 Sets

4 Queues

5 Maps

6 Collections and Iterators

7 Algorithms

40 64
Map Interface

A map is a collection of key-value pairs (e.g., name-address, name-phone, isbn-title,

word-count). Each key maps to one and only value. Duplicate keys are not allowed, but
duplicate values are allowed. Maps are similar to linear arrays, except that an array uses an
integer key to index and access its elements; whereas a map uses any arbitrary key (such
as Strings or any objects).

41 64
Map Interface

/ / I n t e r f a c e j a v a . u t i l . Map<K , V>
2 a b s t r a c t i n t size ( ) ; / / Returns the number of key-value pairs
a b s t r a c t b o o l e a n isEmpty ( ) ; / / Returns true if this map contain no key-value pair
4
a b s t r a c t V get ( O b j e c t key ) ; / / Returns the value of the specified key
6 a b s t r a c t V put ( K key , V v a l u e ) ; / / Associates the specified value with the specified key

8 a b s t r a c t b o o l e a n containsKey ( O b j e c t key ) ; / / Returns true if this map has specified key

a b s t r a c t b o o l e a n containsValue ( O b j e c t v a l u e ) ; / / Returns true if this map has specified value
10
a b s t r a c t v o i d clear ( ) ; / / Removes all key-value pairs
12 a b s t r a c t v o i d V remove ( O b j e c t key ) ; / / Removes the specified key

42 64
HashMap

Get/set takes constant time (without considering collisions).

Automatic re-allocation when load factor reached.

Constructor optional arguments

▶ load factor (default = .75)
▶ initial capacity (default = 16)

43 64
Map Example I

Map< S t r i n g , I n t e g e r > map = new HashMap < > ( ) ;

2 map . p u t ( " Agata " , 2 ) ;
map . p u t ( " M a r z i a " , 3 ) ;
4 map . p u t ( " Agata " , 4 ) ;
map . p u t ( " N i c o l a " , 1 ) ;
6
/ ∗ More compact v e r s i o n ∗ /
8 Map< S t r i n g , I n t e g e r > map = new HashMap < > (
Map . o f ( " Agata " , 2 , " M a r z i a " , 3 , " Agata " , 4 , " N i c o l a " , 1 )
10 );

12 / ∗ Immutable v e r s i o n ∗ /
Map< S t r i n g , I n t e g e r > map =
14 Map . o f ( " Agata " , 2 , " M a r z i a " , 3 , " Agata " , 4 , " N i c o l a " , 1 ) ;

44 64
Map Implementations

HashMap implements Map

▶ Hash tables as internal data
Map< I n t e g e r , S t r i n g > s r c ;
structure (fast!). 2 s r c = new HashMap < > ( ) ;
s r c . put ( 7 7 , " N i c o l a " ) ;
▶ Insertion order not preserved. 4 s r c . put ( 1 7 , " M a r z i a " ) ;
s r c . put ( 2 2 , " Agata " ) ;
6 System . o u t . p r i n t l n ( s r c ) ;
LinkedHashMap extends HashMap
8 / / { 1 7 = Marzia , 22= Agata , 77= N i c o l a }
▶ Insertion order preserved. s r c = new LinkedHashMap < > ( ) ;
10 s r c . put ( 7 7 , " N i c o l a " ) ;
s r c . put ( 1 7 , " M a r z i a " ) ;
TreeMap implements SortedMap 12 s r c . put ( 2 2 , " Agata " ) ;
System . o u t . p r i n t l n ( s r c ) ;
▶ R-B trees as internal data structure. 14 / / { 7 7 = N i c o l a , 17= Marzia , 22= Agata }

▶ User definable internal ordering. 16 s r c = new TreeMap < > ( ) ;

s r c . put ( 7 7 , " N i c o l a " ) ;
▶ Slow when compared to hash-based 18 s r c . put ( 1 7 , " M a r z i a " ) ;
s r c . put ( 2 2 , " Agata " ) ;
implementations. 20 System . o u t . p r i n t l n ( s r c ) ;
/ / { 1 7 = Marzia , 22= Agata , 77= N i c o l a }

45 64
Map Example II

1 Map< S t r i n g , I n t e g e r > map = new HashMap< S t r i n g , I n t e g e r > ( ) ;

...
3 / / L o o p i n g k e y s and a c c e s s i n g v a l u e s
S e t < S t r i n g > k e y s = map . k e y S e t ( ) ;
5 f o r ( S t r i n g key : k e y s ) {
System . o u t . p r i n t l n ( key + " −> " + map . g e t ( key ) ) ;
7 }

9 / / C o n t a i n s key
i f ( map . c o n t a i n s K e y ( key ) ) {
11 System . o u t . p r i n t l n ( map . g e t ( key ) ) ;
}
13
/ / Looping v a l u e s
15 L i s t < I n t e g e r > v a l u e s = map . v a l u e s ( ) ;
for ( int value : values ) {
17 System . o u t . p r i n t l n ( v a l u e ) ;
}

46 64
Presentation Outline

1 Java Collection Framework

2 Lists

3 Sets

4 Queues

5 Maps

6 Collections and Iterators

7 Algorithms

47 64
Collections and Iterators

It is unsafe to modify (adding or removing elements) a Collection while iterating over it!.

L i s t < Double > l i s t = new L i n k e d L i s t < Double > (

2 L i s t . of ( 1 0 . 8 , 11.1 , 13.2 , 3 0 . 2 )
);
4
i n t count = 0 ;
6 f o r ( double i : l i s t ) {
i f ( c o u n t == 1 ) {
8 l i s t . remove ( c o u n t ) ;
}
10
i f ( c o u n t == 2 ) {
12 l i s t . add ( 2 2 . 3 ) ;
}
14
count ++;
16 } / / Run− t i m e e r r o r ! We modify t h e l i s t w h i l e i t e r a t i n g

48 64
Iterator and ListIterator Interfaces

Interface Iterator provides a Interface ListIterator provides a transparent

transparent means for cycling means for cycling through all elements of a
through all elements of a Collection Collection (forward and backward) and
(forward only) and removing removing and adding elements.
elements.

b o o l e a n hasNext ( )
2 b o o l e a n hasPrevious ( )
b o o l e a n hasNext()
O b j e c t next ( )
2 O b j e c t next()
4 O b j e c t previous ( )
v o i d remove()
v o i d add ( )
6 v o i d set ( )
v o i d remove ( )
8 i n t nextIndex ( )
i n t previousIndex ( )

49 64
Iterator and ListIterator Interfaces

L i s t < Double > l i s t = new L i n k e d L i s t < Double > (

2 L i s t . of ( 1 0 . 8 , 11.1 , 13.2 , 3 0 . 2 )
);
4
i n t count = 0 ;
6 f o r (Iterator<Double> it = [Link](); [Link]();) {
double d = i t . next ( ) ;
8
i f ( c o u n t == 1 ) {
10 i t . remove ( ) ;
}
12
count ++;
14 }

50 64
Iterator and ListIterator Interfaces

L i s t < Double > l i s t = new L i n k e d L i s t < Double > (

2 L i s t . of ( 1 0 . 8 , 11.1 , 13.2 , 3 0 . 2 )
);
4
i n t count = 0 ;
6 f o r (Iterator<Double> it = [Link](); [Link]();) {
double d = i t . next ( ) ;
8
i f ( c o u n t == 1 ) {
10 i t . remove ( ) ;
}
12
i f ( c o u n t == 2 ) {
14 i t . add ( 2 2 . 3 ) ;
}
16
count ++;
18 }

51 64
Iterations and Iterators

L i s t < Person > p e r s o n L i s t = new A r r a y L i s t < Per so n > ( ) ;

2
/∗ C style ∗/
4 f o r ( i n t i = 0 ; i < p e r s o n L i s t . s i z e ( ) ; i ++) {
System . o u t . p r i n t l n ( p e r s o n L i s t . g e t ( i ) )
6 }

8 / ∗ f o r − each s t y l e ∗ /
f o r ( Person person : p e r s o n L i s t ) {
10 System . o u t . p r i n t l n ( p e r s o n ) ;
}
12
/∗ iterator style ∗/
14 f o r ( I t e r a t o r < Person > i t = p e r s o n L i s t . i t e r a t o r ( ) ; i t . h a s N e x t ( ) ; ) {
Person person = i t . next ( ) ;
16 System . o u t . p r i n t l n ( p e r s o n ) ;
}
18
/ ∗ while s t y l e ∗ /
20 Iterator it = personList . iterator () ;
while ( i t . hasNext ( ) ) {
22 System . o u t . p r i n t l n ( ( P e r s o n ) i t . n e x t ( ) ) ;
}

52 64
Presentation Outline

1 Java Collection Framework

2 Lists

3 Sets

4 Queues

5 Maps

6 Collections and Iterators

7 Algorithms
Comparable and Comparator

53 64
[Link]

This class contains various methods for manipulating arrays such as sorting, searching,
filling, printing or being viewed as an array.

1 sort () // merge s o r t i m p l e m e n t a t i o n , n l o g ( n )
binarySearch ( ) // requires ordered c o l l e c t i o n
3 shuffle () // unsort
reverse () // requires ordered c o l l e c t i o n
5 rotate () // r o t a t e elements of a given distance
min ( ) // min i n a c o l l e c t i o n
7 max ( ) // max i n a c o l l e c t i o n

54 64
Algorithms

1 A r r a y L i s t < S t r i n g > l i s t = new A r r a y L i s t < S t r i n g > (

L i s t . o f ( " N i c o l a " , " Agata " , " M a r z i a " , " Agata " )
3 );

5 Collections . sort ( l i s t ) ;
System . o u t . p r i n t l n ( l i s t ) ; / / [ Agata , Agata , Marzia , N i c o l a ]
7
Collections . reverse ( l i s t ) ;
9 System . o u t . p r i n t l n ( l i s t ) ; / / [ N i c o l a , Marzia , Agata , Agata ]

11 Collections . shuffle ( l i s t ) ;
System . o u t . p r i n t l n ( l i s t ) ; / / [ Marzia , Agata , Agata , N i c o l a ]
13
Collections . rotate ( l i s t , 1) ;
15 System . o u t . p r i n t l n ( l i s t ) ; / / [ N i c o l a , Marzia , Agata , Agata ]

55 64
Algorithms

1 A r r a y L i s t < S t r i n g > l i s t = new A r r a y L i s t < S t r i n g > (

L i s t . o f ( " N i c o l a " , " Agata " , " M a r z i a " , " Agata " )
3 );

5 Collections . sort ( l i s t ) ;
System . o u t . p r i n t l n ( i s t ) ; / / [ Agata , Agata , Marzia , N i c o l a ]
7
Collections . binarySearch ( l i s t , " Nicola " ) ; // 3
9 C o l l e c t i o n s . b i n a r y S e a r c h ( l i s t , " Zuck " ) ) ; / / −5

Using binarySearch, the list must be sorted. If it is not sorted, the results are undefined.

56 64
Presentation Outline

1 Java Collection Framework

2 Lists

3 Sets

4 Queues

5 Maps

6 Collections and Iterators

7 Algorithms
Comparable and Comparator

57 64
Sorting Collections of Objects

For sorting collections of objects, the Comparable or Comparator interface must be

implemented for making objects comparable to each other.
The Comparable and Comparator Interface are implemented by default in common types
in packages [Link] and [Link].

1 p u b l i c interface Comparable<T> {
p u b l i c i n t compareTo ( T o b j ) ;
3 }

5 p u b l i c interface Comparator<T> {
p u b l i c i n t compare ( T l e f t , T r i g h t ) ;
7 }

58 64
The Comparable Interface

A collection of T can be sorted if T implements Comparable. The compareTo() method

compares the object with the object passed as a parameter. Return value must be:
< 0 if this object precedes obj
== 0 if this object has the same position as obj
> 0 if this object follows obj

c l a s s P e r s o n implements Comparable<Person> {
2 protected String firstname ;
protected S t r i n g lastname ;
4 p r o t e c t e d i n t age ;

6 p u b l i c i n t compareTo(Person person) {
/ / o r d e r by l a s t n a m e
8 r e t u r n l a s t n a m e . compareTo ( p e r s o n . l a s t n a m e ) ;
}
10 }

59 64
The Comparable Interface

c l a s s P e r s o n implements Comparable<Person> {
2 protected String firstname ;
protected S t r i n g lastname ;
4 p r o t e c t e d i n t age ;

6 p u b l i c i n t compareTo(Person person) {
/ / o r d e r by l a s t n a m e
8 compare = l a s t n a m e . compareTo ( p e r s o n . l a s t n a m e ) ;
i f ( compare == 0 ) {
10 / / i f l a s t n a m e s a r e e q u a l , o r d e r by f i r s t n a m e
compare = f i r s t n a m e . compareTo ( p e r s o n . f i r s t n a m e ) ;
12 }

14 r e t u r n compare ;
}
16 }

60 64
The Comparator Interface

We can also sort objects using a Comparator<E>.

Given a class already implementing Comparable<E>, we can sort it using alternative orders
using a Comparator<E>.

p u b l i c c l a s s SortByAge i m p l e m e n t s Comparator < Person > {

2 @Override
p u b l i c i n t compare ( P e r s o n l e f t , P e r s o n r i g h t ) {
4 r e t u r n l e f t . age − r i g h t . age ;
}
6 }

8 c l a s s P e r s o n i m p l e m e n t s Comparable < Person > {

protected String firstname ;
10 protected S t r i n g lastname ;
p r o t e c t e d i n t age ;
12
p u b l i c i n t compareTo ( P e r s o n p e r s o n ) {
14 r e t u r n l a s t n a m e . compareTo ( p e r s o n . l a s t n a m e ) ;
}
16 }

61 64
The Comparator Interface

p u b l i c s t a t i c v o i d main ( S t r i n g [ ] a r g s ) {
2 A r r a y L i s t < Person > l i s t = new A r r a y L i s t < Per so n > ( ) ;
l i s t . add ( new P e r s o n ( " Mario " , " R o s s i " , 6 8 ) ) ;
4 l i s t . add ( new P e r s o n ( " Luca " , " B i a n c h i " , 2 8 ) ) ;
l i s t . add ( new P e r s o n ( " C a r l o " , " A n t o n i " , 3 4 ) ) ;
6
/ / N a t u r a l o r d e r i n g ( Comparable )
8 Collections . sort ( l i s t ) ;

10 / / S p e c i a l o r d e r i n g ( Comparator )
C o l l e c t i o n s . s o r t ( l i s t , new S ortBy Age ( ) ) ;
12
/ / Comparator anonymous c l a s s
14 C o l l e c t i o n s . s o r t ( l i s t , new Comparator < Pers on > ( ) {
@Override
16 p u b l i c i n t compare ( P e r s o n l e f t , P e r s o n r i g h t ) {
r e t u r n l e f t . age − r i g h t . age ;
18 }
}) ;
20 }

62 64
Comparator vs Comparable

The Comparable interface is a good choice to use for defining the default ordering, or in
other words, if it’s the main way of comparing objects.

So why use a Comparator if we already have Comparable? There are several reasons why:
▶ Sometimes we can’t modify the source code of the class whose objects we want to sort, thus
making the use of Comparable impossible.
▶ Using Comparators allows us to avoid adding additional code to our domain classes.
▶ We can define multiple different comparison strategies, which isn’t possible when using
Comparable.

63 64
References

Allen B. Downey, Chris Mayfield, Think Java, (2016).

Graham Mitchell, Learn Java the Hard Way, 2nd Edition, (2016).
Cay S. Horstmann, Big Java - Early Objects, 7e-Wiley, (2019).
James Gosling, Bill Joy, Guy Steele, Gilad Bracha, Alex Buckley, The Java Language Specification -
Java SE 8 Edition, (2015).
Martin Fowler, UML Distilled - A Brief Guide To The Standard Object Modeling Language,
(2004).
Richard Warburton, Object-Oriented vs. Functional Programming - Bridging the Divide
Between Opposing Paradigms, (2016).
Naftalin, Maurice Wadler, Philip Java Generics and Collections, O’Reilly Media, (2009).
Eric Freeman, Elisabeth Robson Head First Design Patterns - Building Extensible and
Maintainable Object, Oriented Software-O’Reilly Media, (2020).
Alexander Shvets Dive Into Design Patterns, (2019).

64 / 64
Thank You!