Midterm Review Flashcards
Which of the JCF interfaces would be the most useful if we want to store a collection of students
enrolled in COMP2402 so that we can quickly check if a student is enrolled in COMP2402?
Set
What if we also want to be able to quickly output a list of students, sorted by (lastname,firstname)?
SortedSet
What if, in addition, we also want to store some auxiliary information (e.g., a mark) with each student?
SortedMap
A Bag is like a Set except that equal elements can be stored more than once. Which of the following
is best suited to implement a Bag<T>?</T>
b or c depending on behaviour
The running time of the methods get(i) and remove(i) for an ArrayList are?
O(1) and O(1 + size() − i), respectively
The running time of the methods get(i) and remove(i) for a LinkedList are?
O(1 + min{i, size() − i}) and O(1 + min{i, size() − i}), respectively
public static void insertAtBack(List<Integer> l, int n) {
for (int i = 0; i < n; i++) {
l.add(new Integer(i));
}
}
The above method is</Integer>
about the same speed independent of whether l is an ArrayList or a LinkedList
public static void frontGets(List<Integer> l, int n) {
for (int i = 0; i < n; i++) {
l.get(0);
}
}
The above method is</Integer>
about the same speed independent of whether l is an ArrayList or a LinkedList
public static void randomGets(List<Integer> l, int n) {
Random gen = new Random();
for (int i = 0; i < n; i++) {
l.get(gen.nextInt(l.size()));
}
}
The above method is</Integer>
much faster when l is an ArrayList
public static void insertAtFront(List<Integer> l, int n) {
for (int i = 0; i < n; i++) {
l.add(0, new Integer(i));
}
}
The above method is</Integer>
much faster when l is a LinkedList
public static void insertInMiddle(List<Integer> l, int n) {
for (int i = 0; i < n; i++) {
l.add(new Integer(i));
}
for (int i = 0; i < n; i++) {
l.add(n/2+i, new Integer(i));
}
}
The above method is</Integer>
about the same speed independent of whether l is an ArrayList or a LinkedList
public static void insertInMiddle2(List<Integer> l, int n) {
for (int i = 0; i < n; i++) {
l.add(new Integer(i));
}
ListIterator<Integer> li = l.listIterator(n/2);
for (int i = 0; i < n; i++) {
li.add(new Integer(i));
}
}
The above method is</Integer></Integer>
much faster when l is a LinkedList
Recall that an ArrayStack stores n elements in a backing array a at locations a[0],. . . ,a[n-1]:
public class ArrayStack<T> extends AbstractList<T> {
T[] a;
int n;
...
}
Also recall that, immediately after the backing array a is resized by grow() or shrink it has a.length =
2n.
When adding an element, the ArrayStack grows the backing array a if it is full, i.e, if a.length = n.
If are currently about to grow the backing array a, what can you say about the number of add() and
remove() operations (as a function of the current value of n) since the last time the ArrayStack was
resized?</T></T>
At least n/2 add() operations have occurred since then
From the previous two questions, what can you conclude about the total number of elements copied
by grow() and shrink() if we start with an empty ArrayStack and perform m add() and remove
operations.
At most 2m elements are copied by grow() and shrink()
Recall that we shrink the backing array a when 3n < a.length. If we are currently about to shrink
the backing array a, what can you say about the number of add() and remove() operations since the
last time the ArrayStack was resized?
At least n/2 remove() operations have occurred since then
Recall that an ArrayDeque stores n elements at locations a[j], a[(j+1)%a.length],. . . ,a[(j+n-1)%a.length]:
public class ArrayDeque<T> extends AbstractList<T> {
T[] a;
int j;
int n;
...
}
What is the amortized running time of the add(i,x) and remove(i) operations?</T></T>
O(1 + min{i, n − i})
Recall that a DualArrayDeque implements the List interface using two ArrayStacks:
public class DualArrayDeque<T> extends AbstractList<T> {
ArrayStack<T> front;
ArrayStack<T> back;
...
}
In order to implement get(i) we need to get it from the ArrayStack, front or back. We can express
this as</T></T></T></T>
Either (b) or (c) depending on the value of i and front.size()
If a RootishArrayStack has 10 blocks (so b.size() = 10), then how many elements can it store?
55
In a RootishArrayStack, a call to get(13) will return
blocks.get(4)[3]
Recall our implementation of a singly-linked list (SLList):
protected class Node {
T x;
Node next;
}
public class SLList<T> extends AbstractList<T> {
Node head;
Node tail;
int n;
...
}
Consider how to implement a Queue as an SLList. When we enqueue (add(x)) an element, where
does it go? When we dequeue (remove()) an element, where does it come from?</T></T>
We enqueue (add(x)) at the tail and we dequeue (remove()) at the head
Consider how to implement a Stack as an SLList. When we push an element where does it go? When
we pop an element where does it come from?
We push at the head and we pop at the head
Using the best method you can think of, how quickly can we find the ith node in an SLList?
in O(1 + min{i, n · (n − i − 1)}) time
Recall our implementation of a doubly-linked list (DLList):
protected class Node {
Node next, prev;
T x;
}
public class DLList<T> extends AbstractSequentialList<T> {
protected Node dummy;
protected int n;
...
}
6
Explain the role of the dummy node. In particular, if our list is non-empty, then what are dummy.next
and dummy.prev?</T></T>
dummy.next is the first node in the list and dummy.prev is the last node in the list
Consider the correctness of the following two methods that add a node u before the node p in a DLList.
protected Node add(Node u, Node p) {
u.next = p;
u.prev = p.prev;
u.next.prev = u;
u.prev.next = u;
n++;
return u;
}
protected Node add(Node u, Node p) {
u.next = p;
u.next.prev = u;
u.prev = p.prev;
u.prev.next = u;
n++;
return u;
}
first method
What is the running-time of add(i,x) and remove(i) in a DLList?
O(1 + min{i, size() − i}) and O(1 + min{i, size() − i}), respectively
