Java's ready-made data structures: Collections

For eight weeks we wrote linked lists, stacks and queues by hand. In a real project you don’t write these from scratch: Java’s java.util package has tested, fast versions of all of them. The goal of this week is twofold: to recognize the Java counterpart of every structure you wrote by hand, and to pick the right class for the right job. Exam questions are usually of the “what is printed?” type and contain small traps: is remove(1) an index or a value, the toString difference between Stack and ArrayDeque, the difference between poll and remove on an empty queue.

Golden rules:

1. Declare the variable with the interface type. List<Integer> a = new ArrayList<>();
2. Use ArrayDeque for stacks and queues. The Stack class is old.
3. ArrayList if there is a lot of access by index, ArrayDeque/LinkedList if there is a lot of insertion at the ends.
4. Removing while traversing: Iterator.remove() or removeIf. Don’t call list.remove inside a for-each.
5. HashMap for lookup by key.

A map of the Collections Framework

All of them are generic: they take a type parameter such as <Integer>. You can’t put in a primitive type (int, double); a wrapper class is used. Java converts automatically between int and Integer (autoboxing).

ArrayList: the growing array

It keeps an array inside, and when full it copies to about 1.5 times the size. The same idea as the “growing array stack” in week 5.

List<String> s = new ArrayList<>();
s.add("A"); s.add("B"); s.add("C");
s.add(1, "X");          // insert in the middle, shift the right side
s.set(0, "Y");          // replace
System.out.println(s + " size=" + s.size() + " indexOf(B)=" + s.indexOf("B") + " contains(A)=" + s.contains("A"));

[Y, X, B, C] size=4 indexOf(B)=2 contains(A)=false

PITFALL · remove(int) and remove(Object). On a List<Integer>, list.remove(1) removes index 1. To remove the element whose value is 1, write list.remove(Integer.valueOf(1)). When Java sees an int argument, it chooses the index version.

List<Integer> list = new ArrayList<>(List.of(10, 20, 30, 40));
list.remove(1);                     // index 1 → 20 goes
System.out.println(list);
list.remove(Integer.valueOf(30));   // value 30
System.out.println(list);

[10, 30, 40]
[10, 40]

LinkedList: a doubly linked list

The ready-made version of the DoublyLinkedList from week 3. It implements both the List and Deque interfaces, so it can be used both by index and from the ends.

LinkedList<Integer> ll = new LinkedList<>();
ll.add(5); ll.addFirst(2); ll.addLast(8); ll.add(1, 4);
System.out.println(ll + " getFirst=" + ll.getFirst() + " get(2)=" + ll.get(2));
ll.removeLast(); ll.removeFirst();
System.out.println(ll);

[2, 4, 5, 8] getFirst=2 get(2)=5
[4, 5]

get(2) works but internally it walks from the front (or from the back, whichever is closer): O(n). A loop for (int i = 0; i < ll.size(); i++) ll.get(i) over a LinkedList is O(n²) in total. Use for-each to traverse.

Measurement: inserting n elements at the front.

n=10000 ArrayList add(0) 3.1 ms, LinkedList addFirst 0.6 ms
n=20000 ArrayList add(0) 11.3 ms, LinkedList addFirst 0.8 ms
n=40000 ArrayList add(0) 46.2 ms, LinkedList addFirst 0.8 ms

When n quadrupled, ArrayList slowed by about 15 times (each insertion O(n), O(n²) in total). LinkedList stayed almost constant (each insertion O(1)). The times vary by machine, the ratio doesn’t.

Stack and queue: ArrayDeque

ArrayDeque is the ready-made version of the circular-array deque from week 8. It is the fastest choice both as a stack and as a queue.

Deque<Integer> stack = new ArrayDeque<>();   // stack
stack.push(1); stack.push(2); stack.push(3);
System.out.println(stack + " peek=" + stack.peek());

Queue<Integer> q = new LinkedList<>();       // queue
q.offer(7); q.offer(3); q.offer(5);
System.out.println(q.poll() + " " + q.peek() + " " + q);

[3, 2, 1] peek=3
7 3 [3, 5]

The old Stack class

java.util.Stack still exists and some instructors use it. It derives from Vector, every method is synchronized (slow), and it also allows access by index (which breaks the stack rule).

