What does the List ADT (for example the MyList<E> interface) specify?
A MyArrayList starts with capacity 4 and doubles its array whenever it is full. After 9 calls of add(e) on a new list, what is the capacity, and how many element copies have the resizes made in total?
Why is add(e) at the end of a doubling array list said to take amortized O(1) time?
A student's ensureCapacity grows the array by 10 slots each time it is full (data.length + 10) instead of doubling. What is the total cost of n appends to an empty list?
A buggy add(1, "X") is applied to an array list holding A, B, C, D. What does the last line print?
String[] data = {"A", "B", "C", "D", null};
int size = 4, index = 1;
for (int i = index; i < size; i++) {
data[i + 1] = data[i];
}
data[index] = "X";
System.out.println(Arrays.toString(data));
A student's MyArrayList.remove(int index) shifts the later elements left and does size--, but never sets the old last slot to null. What is the consequence?
What happens when you compile this class?
public class MyArrayList<E> {
private E[] data;
public MyArrayList() {
data = new E[10];
}
}
What is the time complexity of get(i) for a MyArrayList and for a MyLinkedList of n elements?
A student tries to add a node with value 0 at the front of the list 1 → 2. What does printing at most 5 values from head show?
Node head = new Node(1);
head.next = new Node(2);
Node n = new Node(0);
head = n;
n.next = head;
a refers to the first node of the list 1 → 3 → 5. What does printing at most 6 values from a show?
Node ins = new Node(2);
a.next = ins;
ins.next = a.next;
Given these methods of a singly linked list with head, tail and size, what does printing the list from head show after addLast(7); removeFirst(); addLast(9); on an empty list?
void addLast(int v) {
Node n = new Node(v);
if (tail == null) { head = tail = n; }
else { tail.next = n; tail = n; }
size++;
}
int removeFirst() {
int v = head.val;
head = head.next;
size--;
return v;
}
In a singly linked list with both head and tail references, which operation takes O(n) time?
In a doubly linked list, p refers to a node that is neither the first nor the last. Which statements unlink p from the list?
head refers to the list 1 → 2 → 3 → 4, and show(x) prints the values reachable from node x. What does this print?
Node prev = null, cur = head;
while (cur != null) {
Node next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
System.out.println(show(prev) + " " + show(head));
What happens when you compile this list class?
public class MyLinkedList<E> implements Iterable<E> {
private static class Node<E> { E val; Node<E> next; }
private Node<E> head;
private static class ListIter<E> implements Iterator<E> {
private Node<E> cur = head;
public boolean hasNext() { return cur != null; }
public E next() { E v = cur.val; cur = cur.next; return v; }
}
public Iterator<E> iterator() { return new ListIter<E>(); }
}
What must MyLinkedList<E> do so that for (E e : list) compiles?
Using the ArrayStack of this chapter, what does this print?
ArrayStack<Integer> s = new ArrayStack<>();
StringBuilder out = new StringBuilder();
s.push(4); s.push(7);
out.append(s.pop()).append(' ');
s.push(1); s.push(9);
out.append(s.pop()).append(' ');
out.append(s.peek()).append(' ');
s.push(3);
out.append(s.pop()).append(' ').append(s.pop());
System.out.println(out);
You implement a stack with a singly linked list. Where should the top of the stack be, and why?
A circular-array queue (front, size, enqueue at (front + size) % length) has capacity 5 and starts empty. After the operations below, what does the array contain, and what is front?
q.enqueue(10); q.enqueue(20); q.enqueue(30); q.enqueue(40);
q.dequeue(); q.dequeue();
q.enqueue(50); q.enqueue(60); q.enqueue(70);
In a circular-array queue with fields data, front and size, at which index does enqueue store the new element?
A circular queue keeps only front and rear indices (no size) and uses every slot of the array. What problem arises?
A full circular queue has capacity 4, front = 2, and data = [E, F, C, D] (queue order C, D, E, F). Its resize() does data = Arrays.copyOf(data, 8); and changes nothing else. What is wrong?
You implement a queue with a singly linked list that has head and tail. Which choice makes both operations O(1)?
A queue is stored in a plain array: enqueue writes at data[size], and dequeue returns data[0] and shifts all other elements one place left. What is the cost of dequeue?
Which operation is O(1) on a doubly linked list with head and tail but O(n) on MyArrayList?
Benchmarks often show ArrayList beating LinkedList even when both do the same number of O(1) operations (e.g. appending 10 million elements). What is the main reason?
Explain why appending to a doubling array list costs O(1) amortized even though some appends cost O(n). Why does growing by a fixed 100 slots not give the same result?
In a singly linked list with head, tail and size, a student's removeFirst is head = head.next; size--;. Describe an operation sequence that exposes the bug, what goes wrong, and the fix.
Compare a stack implemented on an array with a stack implemented on a singly linked list: where is the top in each, what are the costs of push and pop, and name one advantage of each.
Why is a linked list's iterator usually written as a private inner (non-static) class, while its Node is a private static nested class? What state does the iterator need?
Write public E remove(int index) for the singly linked MyLinkedList<E> of this chapter (fields head, tail, size; methods removeFirst() available). It returns the removed element and throws IndexOutOfBoundsException for a bad index. Keep tail correct.
The circular-array queue of this chapter has fields E[] data, int front and int size. Write the private void resize() that doubles the capacity while keeping the queue order.