The Collections Framework: Lists, Stacks, Queues and Deques

Which of these types is not a subtype of Collection<E>?

Which operation is O(1) on an ArrayList but O(n) on a LinkedList of n elements?

What is the result?

List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3));
for (Integer x : list) {
    if (x == 1) list.remove(x);
}
System.out.println(list);

The same loop, but removing the element 2. What is the result?

List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3));
for (Integer x : list) {
    if (x == 2) list.remove(x);
}
System.out.println(list);

The loop is meant to remove every even number. What does it print?

List<Integer> list = new ArrayList<>(Arrays.asList(2, 4, 5, 6, 8));
for (int i = 0; i < list.size(); i++) {
    if (list.get(i) % 2 == 0) list.remove(i);
}
System.out.println(list);

What is the result?

List<Integer> list = new ArrayList<>(Arrays.asList(7, 8, 9));
Iterator<Integer> it = list.iterator();
it.next();
it.remove();
it.remove();
System.out.println(list);

What does this fragment print?

List<String> l = new ArrayList<>(Arrays.asList("a", "b", "c"));
ListIterator<String> it = l.listIterator();
while (it.hasNext()) {
    String s = it.next();
    if (s.equals("b")) {
        it.set("B");
        it.add("x");
    }
}
System.out.println(l);

For an ArrayList, when is a ConcurrentModificationException thrown by a fail-fast iterator?

What does this fragment print?

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

What does this fragment print?

Deque<String> q = new ArrayDeque<>();
q.offer("A");
q.offer("B");
q.offer("C");
q.poll();
q.offer("D");
System.out.println(q.peek() + " " + q.size());

What does this fragment print?

Deque<Integer> d = new ArrayDeque<>();
d.push(1);
d.offer(2);
d.push(3);
d.offer(4);
System.out.println(d.poll() + " " + d.pollLast() + " " + d);

What is the result?

Deque<Integer> d = new ArrayDeque<>();
System.out.print(d.poll() + " " + d.peek() + " ");
System.out.print(d.pop());

What is the result?

Queue<String> a = new LinkedList<>();
Queue<String> b = new ArrayDeque<>();
a.offer(null);
b.offer(null);
System.out.println(a.size() + " " + b.size());

Why does the Java documentation recommend Deque<E> s = new ArrayDeque<>() instead of java.util.Stack for a stack?

What does this fragment print?

Stack<Integer> s = new Stack<>();
s.push(1);
s.push(2);
s.add(0, 99);
System.out.println(s.pop() + " " + s);

What does this fragment print?

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(7);
pq.offer(3);
pq.offer(9);
pq.offer(1);
while (!pq.isEmpty()) {
    System.out.print(pq.poll() + " ");
}

What does this fragment print?

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(3);
pq.offer(1);
pq.offer(2);
System.out.println(pq + " " + pq.peek());

What does this fragment print?

PriorityQueue<String> pq = new PriorityQueue<>(
        Comparator.comparing(String::length).thenComparing(Comparator.naturalOrder()));
pq.addAll(Arrays.asList("pear", "fig", "banana", "kiwi"));
pq.poll();
System.out.println(pq.poll() + " " + pq.poll());

What is the result?

String[] arr = {"x", "y", "z"};
List<String> list = Arrays.asList(arr);
list.set(0, "w");
System.out.print(arr[0] + " ");
list.add("v");
System.out.print(list.size());

What does this fragment print?

List<Integer> l = new ArrayList<>(Arrays.asList(10, 20, 30, 40));
System.out.println(Collections.binarySearch(l, 30) + " "
                 + Collections.binarySearch(l, 25));

A list holds [40, 10, 30, 20] (unsorted). What can you rely on about Collections.binarySearch(list, 40)?

What is the result?

List<String> base = new ArrayList<>(Arrays.asList("a", "b"));
List<String> view = Collections.unmodifiableList(base);
base.add("c");
System.out.print(view.size() + " ");
view.add("d");

What does this fragment print?

List<Integer> l = new ArrayList<>(Arrays.asList(5, 0, 3, 1));
l.remove(1);
l.remove(Integer.valueOf(1));
System.out.println(l);

Does this fragment compile?

List<Integer> list = new LinkedList<>();
list.add(1);
list.push(2);
System.out.println(list);

A hospital emergency department must always treat the waiting patient with the highest severity next; patients arrive at any time. Which collection fits best?

A text editor needs an undo command: each edit is recorded, and undo reverses the most recent edit that has not been undone. Which structure fits best?

list is a LinkedList<Integer> with n elements. What is the running time of this loop?

long total = 0;
for (int i = 0; i < list.size(); i++) {
    total += list.get(i);
}

A student's code throws ConcurrentModificationException:

for (String s : names) {
    if (s.startsWith("tmp")) names.remove(s);
}

Explain why, and give two correct ways to remove those names.

A music player keeps a playlist of n songs. Compare ArrayList and LinkedList for (a) jumping to song number k, and (b) deleting the current song while walking through the playlist with an iterator. Give the Big-O cost of each and recommend one implementation if (a) is far more frequent.

After offer(5), offer(1), offer(4), offer(2), offer(3) a PriorityQueue<Integer> prints as [1, 2, 4, 5, 3]. Why is it not printed in sorted order, and how would you obtain the elements in sorted order?

Give three reasons to use ArrayDeque rather than java.util.Stack or LinkedList to implement a stack.

Write a method

static void reverseFirstK(Queue<Integer> q, int k)

that reverses the order of the first k elements of q and leaves the others in their original order. Use a Deque as a stack; assume 0 ≤ k ≤ q.size(). Example: [1, 2, 3, 4, 5] with k = 3 becomes [3, 2, 1, 4, 5].

Write a method

static int removeAdjacentDuplicates(List<Integer> list)

that removes every element equal to the element just before it, using an Iterator (no index loop, no removeIf), and returns how many elements were removed. Example: [1, 1, 2, 2, 2, 3, 1] becomes [1, 2, 3, 1] and the method returns 3.