The Collections Framework: Lists, Stacks, Queues and Deques

In CPS 2231 you used ArrayList as a "resizable array". In this course you will look at collections the way a library designer does: as abstract data types (what operations exist and what they mean) with several implementations (how they are stored and how much each operation costs). This chapter tours the part of the Java Collections Framework you will use for lists, stacks and queues; later chapters build some of these structures yourself.

The interface hierarchy

Iterable<E>
 └─ Collection<E>
     ├─ List<E>        ArrayList, LinkedList            (indexed sequence)
     ├─ Set<E>         HashSet, TreeSet                 (no duplicates — Chapter on sets)
     └─ Queue<E>       PriorityQueue                    (take from the head)
         └─ Deque<E>   ArrayDeque, LinkedList           (add/remove at both ends)

Map<K, V>              HashMap, TreeMap                 (NOT a Collection)

Map stores pairs (a key and its value, like a word and its meaning in a dictionary), not single elements, so it does not fit the Collection methods such as add(E).

Program to the interface and choose the implementation once: List<String> names = new ArrayList<>(); or Deque<Integer> stack = new ArrayDeque<>();. The declared type decides which methods you can call: LinkedList implements both List and Deque, but through a List variable you cannot call push.

List<String> a = new LinkedList<>();
a.add("x");       // fine: add is in List
a.push("y");      // compile-time error: List has no push, even though the object could do it

Deque<String> b = new LinkedList<>();
b.push("y");      // fine: push is in Deque

The variable's type is like the menu you are given: the kitchen (the object) might cook more dishes, but you can only order what is on your menu.

ArrayList versus LinkedList

ArrayList stores elements in an array that is replaced by a larger one when full; LinkedList is a doubly linked chain of nodes, each holding an element and references to its neighbours.

ArrayList: one array, elements side by side
  index:   0   1   2   3   4   5   6   7
         [ A | B | C | D |   |   |   |   ]     size = 4, capacity = 8

LinkedList: separate nodes, each with a link to the previous and the next node
  head                                 tail
   ↓                                    ↓
  [A] <──> [B] <──> [C] <──> [D]

Worked example: add(0, "X") on [A, B, C, D]. Both lists end up as [X, A, B, C, D], but the work is very different:

ArrayList — shift every element one place to the right, then write X:
  step 1: [ A | B | C | D |   ]    move D to index 4
  step 2: [ A | B | C | D | D ]    move C to index 3
  step 3: [ A | B | C | C | D ]    move B to index 2
  step 4: [ A | B | B | C | D ]    move A to index 1
  step 5: [ X | A | B | C | D ]    write X at index 0      → n moves: O(n)

LinkedList — create one node and change a few links:
  [X] <──> [A] <──> [B] <──> [C] <──> [D]
   ↑ new head                                               → O(1)

Operation	ArrayList	LinkedList
get(i), set(i, x)	O(1)	O(n) — walks from the nearer end
add(x) at the end	O(1) amortised	O(1)
add(0, x) / remove(0)	O(n) — shifts everything	O(1)
add(i, x) / remove(i) in the middle	O(n) shifting	O(n) to find the position, O(1) to relink
insert/remove via an iterator already at the position	O(n) shifting	O(1)
contains(x), indexOf(x)	O(n)	O(n)
memory per element	one reference	node with element + two links

Amortised O(1) means "O(1) on average over many operations". Most add(x) calls just write into a free slot. Now and then the array is full and must be copied into a bigger one (an O(n) step), but this happens so rarely that the average cost per add stays constant — like paying rent every month instead of buying a house: one big payment, spread over a long time.

In practice ArrayList wins almost always: arrays are compact and cache-friendly. Choose LinkedList only when you really insert or delete at the front or through an iterator a lot — and for a queue or stack prefer ArrayDeque anyway.

Iterator and ListIterator

Every Collection is Iterable, so it can give you an Iterator<E>:

Method	Meaning
hasNext()	is there another element?
next()	return it and move past it (NoSuchElementException at the end)
remove()	remove the element last returned by next() — at most once per next()

cursor positions:   ^ A ^ B ^ C ^
                    0   1   2   3

