Chapter 3 · Data
Lists and maps
Step 1 of 19 · Concept
A list grows as you add to it
In this lesson you keep values in lists that grow, and in maps that find them by a key.
An array's length is fixed. An ArrayList grows as you add and shrinks as you remove. It lives in
java.util.
ArrayList<String> items = new ArrayList<>();
items.add("bread");
ArrayList<String> reads "a list of String". The angle brackets name the elements' type, so javac refuses
items.add(5). On the right, <> takes the type from the left.
Step 2 of 19 · Concept
What a list can do
| call | does |
|---|---|
items.add("milk") | puts "milk" at the end |
items.get(0) | the element at index 0, counted as in an array |
items.size() | how many elements: an array's length, but a method |
items.contains("milk") | true if "milk" is in the list |
items.indexOf("eggs") | its index, or -1 if it is not there |
items.remove("milk") | takes it out; items.remove(0) takes out index 0 |
Step 3 of 19 · Concept
A list holds arrows
An ArrayList is an object on the heap, and items holds an arrow to it. The list itself holds an arrow per
element.
items.remove(1) takes out the element at index 1. The elements after it move up one place: "eggs" is now at
index 1. The list no longer points at "milk".
Step 4 of 19 · Quiz
After a remove
items holds [bread, milk, eggs]. After items.remove(0), what is items.get(0)?
Step 5 of 19 · Demo
A list at work
Run it. println(items) prints the whole list, and a for-each goes through a list as through an array.
Step 6 of 19 · Concept
Numbers in a list: Integer
ArrayList<Integer> nums = new ArrayList<>();
nums.add(7);
nums.add(3);
int[] arr = {7, 3};
The type in angle brackets must be a class, and int is not one. An Integer is an object with one int inside.
nums.add(7) puts 7 into an Integer for you: autoboxing. int n = nums.get(0); takes it out again.
Double, Boolean and Character do the same for double, boolean and char.
Step 7 of 19 · Quiz
Which one compiles?
Which line makes a list of whole numbers?
Step 8 of 19 · Exercise
Your turn: each name once
Complete unique: it returns a list of the names in their first order, each name only once. Add a name to
result only if result does not contain it yet. The program must print:
[Ada, Grace, Alan]
3 different names
Go through names with a for-each. For each name, ask the list result a question first.
The question is !result.contains(name): true when the name is new. Then result.add(name);.
for (String name : names) {
if (!result.contains(name)) {
result.add(name);
}
}
Step 9 of 19 · Concept
A map finds a value by its key
A map stores pairs: a key and its value. You look a value up by its key, as you look a word up in a dictionary.
HashMap<String, Integer> stock = new HashMap<>();
stock.put("pears", 2);
stock.put("apples", 7);
HashMap<String, Integer> maps String keys to Integer values: how many of each fruit a shop has.
Step 10 of 19 · Concept
What a map can do
| call | does |
|---|---|
stock.put("kiwis", 4) | stores the pair; a key that is there gets the new value |
stock.get("apples") | the key's value, or null if the key is not there |
stock.getOrDefault("plums", 0) | the value, or 0 if the key is not there |
stock.containsKey("pears") | true if the key is there |
null means no object at all: a box with no arrow (lesson 7). For a count, getOrDefault with 0 is what you
need.
Step 11 of 19 · Quiz
One key, one value
What does this print?
stock.put("apples", 5);
stock.put("apples", 7);
System.out.println(stock.get("apples"));
Step 12 of 19 · Concept
Every pair, in order
A HashMap keeps its keys in no order you can count on. A TreeMap keeps them sorted.
new TreeMap<>(stock) makes a sorted copy.
| call | gives |
|---|---|
sorted.keySet() | the keys: [apples, pears] |
sorted.entrySet() | the pairs, one Map.Entry each |
e.getKey(), e.getValue() | a pair's key and value |
Step 13 of 19 · Demo
A map at work
Run it. stock.put("pears", stock.get("pears") + 1) adds 1 to a value: read it, add, store it back.
Step 14 of 19 · Exercise
Your turn: counting words
Complete count: it returns how often each word appears. For each word, store its count so far plus one. A
TreeMap prints its pairs in sorted order, so the program must print:
{be=2, not=1, or=1, to=2}
be: 2
A word seen for the first time has no count yet: getOrDefault gives 0 for it.
In a for-each over words: read the count with counts.getOrDefault(word, 0), add 1, and put it back.
for (String word : words) {
counts.put(word, counts.getOrDefault(word, 0) + 1);
}
Step 15 of 19 · Concept
An array, a list or a map?
| use | when | example |
|---|---|---|
| an array | the number of elements is known and fixed | the 9 squares of a tic-tac-toe board |
| a list | elements come and go, or you do not know how many | a shopping list |
| a map | you find things by a name, not by a position | the stock of each fruit |
Step 16 of 19 · Quiz
Pick the right one
A program keeps each student's points and looks them up by the student's name. What fits best?
Step 17 of 19 · Check yourself
Check yourself: a gradebook
Main.java uses the class Gradebook. Write its four methods, each as its comment says.
A field can get its value where it is declared, as these two fields do. The program must print:
Grace: 4
Ada: 12
Best: Ada
The list keeps the order the names came in; the map keeps each name's points. add puts a new name in both.
Step 18 of 19 · Challenge · optional
Challenge: letters in a word
Optional. It earns the lesson's third star.
Count how often each letter appears in word, in a map, and print the map in sorted order. The program must print:
{a=3, b=1, n=2}
It is the word count of Your turn: counting words, with the characters of one word instead of words.
The key type must be a class: HashMap<Character, Integer>. Import HashMap and TreeMap as Your turn:
counting words does.
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
counts.put(c, counts.getOrDefault(c, 0) + 1);
}
Step 19 of 19 · Recap
Recap
- An
ArrayListgrows and shrinks. It holds arrows to its elements. - The type in angle brackets is a class:
Integerforint, boxed for you. - A
HashMapfinds a value by its key, each key once, in no order. ATreeMapkeeps its keys sorted. - An array for a fixed number, a list for a changing one, a map to find by name.
Next: lesson 14 shows how a program catches exceptions, and how your own methods throw them.
Review
4 questions from this lesson, in a new order each time. Answer from memory: 3 of 4 right on the first try passes. On a day after you finish the lesson, a pass earns 15 XP.
The review needs JavaScript.
import java.util.ArrayList;
public class Shopping {
public static void main(String[] args) {
ArrayList<String> items = new ArrayList<>();
items.add("bread");
items.add("milk");
items.add("eggs");
System.out.println(items);
System.out.print(items.size() + " items, ");
System.out.println("the first is " + items.get(0));
System.out.print(items.contains("milk") + " ");
System.out.print(items.indexOf("eggs") + " ");
System.out.println(items.indexOf("tea"));
items.remove("milk");
System.out.println(items + " " + items.size());
for (String item : items) {
System.out.println("- " + item);
}
}
}
import java.util.ArrayList;
public class Unique {
static ArrayList<String> unique(String[] names) {
ArrayList<String> result = new ArrayList<>();
// add each name that is not in result yet
return result;
}
public static void main(String[] args) {
String[] names = {"Ada", "Grace", "Ada",
"Alan", "Grace", "Ada"};
ArrayList<String> once = unique(names);
System.out.println(once);
System.out.println(once.size() + " different names");
}
}
import java.util.*;
public class Stock {
public static void main(String[] args) {
HashMap<String, Integer> stock = new HashMap<>();
stock.put("pears", 2);
stock.put("apples", 5);
stock.put("apples", 7);
System.out.print(stock.get("apples") + " ");
System.out.println(stock.get("plums"));
System.out.print(stock.getOrDefault("plums", 0) + " ");
System.out.println(stock.containsKey("pears"));
stock.put("pears", stock.get("pears") + 1);
TreeMap<String, Integer> sorted = new TreeMap<>(stock);
System.out.println(sorted.keySet());
for (Map.Entry<String, Integer> e : sorted.entrySet()) {
System.out.print(e.getKey() + ": ");
System.out.println(e.getValue());
}
}
}
import java.util.HashMap;
import java.util.TreeMap;
public class Count {
static HashMap<String, Integer> count(String[] words) {
HashMap<String, Integer> counts = new HashMap<>();
// add 1 to the count of each word
return counts;
}
public static void main(String[] args) {
String[] words = {"to", "be", "or", "not", "to", "be"};
HashMap<String, Integer> counts = count(words);
System.out.println(new TreeMap<>(counts));
System.out.println("be: " + counts.get("be"));
}
}
public class Main {
public static void main(String[] args) {
Gradebook book = new Gradebook();
book.add("Grace");
book.add("Ada");
book.add("Grace");
book.score("Ada", 7);
book.score("Grace", 4);
book.score("Ada", 5);
book.score("Bob", 9);
book.print();
System.out.println("Best: " + book.best());
}
}
public class Letters {
public static void main(String[] args) {
String word = "banana";
// a map from each letter to its count,
// printed in sorted order
}
}