Stack<Integer> st = new Stack<>();
st.push(1); st.push(2); st.push(3);
System.out.println(st.pop() + " " + st.peek() + " " + st);

3 2 [1, 2]

PITFALL · Two different toStrings. With the same push order, Stack writes from bottom to top ([1, 2, 3]) and ArrayDeque from top to bottom ([3, 2, 1]). pop gives 3 in both. In an output question, look at which class it is.

Two families: exception or special value?

On an empty queue:

null null
remove: NoSuchElementException
element: NoSuchElementException
deque peek=null
deque pop: NoSuchElementException
Stack pop: EmptyStackException
ArrayDeque null: NullPointerException

The last line: null can’t be put into an ArrayDeque, because poll returning null means “empty”.

Iterator

Every collection provides an Iterator: hasNext(), next(), remove(). The for-each loop uses this behind the scenes. It is the abstract version of the traversal you did with p = p.next on a linked list.

List<Integer> nums = new ArrayList<>(List.of(1, 2, 3, 4, 5, 6));
Iterator<Integer> it = nums.iterator();
while (it.hasNext())
    if (it.next() % 2 == 0) it.remove();
System.out.println(nums);

[1, 3, 5]

If you change the list directly inside a for-each, the iterator notices and throws a ConcurrentModificationException at the next next(). A one-line modern alternative: nums.removeIf(x -> x % 2 == 0);

HashMap basics

A table that maps keys to values. Lookup, insertion and deletion are O(1) on average. How it works (hashing) is a SEN2212 topic; here we learn to use it.

Map<String, Integer> count = new HashMap<>();
for (String w : "to be or not to be".split(" "))
    count.put(w, count.getOrDefault(w, 0) + 1);
System.out.println(count.get("to") + " " + count.get("or") + " " + count.get("is") + " size=" + count.size());
System.out.println(new TreeMap<>(count));

2 1 null size=4
{be=2, not=1, or=1, to=2}

A HashMap’s traversal order is undefined; use TreeMap if you want sorted order, LinkedHashMap if you want insertion order.

Which structure for which job?

Common mistakes

List<Integer> list = new ArrayList<>(List.of(10, 20, 30, 40));
list.remove(1);
System.out.println(list);
list.remove(Integer.valueOf(30));
System.out.println(list);

List<String> s = new ArrayList<>();
s.add("A"); s.add("B"); s.add("C");
s.add(1, "X");
s.set(0, "Y");
System.out.println(s + " " + s.indexOf("B") + " " + s.contains("A"));

Stack<Integer> st = new Stack<>();
st.push(1); st.push(2); st.push(3);
System.out.println(st.pop() + " " + st.peek() + " " + st);

Deque<Integer> ad = new ArrayDeque<>();
ad.push(1); ad.push(2); ad.push(3);
System.out.println(ad + " peek=" + ad.peek());

Queue<Integer> q = new LinkedList<>();
q.offer(7); q.offer(3); q.offer(5);
System.out.println(q.poll() + " " + q.peek() + " " + q);
q.offer(q.poll());
System.out.println(q);

System.out.println(q.poll());
System.out.println(q.peek());
q.remove();

List<Integer> nums = new ArrayList<>(List.of(1, 2, 3, 4, 5, 6));
Iterator<Integer> it = nums.iterator();
while (it.hasNext())
    if (it.next() % 2 == 0) it.remove();
System.out.println(nums);

List<Integer> a = new ArrayList<>(List.of(1, 2, 3, 4));
for (Integer x : a) if (x == 2) a.remove(x);   // (i)

List<Integer> b = new ArrayList<>(List.of(1, 2, 3, 4));
for (Integer x : b) if (x == 3) b.remove(x);   // (ii)
System.out.println(b);

Map<String, Integer> count = new HashMap<>();
for (String w : "to be or not to be".split(" "))
    count.put(w, count.getOrDefault(w, 0) + 1);
System.out.println(count.get("to") + " " + count.get("or") + " " + count.get("is") + " size=" + count.size());

Map<String, Integer> m = new HashMap<>();
System.out.println(m.put("ali", 70));
System.out.println(m.put("ali", 85));
m.put("ece", 90);
System.out.println(m.get("ali") + " " + m.size() + " " + m.getOrDefault("can", -1));