start: cursor at 0.   next() returns A, cursor moves to 1.
                      next() returns B, cursor moves to 2.   remove() deletes B.

The enhanced for loop for (E x : coll) is compiled into exactly this hasNext/next loop. A List also offers listIterator(), whose ListIterator can move backwards (hasPrevious, previous), report indices (nextIndex), replace the last returned element (set) and insert before the cursor (add).

ListIterator<String> it = list.listIterator();
while (it.hasNext()) {
    String s = it.next();
    if (s.isEmpty()) it.remove();          // delete this one
    else it.set(s.trim());                 // replace this one
}

Worked example with list = [" a ", "", "b", ""]:

Round	next() returns	Action	list after the round	nextIndex()
1	" a "	not empty → set("a")	[a, "", b, ""]	1
2	""	empty → remove()	[a, b, ""]	1
3	"b"	not empty → set("b")	[a, b, ""]	2
4	""	empty → remove()	[a, b]	2

After a remove(), nextIndex() does not grow: the elements behind the cursor moved one place to the left.

remove() without a preceding next(), or twice for the same next(), throws IllegalStateException.

Fail-fast iterators

The collections in java.util count their structural modifications (adds and removes, not set) in a field called modCount. An iterator remembers the value it expects; each next() checks it, and if the collection was modified by anything other than the iterator itself, it throws ConcurrentModificationException. The name is misleading — no threads are needed; the usual cause is calling list.remove(...) inside a for-each loop over the same list.

The check happens in next(), not in hasNext(). That produces a famous special case: removing the second-to-last element makes the list shrink so that hasNext() returns false, the loop simply ends, and no exception is thrown — the last element is silently skipped. Fail-fast behaviour is a debugging aid, not a guarantee.

Worked example: the two cases side by side with list = [A, B, C] and for (String s : list) { … list.remove(s); }:

Remove when s is	What happens	Result
"A" (first)	after removal size = 2, cursor = 1 → hasNext() is true → next() sees the changed modCount	ConcurrentModificationException
"B" (second-to-last)	after removal size = 2, cursor = 2 → hasNext() is false → loop ends quietly	[A, C], and C was never visited

Calling list.set(0, "Z") inside the loop is fine: set is not a structural change.

Removing while iterating — correctly

// 1. Let the iterator do the removing
Iterator<Integer> it = nums.iterator();
while (it.hasNext()) {
    if (it.next() < 0) it.remove();
}

// 2. Java 8: say what to remove
nums.removeIf(n -> n < 0);

// 3. Index loop, walking BACKWARDS so shifts do not skip elements
for (int i = nums.size() - 1; i >= 0; i--) {
    if (nums.get(i) < 0) nums.remove(i);
}

A forward index loop that removes with remove(i) and then does i++ skips the element that slid into position i.

Worked example: the forward bug. Remove all negative numbers from [-1, -2, 3, -4] with for (int i = 0; i < nums.size(); i++) if (nums.get(i) < 0) nums.remove(i);

i	nums.get(i)	Action	nums after
0	−1	remove index 0; −2 slides into index 0	[-2, 3, -4]
1	3	keep (−2 at index 0 was skipped)	[-2, 3, -4]
2	−4	remove index 2	[-2, 3]

Wrong result: [-2, 3]. The same list with the backwards loop:

i	nums.get(i)	Action	nums after
3	−4	remove	[-1, -2, 3]
2	3	keep	[-1, -2, 3]
1	−2	remove	[-1, 3]
0	−1	remove	[3]

Correct result: [3]. Going backwards works because a removal only shifts elements you have already checked.

For example, with nums = [5, 7, 1]: nums.remove(1) gives [5, 1] (index 1 was 7), but nums.remove(Integer.valueOf(1)) gives [5, 7].

Stacks and queues with Deque

A stack is LIFO (last in, first out); a queue is FIFO (first in, first out). The Deque ("double-ended queue", say deck) interface does both, because it can add and remove at either end. ArrayDeque implements it with a circular array: all end operations are O(1) amortised.

Use	Add	Remove	Look	Where
Stack	push(x)	pop()	peek()	all at the front (head)
Queue	offer(x)	poll()	peek()	add at the back, remove from the front
Deque	offerFirst / offerLast	pollFirst / pollLast	peekFirst / peekLast	either end

