Collections: Lists, Sets and Maps

Introduction

Arrays have a fixed size. Real programs need groups that grow and shrink: a shopping basket, the set of users who are online, a phone book. Java's Collections Framework provides ready-made containers. The three you need most are List (ordered items), Set (no duplicates) and Map (key to value).

ArrayList

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<String> fruits = new ArrayList<>();

        fruits.add("apple");
        fruits.add("banana");
        fruits.add("cherry");
        fruits.add(1, "blueberry");

        System.out.println(fruits);
        System.out.println(fruits.get(0));
        System.out.println(fruits.size());
        System.out.println(fruits.contains("banana"));

        fruits.remove("apple");
        fruits.set(0, "BLUEBERRY");
        System.out.println(fruits);
        System.out.println(fruits.indexOf("cherry"));
    }
}

[apple, blueberry, banana, cherry]
apple
4
true
[BLUEBERRY, banana, cherry]
2

List<String> means a list of Strings. The <...> is a generic type: it says what the list holds, and the compiler stops you adding anything else. You cannot use primitives there, so write List<Integer>, not List<int>.
We declare the variable as List (the interface) and create an ArrayList (one implementation). This is a good habit.
The empty <> after new ArrayList lets Java infer the type.

Quick quiz

What does List<Integer> mean?

Looping over a list

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<Integer> scores = new ArrayList<>();
        scores.add(72);
        scores.add(85);
        scores.add(90);

        int total = 0;
        for (int score : scores) {
            total += score;
        }
        System.out.println("Total: " + total);
        System.out.println("Average: " + (double) total / scores.size());

        scores.forEach(s -> System.out.println("Score " + s));
    }
}

Total: 247
Average: 82.33333333333333
Score 72
Score 85
Score 90

Careful: scores.remove(1) removes the item at index 1, but with List<Integer> you can remove a value with scores.remove(Integer.valueOf(85)). This is an easy trap.

Sorting

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<String> words = new ArrayList<>(List.of("pear", "fig", "banana", "kiwi"));

        Collections.sort(words);
        System.out.println(words);

        words.sort(Comparator.comparing(String::length));
        System.out.println(words);

        words.sort(Comparator.comparing(String::length).reversed());
        System.out.println(words);
    }
}

[banana, fig, kiwi, pear]
[fig, kiwi, pear, banana]
[banana, kiwi, pear, fig]

A Comparator describes how to order items. String::length is a method reference, a short way to say "use each String's length". When lengths tie, the original order is kept.

List.of(...) builds a quick list, but it is immutable: calling add on it throws an exception. Wrap it in new ArrayList<>(...) if you need to change it.

HashSet: no duplicates

A set stores each value at most once and answers "is it in there?" very quickly.

Java

import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        Set<String> visitors = new HashSet<>();
        visitors.add("Asha");
        visitors.add("Ben");
        visitors.add("Asha");

        System.out.println(visitors.size());
        System.out.println(visitors.contains("Ben"));
        System.out.println(visitors.add("Ben"));

        Set<Integer> sorted = new TreeSet<>(List.of(5, 1, 3, 1, 5));
        System.out.println(sorted);
    }
}

2
true
false
[1, 3, 5]

add returns false when the item was already there. A HashSet makes no promise about the order of items, so do not rely on it. A TreeSet keeps items sorted, and a LinkedHashSet keeps insertion order. To remove duplicates from a list: new HashSet<>(list).

HashMap: key to value

A map looks things up by key, like a dictionary.

Java

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> ages = new HashMap<>();
        ages.put("Asha", 14);
        ages.put("Ben", 15);
        ages.put("Asha", 16);

        System.out.println(ages.get("Asha"));
        System.out.println(ages.get("Zed"));
        System.out.println(ages.getOrDefault("Zed", 0));
        System.out.println(ages.containsKey("Ben"));
        System.out.println(ages.size());

        ages.remove("Ben");
        System.out.println(ages);
    }
}

16
null
0
true
2
{Asha=16}

put with an existing key replaces the value. get returns null for a missing key, so getOrDefault is safer.

Looping over a map and counting

Java

import java.util.Map;
import java.util.TreeMap;

public class Main {
    public static void main(String[] args) {
        String text = "the cat and the hat and the bat";
        Map<String, Integer> counts = new TreeMap<>();

        for (String word : text.split(" ")) {
            counts.put(word, counts.getOrDefault(word, 0) + 1);
        }

        for (Map.Entry<String, Integer> entry : counts.entrySet()) {
            System.out.println(entry.getKey() + " -> " + entry.getValue());
        }
    }
}

and -> 2
bat -> 1
cat -> 1
hat -> 1
the -> 3

We used a TreeMap so that keys come out sorted. A HashMap would give the same counts in an unpredictable order.

Quick quiz

Which collection should you pick to store each user name only once, with fast lookup?

Choosing a collection

Need	Use
An ordered list that grows	`ArrayList`
Unique items, order does not matter	`HashSet`
Unique items, sorted	`TreeSet`
Look up a value by key	`HashMap`
Keys in sorted order	`TreeMap`
Keep insertion order	`LinkedHashSet` / `LinkedHashMap`

Try it yourself

On your computer, write a program that takes the list "b", "a", "c", "a", "b", "a" and prints how many times each appears, in alphabetical order. You should see a -> 3, b -> 2 and c -> 1.

Summary

List (ArrayList) is an ordered, growable list. Set (HashSet) holds unique values. Map (HashMap) links keys to values.
Collections are generic: List<String> holds only Strings, and primitives become wrapper types like Integer.
Sort with Collections.sort or list.sort(Comparator...). List.of creates an immutable list.
HashSet and HashMap have no guaranteed order. Use TreeSet / TreeMap for sorted order.

Collections: Lists, Sets and Maps

In this lesson you will

Introduction

ArrayList

Looping over a list

Sorting

HashSet: no duplicates

HashMap: key to value

Looping over a map and counting

Choosing a collection

Try it yourself

Summary

Lesson complete