Skip to main content
Logo image

Problem Solving with Algorithms and Data Structures using Java: The Interactive Edition

Section 1.9 Collections and Wrapper Classes

While fixed-length arrays are very efficient, we will need array-like containers that allow us to easily add and delete elements. Java provides a large number of collections, some of which implement the data structures we will be looking at in this book. (We’ll be implementing our own versions of these data structures rather than relying on the ones that Java gives us.)

Subsection 1.9.1 The ArrayList Class

The primary collection we’ll be using is the ArrayList. It’s not one of the built-in data types, so you have to explicitly import it:
jshell> import java.util.ArrayList;
Here, ArrayList is the name of the class. It belongs to the java.util package. Java uses packages to group together related data types.
Let’s create an ArrayList of String elements by using the new method. The element data type is enclosed in angle brackets, and is a generic. As with arrays, all the elements in an ArrayList must be of the same data type.
jshell> ArrayList<String> animals = new ArrayList<String>();
animals ==> []
The add method appends items to the end of the list and returns true. A two-argument version of add lets you give an index position at which to add an element, but it does not return any value. As with arrays, the first element in an ArrayList has index zero.
jshell> animals.add("ibex");
$5 ==> true
jshell> animals.add("capybara");
$6 ==> true
jshell> animals.add("bison");
$7 ==> true
jshell> animals
animals ==> [ibex, capybara, bison]
jshell> animals.add(1, "giraffe");
jshell> animals
animals ==> [ibex, giraffe, capybara, bison]
Here are other commonly-used ArrayList methods:
Table 1.9.1. ArrayList Methods
Returns number of elements in list
Returns the element at the given index in the list
set(index, element)
Replaces item at given index with the given element. Returns the element previously at the position.
Removes and returns the element at the given index
removeRange(start, finish)
Removes elements from index start up to, but not including, finish
Returns index of the first occurrence of the element in the list, or -1 if element is not in list.

Subsection 1.9.2 Wrapper Classes

Let’s say we wanted an ArrayList with floating point values. If we try something like the following, we get an error:
jshell> ArrayList<double> prices = new ArrayList<double>();
|  Error:
|  unexpected type
|    required: reference
|    found:    double
|  ArrayList<double> prices = new ArrayList<double>();
|            ^----^
The problem here is that the data type in the angle brackets must be a reference type (object), but data types such as int and double are primitives. Java solves this problem by providing classes that “wrap” a primitive value into an object:
Table 1.9.2. Wrapper Classes
Wrapper Class Wraps primitive
Integer int
Double double
Boolean boolean
Character char
It is possible to use explicit methods to wrap and unwrap primitives (also referred to as box and unbox):
jshell> Integer objectAge = Integer.valueOf(37);
objectAge ==> 37
jshell> int primitiveAge = objectAge.intValue();
primitiveAge ==> 37
However, modern versions of the Java compiler will automatically “auto-box” and “auto-unbox” values:
jshell> Integer objectAge = 37;
objectAge ==> 37
jshell> int primitiveAge = objectAge;
primitiveAge ==> 37

Subsection 1.9.3 Converting an Array to an ArrayList

While you can initialize an array using brace notation, as in the following:
double discount_rates = {0.03, 0.07, 0.105, 0.15};
You cannot initialize an ArrayList the same way. Instead, you might do something like this:
import java.util.ArrayList;
ArrayList<Double> discount_rates = new ArrayList<>();
Notice that the second set of angle brackets in the second line is empty. Java will implicitly use the same data type as on the left hand side of the assignment, which saves you some typing.
Still, this code is verbose; there must be a better way. Here is a slightly better way to do it.
import java.util.ArrayList;
import java.util.Arrays; // notice the "s" at the end!!

ArrayList<Double> discount_rates = new ArrayList<>(
        new Double[] {0.03, 0.07, 0.105, 0.15}
You need to import the Arrays class (line 2). Reading from the “inside out”, line 6 creates a new array of Double on the fly; this avoids needing a temporary variable. Line 5 converts it to a List (another one of Java’s collections), and that becomes the argument to the ArrayList constructor on line 4.

Subsection 1.9.4 The HashMap Collection

Another important collection type in Java is an unordered structure called a HashMap. A HashMap is a collection of associated pairs of items where each pair consists of a key and a value. Unlike arrays and ArrayLists, which are indexed by number, you access values in a HashMap by their keys. For example, if we want to represent Table 1.9.3 of cities and their populations (according to 2018 estimates by the United Nations):
Table 1.9.3. Table of Cities and Populations
City Population
New York City 7,888,121
Tokyo 13,515,271
Dhaka 8,906,039
Luanda 2,165,867
We would use this code:
import java.util.HashMap;

public class HashMapExample {

    public static void main(String[] args) {

        HashMap<String, Integer> cityInfo = new HashMap<>();
        cityInfo.put("New York City", 7_888_121);
        cityInfo.put("Tokyo", 13_515_271);
        cityInfo.put("Dhaka", 8_906_039);
        cityInfo.put("Luanda", 2_165_867);

Line 7 creates the HashMap, where we put the data types for the key and value inside angle brackets. The data types must be reference types, which is why we are using Integer (the objecct wrapper for int).
Lines 8-11 use the put() method to add keys and values to the HashMap. If a key already is in the HashMap, the value given as the second argument will replace the current HashMap value.
Here’s the output from the program:
{New York City=7888121, Tokyo=13515271, Dhaka=8906039, Luanda=2165867}
In this example, it just so happens that the output matches the order in which we entered the items, but there is no guarantee that this will always be the case; the keys in a HashMap are unordered.
To access a value in the map, use the get() method. If the key used as an argument is in the HashMap, this method returns the value; otherwise, it returns null.
You can, then, iterate through a HashMap with code like this, which uses the keySet() method to return a collection of all the HashMap’s keys:
for (String key: cityInfo.keySet()) {
    System.out.format("Key %s has value %,d.%n",
        key, cityInfo.get(key));
That produces this output:
Key New York City has value 7,888,121.
Key Tokyo has value 13,515,271.
Key Dhaka has value 8,906,039.
Key Luanda has value 2,165,867.
(You will learn more about the String.format method in Subsection 1.11.1.)
Here are the commonly-used HashMap methods:
Table 1.9.4. HashMap Methods
Method Purpose
Returns number of key/value pairs in the map
Returns the value associated with the given key
put(key, value)
Replaces value for given key if it is in the map already; adds a new key and value if not. Returns the value previously associated with the key, or null if not previously in map.
Removes and returns the value for the given key, or null if key is not in the map.
Returns a collection of the keys contained in the map.
Returns true if key is in the map, otherwise false.

Subsection 1.9.5 The Set Collection

The Set collection implements the mathematical version of a set. You can think of a Set as an unordered set of elements (hence the name) where no item appears more than once. In Java, Set is an interface; when we need an actual set, we will construct a HashSet (a set using a HashMap for its underlying storage).
Here are the commonly-used Set methods:
Table 1.9.5. Set Methods
If the element is in the set, removes the object from the set and returns true; otherwise returns false and leaves the set unchanged
Returns true if the element is in the set, false otherwise.
You have attempted of activities on this page.