Each operation has two flavours: add/remove/element (and push/pop) throw an exception when they fail — e.g. NoSuchElementException on an empty deque — while offer/poll/peek return a special value (false or null). Printing an ArrayDeque lists it from head to tail, so a stack prints top first.

Deque<Character> stack = new ArrayDeque<>();
stack.push('a'); stack.push('b');     // [b, a]
stack.pop();                          // 'b'

Deque<String> queue = new ArrayDeque<>();
queue.offer("x"); queue.offer("y");  // [x, y]
queue.poll();                         // "x"

Worked example: a stack, step by step (printed as System.out.println(stack), head first):

Step	Operation	Returns	Deque after (head first)
1	push("A")	—	[A]
2	push("B")	—	[B, A]
3	push("C")	—	[C, B, A]
4	pop()	"C"	[B, A]
5	peek()	"B"	[B, A] (peek does not remove)

The same letters in a queue:

Step	Operation	Returns	Deque after (head first)
1	offer("A"), offer("B"), offer("C")	true each	[A, B, C]
2	poll()	"A"	[B, C]
3	offer("D")	true	[B, C, D]
4	peek()	"B"	[B, C, D]

On an empty deque, poll() and peek() return null, while pop() throws NoSuchElementException.

A classic stack use: matching brackets. Push every opening bracket; at every closing bracket, pop and check that it matches.

static boolean balanced(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') {
            stack.push(c);
        } else if (c == ')' || c == ']' || c == '}') {
            if (stack.isEmpty()) return false;
            char open = stack.pop();
            if ((c == ')' && open != '(') || (c == ']' && open != '[') || (c == '}' && open != '{'))
                return false;
        }
    }
    return stack.isEmpty();
}

Trace for "{[()]}":

