Tracing the Two Maps
Here is a sequence of operations on a Map<String, Integer> that starts out empty:
map.put("kim", 41);
map.put("lee", 67);
map.put("max", 83);
map.put("lee", 90);
map.remove("kim");
map.get("lee");
map.get("kim");
map.put("ola", 58);
map.remove("ola");
map.remove("pat");
put stores the value under the key, replacing any old value, and returns true if the key was not present before. get returns the value stored under the key, or null if the key is absent. remove returns true if the call changed the map.
Solution
put("kim", 41) returns true. size = 1
┌─────────┐
head ───▶ │ kim: 41 │ ──▶ null
└─────────┘
put("lee", 67) returns true. size = 2
┌─────────┐ ┌─────────┐
head ───▶ │ lee: 67 │ ──▶ │ kim: 41 │ ──▶ null
└─────────┘ └─────────┘
put("max", 83) returns true. size = 3
┌─────────┐ ┌─────────┐ ┌─────────┐
head ───▶ │ max: 83 │ ──▶ │ lee: 67 │ ──▶ │ kim: 41 │ ──▶ null
└─────────┘ └─────────┘ └─────────┘
put("lee", 90) returns false. The node for lee keeps its place, and its value becomes 90. size = 3
┌─────────┐ ┌─────────┐ ┌─────────┐
head ───▶ │ max: 83 │ ──▶ │ lee: 90 │ ──▶ │ kim: 41 │ ──▶ null
└─────────┘ └─────────┘ └─────────┘
remove("kim") returns true. size = 2
┌─────────┐ ┌─────────┐
head ───▶ │ max: 83 │ ──▶ │ lee: 90 │ ──▶ null
└─────────┘ └─────────┘
get("lee") returns 90.
get("kim") returns null.
put("ola", 58) returns true. size = 3
┌─────────┐ ┌─────────┐ ┌─────────┐
head ───▶ │ ola: 58 │ ──▶ │ max: 83 │ ──▶ │ lee: 90 │ ──▶ null
└─────────┘ └─────────┘ └─────────┘
remove("ola") returns true. size = 2
┌─────────┐ ┌─────────┐
head ───▶ │ max: 83 │ ──▶ │ lee: 90 │ ──▶ null
└─────────┘ └─────────┘
remove("pat") returns false. pat is not in the map, so the list does not change.
Solution
put("kim", 41) returns true. size = 1
┌─────────┐
│ kim: 41 │
└─────────┘
0
put("lee", 67) returns true. size = 2
┌─────────┬─────────┐
│ kim: 41 │ lee: 67 │
└─────────┴─────────┘
0 1
put("max", 83) returns true. size = 3
┌─────────┬─────────┬─────────┐
│ kim: 41 │ lee: 67 │ max: 83 │
└─────────┴─────────┴─────────┘
0 1 2
put("lee", 90) returns false. The entry at index 1 keeps its place, and its value becomes 90. size = 3
┌─────────┬─────────┬─────────┐
│ kim: 41 │ lee: 90 │ max: 83 │
└─────────┴─────────┴─────────┘
0 1 2
remove("kim") returns true. The last entry, max: 83, moves into index 0. size = 2
┌─────────┬─────────┐
│ max: 83 │ lee: 90 │
└─────────┴─────────┘
0 1
get("lee") returns 90.
get("kim") returns null.
put("ola", 58) returns true. size = 3
┌─────────┬─────────┬─────────┐
│ max: 83 │ lee: 90 │ ola: 58 │
└─────────┴─────────┴─────────┘
0 1 2
remove("ola") returns true. The entry for ola is the last entry, so nothing moves. size = 2
┌─────────┬─────────┐
│ max: 83 │ lee: 90 │
└─────────┴─────────┘
0 1
remove("pat") returns false. pat is not in the map, so the array does not change.