Wildcards and Generics

Question 1

Fill in the blank:
public static <T> void selectionSort(T[] arr, Comparator <\_\_\_\_> comp){
//code; overriding the compare() method
}</T>

Answer 1

public static <T> void selectionSort(T[] arr, Comparator<? super T> comp){}</T>

Question 2

Fill in the blank:
public static <_____> void selectionSort(T[] arr){
//code; overriding the compareTo() method
}

Answer 2

public static <T extends Comparable<? super T» void selectionSort(T[] arr){
//code; overriding the compareTo() method
}

Question 3

Fill in the blank:
If T is a type parameter and you write Comparator<T>, you probably actually want \_\_\_\_\_.</T>

Answer 3

If T is a type parameter and you write Comparator<T>, you probably actually want Comparator <? super T></T>

Question 3

Fill in the blank:
If T is a type parameter and you write Comparator<T>, you probably actually want \_\_\_\_\_.</T>

Answer 3

If T is a type parameter and you write Comparator<T>, you probably actually want Comparator <? super T></T>

Question 4

Fill in the blank:
If T is a type parameter and you write “T extends Comparable<T>”, you probably actually want \_\_\_\_.</T>

Answer 4

If T is a type parameter and you write “T extends Comparable<T>”, you probably actually want “<T extends Comparable<? super T>>”</T>

Question 5

What are Iterator<E>'s three key methods?</E>

Answer 5

1. boolean hasNext()
2. E next()
3. void remove()

Question 6

What are Collection<E>'s five key methods?</E>

Answer 6

1. boolean add(E item)
2. int size()
3. boolean contains(Object obj)
4. boolean remove(Object obj)
5. Iterator<E> iterator()</E>

Question 7

Iterator’s remove() may only be called…

Answer 7

…after at least one call to Iterator’s next().

Question 8

Iterator’s remove() does what?

Answer 8

It removes the element returned by the last call to Iterator’s next().

Question 9

If Iterator’s remove() is called before another call to Iterator’s next(), what happens?

Answer 9

An IllegalStateException is thrown.

Question 10

An Iterator needs these two things in order to function:

Answer 10

1. int cursor
2. boolean canRemove

Question 11

Iterator’s next() function does what three things?

Answer 11

1. Returns the item at the CURSOR position in DATA
2. Increments CURSOR
3. Sets canRemove to true

Question 12

Iterator’s hasNext() will return true if CURSOR
< ?????

Answer 12

Iterator’s hasNext() will return true if CURSOR < the Collection’s SIZE.

Question 13

Iterator’s remove() function does what three things?

Answer 13

1. Shifts elements after CURSOR down by one and decrements Collection’s SIZE
2. Decrements CURSOR
3. Sets canRemove to false

Question 14

The three main components of a node in a doubly linked list are:

Answer 14

1. Data
2. Pointer to previous node
3. Pointer to next node

Question 15

LinkedIterator keeps track of two nodes at once. They are:

Answer 15

1. Cursor node
2. pending node - named this because this node’s removal is pending, is the predecessor of cursor

Question 16

After a remove(), LinkedIterator’s pending node is set to:

Answer 16

null. This indicates that a remove will not be allowed until another next() is called.

Question 17

Runtime of get(i) for linked list

Answer 17

O(n) - must traverse list to find position

Question 18

Runtime of get(i) for array list

Answer 18

O(1)

Question 19

Runtime of contains(item) for linked list

Answer 19

O(n)

Question 20

Runtime of contains(item) for array list

Answer 20

O(n)

Question 21

Runtime of size() for linked list

Answer 21

O(1)

Question 22

Runtime of size() for array list

Answer 22

O(1)

Question 23

Runtime of add(item) for linked list

Answer 23

O(1) - adds item at end

Question 24

Runtime of add(i, item) for linked list

Answer 24

O(n) - we must traverse the list to find the position

Question 25

Runtime of add(i, item) for array list

Answer 25

O(n) - we must shift elements in order to add in the middle of the array

Question 26

Runtime of remove(item) for linked list

Answer 26

O(n)

Question 27

Runtime of remove(item) for array list

Answer 27

O(n)

Question 28

Runtime of add(item) for ListIterator for linked list

Answer 28

O(1)

Question 29

Runtime of add(item) for ListIterator for array list

Answer 29

O(n) - must shift elements to add/remove

Question 30

Runtime of remove(item) for ListIterator for linked list

Answer 30

O(1)

Question 31

Runtime of remove(item) for ListIterator for array list

Answer 31

O(n)