Character	Action	Stack after (top first)
{	push	[{]
[	push	[[, {]
(	push	[(, [, {]
)	pop ( — matches	[[, {]
]	pop [ — matches	[{]
}	pop { — matches	[]

The stack is empty at the end, so the answer is true. For "([)]" the stack is [[, (] when ) arrives; the pop gives [, which does not match, so the answer is false.

ArrayDeque does not accept null elements (NullPointerException): null is reserved as the "empty" answer of poll and peek.

Why not java.util.Stack?

Stack is a legacy class from Java 1.0. It extends Vector, so every method is synchronised (slower, for no benefit in single-threaded code), and it inherits index methods such as add(0, x), get(i) and remove(i) that let code break the LIFO discipline. Its toString also lists bottom first, the opposite of ArrayDeque. The Java documentation itself recommends Deque<E> stack = new ArrayDeque<>(). LinkedList also implements Deque, but it allocates a node per element; use it only if you also need List operations or null elements.

After push("A"), push("B"), push("C")	Printed
Stack<String>	[A, B, C] (bottom first)
ArrayDeque<String>	[C, B, A] (top first)

PriorityQueue

A PriorityQueue is a queue whose poll() always removes the smallest element — by natural order, or by the Comparator given to the constructor:

PriorityQueue<Integer> minFirst = new PriorityQueue<>();
PriorityQueue<Integer> maxFirst = new PriorityQueue<>(Comparator.reverseOrder());
PriorityQueue<Task> byDeadline = new PriorityQueue<>(Comparator.comparing(Task::getDeadline));

offer and poll are O(log n) and peek is O(1). Internally it is a binary heap stored in an array (a later chapter builds one). Only the head is guaranteed to be the minimum; the rest of the array is only partially ordered. So toString(), a for-each loop and the iterator show the elements in heap order, which is generally not sorted. To see them in priority order, poll repeatedly.

Worked example. Offer 5, 1, 4, 2, 3 to a new PriorityQueue<Integer>() and print after each step:

Step	Operation	println(pq) shows	peek()
1	offer(5)	[5]	5
2	offer(1)	[1, 5]	1
3	offer(4)	[1, 5, 4]	1
4	offer(2)	[1, 2, 4, 5]	1
5	offer(3)	[1, 2, 4, 5, 3]	1

The printed order [1, 2, 4, 5, 3] is not sorted, but the smallest element is always first. Now poll() five times: 1, 2, 3, 4, 5 — sorted. The array is a tree drawn row by row: every parent is smaller than or equal to its children, but brothers and sisters have no order.

array: [1, 2, 4, 5, 3]            the same array as a tree:
index:  0  1  2  3  4                       1          index 0
                                          /   \
                                         2     4       index 1, 2
                                        / \
                                       5   3           index 3, 4

With Comparator.reverseOrder(), the same five numbers print as [5, 3, 4, 1, 2] and peek() is 5.

Arrays.asList and the Collections utilities

• Arrays.asList(a, b, c) returns a fixed-size list backed by the array: set works (and writes through to the array), but add and remove throw UnsupportedOperationException. Wrap it — new ArrayList<>(Arrays.asList(...)) — when you need a growable list.
• Collections.sort(list) / list.sort(cmp) — stable sort, O(n log n).
• Collections.binarySearch(list, key) — O(log n) on a list sorted in ascending order (by the same ordering). On success it returns the index; otherwise it returns -(insertionPoint) - 1, always negative. On unsorted data the result is undefined.
• Collections.unmodifiableList(list) — a read-only view: every mutator throws UnsupportedOperationException, but changes made to the original list are still visible through the view.
• Also handy: Collections.reverse, shuffle, swap, max, min, frequency.

Worked examples (all checked with the JDK):

String[] arr = {"a", "b", "c"};
List<String> fixed = Arrays.asList(arr);
fixed.set(0, "z");          // arr is now {z, b, c}: the list writes through to the array
fixed.add("d");             // UnsupportedOperationException: the size is fixed

Collections.binarySearch on [10, 20, 30, 40]. The insertion point is the index where the key would be inserted to keep the list sorted:

Key	Found?	Insertion point	Return value
30	yes, at index 2	—	2
25	no	2 (between 20 and 30)	−(2) − 1 = -3
5	no	0 (before everything)	−(0) − 1 = -1
50	no	4 (after everything)	−(4) − 1 = -5

Why the extra "− 1"? Without it, "not found, insert at 0" would return −0 = 0, which looks exactly like "found at index 0".

List<String> orig = new ArrayList<>(Arrays.asList("x"));
List<String> view = Collections.unmodifiableList(orig);
orig.add("y");              // allowed: orig is a normal list
System.out.println(view);   // [x, y]  — the view shows the change
view.add("z");              // UnsupportedOperationException

Choosing the right collection

Need	Choose
sequence with fast access by index	ArrayList
LIFO: undo, bracket matching, depth-first search	ArrayDeque as a stack
FIFO: print jobs, buffering, breadth-first search	ArrayDeque as a queue
always serve the most urgent / smallest item	PriorityQueue
many insertions/removals in the middle via an iterator	LinkedList
a list that must never change	Collections.unmodifiableList(...)

Worked example: three quick decisions.

1. A text editor's Undo button — the last change must be undone first → LIFO → ArrayDeque used as a stack.
2. Customers calling a help line — the first caller should be answered first → FIFO → ArrayDeque used as a queue.
3. An airport choosing which plane lands next, lowest fuel first → by priority → PriorityQueue with Comparator.comparing(Plane::getFuel).

Key takeaways

• List, Set, Queue and Deque extend Collection; Map does not. The declared type decides which methods you may call.
• ArrayList = numbered seats: O(1) get(i), O(n) insert at the front. LinkedList = chain of nodes: O(1) at the ends, O(n) get(i). Prefer ArrayList in almost every case.
• An iterator is a bookmark between elements; it.remove() deletes the element last returned by next().
• Changing a list (add/remove) during a for-each loop → ConcurrentModificationException, except the silent second-to-last case. Use it.remove(), removeIf, or a backwards index loop.
• list.remove(1) removes index 1; list.remove(Integer.valueOf(1)) removes the value 1.
• Use ArrayDeque for both stacks (push/pop/peek) and queues (offer/poll/peek); not Stack, and no null elements.
• PriorityQueue.poll() returns the smallest element first (O(log n)), but printing or iterating shows heap order, not sorted order.
• Arrays.asList is fixed-size; unmodifiableList is a read-only view; binarySearch returns -(insertionPoint) - 1 when the key is missing.