Term
| Big O of indexOf() in ArrayList |
|
Definition
| O(n) because you loop through the list of n items |
|
|
Term
| Big O of LinkedList, add to front |
|
Definition
| O(1), only have to change newNode.next pointer and head pointer |
|
|
Term
| Big O of ArrayList, add to front |
|
Definition
| O(n), memory is contiguous, you must shift elements over |
|
|
Term
| Big O of ArrayList set element i |
|
Definition
|
|
Term
| Big O of LinkedList set element i |
|
Definition
| O(n), you have to follow the next pointers to get to the ith spot |
|
|
Term
| Big O of ArrayList add (append) |
|
Definition
O(1)
Amortized cost is constant because resizing is rare |
|
|
Term
| For a linked list implementation, what data members do you have? Inner class? (3) |
|
Definition
1) The value of the linked list. Could be any data type.
2) The next pointer
3) Class Node |
|
|
Term
| Add an element to the front of a linked list (3) |
|
Definition
1) Create a new Node
2) Point new Node to head
3) Head = new Node |
|
|
Term
| Adding an element to the end of a linked list (3) |
|
Definition
1) Create new Node
2) Point tail at new Node
3) Tail = new Node |
|
|
Term
| Insert a node into a sorted linked list (7) |
|
Definition
1) Create new Node
2) previous = head, current = head
3) while new Node's value is less than current's value:
4) previous = current
5) current = current.next
6) Point new Node at current
7) Point previous at new Node |
|
|
Term
| Remove the first occurrence of a certain value from a linked list (6) |
|
Definition
1) Node previous = head
2) Node current = head
3) While value of current does not equal target value:
4) previous = current
5) current = current.next
6) previous.next = current.next |
|
|
Term
| Suppose that 20 hash entries were entered in the 10-bucket Hashmap, and later you perform a get() on all 20. Estimate how many key comparisons you would need for the 20 gets? Besides comparing keys, what other processing do you do when you do a get? (3) |
|
Definition
1) Min 20
2) Max 20 + 19 + 18 + ... + 1
3) Amortized 30 |
|
|
Term
|
Definition
| When a function is defined in terms of itself |
|
|
Term
| What is an advantage of recursion? |
|
Definition
| Breaks a problem down into smaller and smaller sub-problems |
|
|
Term
|
Definition
| The branch in which there is no recursive call |
|
|
