The Java Collections Framework is designed to support numerous collections in a hierarchical fashion. It is essentially made up of interfaces, implementations, and algorithms.
Collections are objects that group multiple elements and store, retrieve, and manipulate those elements. The Collection
interface is at the root of the collection hierarchy. Subinterfaces of Collection
include List, Queue
, and Set
. Table 15-1 shows these interfaces and whether they are ordered or allow duplicates. The Map
interface is also included in the table, as it is part of the framework.
Table 15-2 lists commonly used collection type implementations, their interfaces, and whether or not they are ordered, sorted, and/or contain duplicates.
Implementations | Interface | Ordered | Sorted | Dupes | Notes |
|
| Index | No | Yes | Fast resizable array |
|
| Index | No | Yes | Doubly linked list |
|
| Index | No | Yes | Legacy, synchronized |
|
| No | No | No | Key/value pairs |
|
| No | No | No | Legacy, synchronized |
|
| Insertion, last access | No | No | Linked list/hash table |
|
| Balanced | Yes | No | Red-black tree map |
|
| Priority | Yes | Yes | Heap implementation |
|
| No | No | No | Fast access set |
|
| Insertion | No | No | Linked list/hash set |
|
| Sorted | Yes | No | Red-black tree set |
The subinterfaces of the Collection
interface provide several valuable method signatures, as shown in Table 15-3.
Method | List params | Set params | Map params | Returns |
| index, element | element | n/a |
|
| Object | Object | n/a |
|
| n/a | n/a | key |
|
| n/a | n/a | value |
|
| index | n/a | key |
|
| Object | n/a | n/a |
|
| none | none | n/a |
|
| n/a | n/a | none |
|
| n/a | n/a | key, value |
|
| index or Object | Object | key |
|
| none | none | none |
|
Collection.stream()
returns a sequential Stream
with the context collection as its source. Collection.parallelStream()
returns a parallel Stream
with the context collection as its source.
The Collections
class, not to be confused with the Collection
interface, contains several valuable static methods (i.e., algorithms). These methods can be invoked on a variety of collection types. Table 15-4 shows commonly used Collection
class methods, their acceptable parameters, and return values.
Method | Parameters | Returns |
| Collection <? super T>, T… |
|
| Collection, [Comparator] |
|
| Collection, [Comparator] |
|
| Collection, Collection |
|
| Collection, Object |
|
| Deque |
|
| List |
|
| List |
|
| List destination, List source |
|
| List, int distance |
|
| List, int position, int position |
|
| List, Object |
|
| List, Object |
|
| List, Object, [Comparator] |
|
| List, Object oldValue, Object newValue |
|
| Map |
|
See Chapter 16 for more information on typed parameters (i.e., <T>
).
Algorithms and data structures are optimized for different reasons—some for random element access, or insertion/deletion, others for keeping things in order. Depending on your needs, you may have to switch algorithms and structures.
Common collection algorithms, their types, and average time efficiencies are shown in Table 15-5.
Algorithms | Concrete type | Time |
|
| 0 (1) |
|
| 0 (n) |
|
| 0 (n) |
|
| 0 (1) |
|
| 0 (1) |
|
| 0 (1) |
|
| 0 (1) |
|
| 0 (n) |
|
| 0 (n) |
|
| 0 (1) |
|
| 0 (log n) |
|
| 0 (log n) |
|
| 0 (log n) |
The Big O notation is used to indicate time efficiencies, where n is the number of elements; see Table 15-6.
Several methods in the Collections
class assume that the objects in the collection are comparable. If there is no natural ordering, a helper class can implement the Comparator
functional interface to specify how the objects are to be ordered:
public
class
Crayon
{
private
String
color
;
public
Crayon
(
String
color
)
{
this
.
color
=
color
;
}
public
String
getColor
()
{
return
color
;
}
public
void
setColor
(
String
color
)
{
this
.
color
=
color
;
}
public
String
toString
()
{
return
this
.
color
;
}
}
import
java.util.Comparator
;
public
class
CrayonSort
implements
Comparator
<
Crayon
>
{
@Override
public
int
compare
(
Crayon
c1
,
Crayon
c2
)
{
return
c1
.
getColor
().
compareTo
(
c2
.
getColor
());
}
}
import
java.util.ArrayList
;
import
java.util.Collections
;
public
class
CrayonApp
{
public
static
void
main
(
String
[]
args
)
{
Crayon
crayon1
=
new
Crayon
(
"yellow"
);
Crayon
crayon2
=
new
Crayon
(
"green"
);
Crayon
crayon3
=
new
Crayon
(
"red"
);
Crayon
crayon4
=
new
Crayon
(
"blue"
);
Crayon
crayon5
=
new
Crayon
(
"purple"
);
ArrayList
<
Crayon
>
cList
=
new
ArrayList
<>();
cList
.
add
(
crayon1
);
cList
.
add
(
crayon2
);
cList
.
add
(
crayon3
);
cList
.
add
(
crayon4
);
cList
.
add
(
crayon5
);
System
.
out
.
println
(
"Unsorted: "
+
cList
);
CrayonSort
cSort
=
new
CrayonSort
();
// Here
Collections
.
sort
(
cList
,
cSort
);
System
.
out
.
println
(
"Sorted: "
+
cList
);
}
}
$
Unsorted:
[
yellow
,
green
,
red
,
blue
,
purple
]
$
Sorted:
[
blue
,
green
,
purple
,
red
,
yellow
]
The CrayonSort
class implemented the Comparator
interface which was used by the cSort
instance. Optionally, an anonymous inner class could have been created to avoid the work of creating the seperate CrayonSort
class:
Comparator
<
Crayon
>
cSort
=
new
Comparator
<
Crayon
>()
{
public
int
compare
(
Crayon
c1
,
Crayon
c2
)
{
return
c1
.
getColor
().
compareTo
(
c2
.
getColor
());
}
};
Since Comparator
is a functional interface, a lambda expression could have been used to make the code more readable:
Comparator
<
Crayon
>
cSort
=
(
Crayon
c1
,
Crayon
c2
)
->
c1
.
getColor
().
compareTo
(
c2
.
getColor
());
Class names do not need to be explicitly stated in the argument list, as the lambda expressions have knowledge of the target types. That is, notice (c1, c2)
versus (Crayon c1, Crayon c2)
:
// Example 1
Comparator
<
Crayon
>
cSort
=
(
c1
,
c2
)
->
c1
.
getColor
().
compareTo
(
c2
.
getColor
());
Collections
.
sort
(
cList
,
cSort
);
// Example 2
Collections
.
sort
(
cList
,
(
c1
,
c2
)
->
c1
.
getColor
().
compareTo
(
c2
.
getColor
()));