LinkedList

Question 1

FIFO

Answer 1

first in, first out - a queue: first in line gets into theater first; a call center, etc

Question 2

LIFO

Answer 2

last in, first out - like a stack of plates

Question 3

removing head/first element from LinkedList vs ArrayList

Answer 3

LinkedList: O(1)
ArrayList: O(n)

Question 4

if the list needs to be sorted…

Answer 4

…use an ArrayList - sorting accesses items by index

Question 5

examples of LinkedList

Answer 5

list of orders to fultill FIFO
list of customers to contact
list of successful and failed calls (??)
list of books to download
list of categories (almost always printed together) (??)

Question 6

examples of ArrayList

Answer 6

list of items in an order - customer may want to access or edit any item
list of names to sort - sorting accesses items by index
instructions - made need to interrupt and start over
list of lines in a file - editing often accesses lines by index

Best when manipulating the ends of a list

Question 7

the one thing array is better suited for

Answer 7

get(index) - O(1) for array; O(n) for linkedlist

Question 8

Deque interface

Answer 8

==”double ended” queue
pronounced “deck”
LinkedList implements methods from the Deque interface

Question 9

end-related methods

Answer 9

addFirst()
addLast()
removeFirst()
removeLast()

Question 10

linkedlist descendingIterator()

Answer 10

LinkedList list = new LinkedList<>();
list.add("A");
list.add("B");
list.add("C");
Iterator x = list.descendingIterator();

while(x.hasNext()) {
System.out.println(“value is: “ + x.next());
}

Question 11

which data structures have a backing array

Answer 11

ArrayList, HashMap, HashSet

initialCapacity is 16

Question 12

which data structure for DNS is best?

Answer 12

HashMap since we need to get any element in O(1) time.

HashSet cannot retrieve a single item, can only say whether the structure contains the item.

Question 13

can HashSet have a key-value pair?

Answer 13

no, HashSet takes in only 1 generic: HashSet where E is an object

Question 14

in a HashMap hashExample, what happens:
hashExample.add(blue, 3);
hashExample.add(blue, 5);

Answer 14

The key-value pair “blue, 5” overwrites “blue, 3”. If both values should be saved, the structure should be HashMap.
–>note that HashMap is a kind of Set, where the key cannot hold duplicate values. In HashSet however, we can only hold “keys” not a meaning or value associated with the key.

Question 15

does HashMap preserve insertion order?

Answer 15

no, HashMap is a collection of Key and Value but HashMap does not give guaranty that the insertion order will preserve
note: LinkedHashMap retains insertion order
TreeMap can sort the keys

Question 16

Use case: we need to keep track of the completeness progress of a stamp collection. We want to know which Stamps we have at least one of in our collection.

Answer 16

Since we need to track unique values of Stamp, and can use the contains method oa a HashMap (with O(1) runtime), we could use a HashMap. However, it may be simpler to use a HashSet (provided we don’t need to know how many stamps we have, just whether we have at least 1).
If we were interested in anything related to inventory, we’d need a HashMap - key is Stamp accessed in O(1) time, and value is count, or other information holding object.

Question 17

how to add to a HashMap?

how to add to a HashSet?

Answer 17

hashMap.put(myKey, myValue); –>note, this is different than add() because a HashMap puts another entry in the designated bucket (ie the backing array index location from the hash of the key) if there is a collision.
hash(key) = index

hashSet.add(setItem); –> note, if setItem is added twice, the second time it’s simply not added (and returns false)

fun fact: hashSet.contains(setItem) returns true if set contains item, while hashSet.add(setItem) returns false if set contains item.

Question 18

is HashMap a collection?

Answer 18

No.
That explains why we use the method “put(key, value)” to add a pair to the HashMap - the underlying code will append to the list at the hash-index, which is different that the simple “add”.

This also explains why HashMap does not have a toArray() method, while HashSet and LinkedList both have this method.

Question 19

why is it important to have “good” hash function for the HashMap?

Answer 19

The implementation of HashMap provides constant-time performance for the basic opertions (get and put), assuming the hash function disperses the elements properly among the buckets.
Iteration over collections at the index requires time proportional to the capacity of the HashMap instance and the quality of the hash function.
We just use Java: equals() and hashCode().