Generics and Collections Flashcards
Declaring a class with generics
public class Crate {
private T contents;
public T emptyCrate() {
return contents;
}
}
T can be used throughout the class and when the class is instantiated then the T’s become the class object type you specify
How to call a method that uses generics
Two ways
methodName(“a string”) //Detects automatically
ClassName.methodName(“a string”) //Explicitly
Raw Collections
Collections that do not use generics
What goes wrong in this code?
class Dragon {}
class Unicorn { }
public class LegacyDragons {
public static void main(String[] args) {
List unicorns = new ArrayList();
unicorns.add(new Unicorn());
printDragons(unicorns);
}
private static void printDragons(List dragons) {
for (Dragon dragon: dragons) {
System.out.println(dragon);
}
}
}
The List unicorns doesn’t use generics, so when it adds a Unicorn, that’s fine but it sees it as an Object. So basically, it compiles because that’s technically legal to pass to printDragons, but the for loop then tries top cast the Unicorn element to Dragon, which causes a ClassCastException.
It will also give you a compiler warning, but still compile
What goes wrong with this code?
public class LegacyAutoboxing {
public static void main(String[] args) {
java.util.List numbers = new java.util.ArrayList();
numbers.add(5);
int result = numbers.get(0);
}
}
When the number 5 is added to the List, it is added just as an Object since there isn’t a type specified by generics. So when you try to store that value in an int, it can’t be unboxed how an Integer usually would be able to.
Unbounded Wildcard
Specified with a ?
public static void printList(List> list)
This indicates that the List could be of anything.
The difference here between just specifying List without generics, is that when we don’t use generics it will treat the list passed in as List, which could allow the wrong types of elements to be added.
Upper-bounded Wildcard
Specified with a ? extends className
public static void printList(List extends Number> list)
This means the List can be of Number itself, or any class that is a subclass of Number
Lower-bounded Wildcards
Specified with a ? super className
public static void printList(List super String> list)
This means that the List can be of String itself, or any class that is a superclass of String
Mutability of Lists declared with wildcards
With unbounded or upper-bounded, the Lists are immutable, meaning you cannot add anything to them.
With lower-bounded, you can add anything that is the lower-bound specified or a subclass of that lower-bound
Collection
A group of objects contained in a single object
List
An ordered collection of elements that allows duplicate entries. Elements in a list can be accessed by an int index.
Set
A collection that does not allow duplicate entries
Queue
A collection that orders its elements in a specific order for processing. A typical queue processes its elements in a first-in, first-out order, but other orderings
are possible.
Map
A collection that maps keys to values, with no duplicate keys allowed. The elements in a map are key/value pairs.
add()
Inserts a new element into the Collection and returns whether it was
successful.
boolean add(E element)
remove()
Removes a single matching value in the Collection and returns whether it was successful.
boolean remove(Object object)
Removes the element at the specified index
void remove(int index)
clear()
Discards all elements in the Collection
void clear()
contains()
Checks if a certain value is in the Collection
boolean contains(Object object)
Benefit of ArrayList
You can look up any element in constant time.
Adding or removing an element is slower than accessing an element.
This makes an ArrayList a good choice when you are reading more often than writing
Benefit of LinkedList
You can access, add, and remove from the
beginning and end of the list in constant time.
The tradeoff is that dealing with an arbitrary
index (not necessarily first or last) takes linear time.
This makes a LinkedList a good choice when you’ll be using it as Queue.
What should you use instead of Stack?
ArrayDeque
List method used to add an element at a specific index
void add(int index, E element)
List method to grab a specific element in the list
E get(int index)
List method to replace the element at a specific index
E set(int index, E e)
List method to find the position in the List that matches a specified element
//For first match int indexOf(Object o)
//For the last match int lastIndexOf(Object o)
Both return -1 if there is no match found
Benefit of HashSet
Adding elements and checking if an element is in the set are done in constant time
The tradeoff is that you lose the order in which you added the elements, but this is the case with sets usually, so if you care that much then don’t use a set ya dummy.
Benefit of TreeSet
The set is always in sorted order.
The tradeoff is that adding and checking if an element is present are done in O(logn)
TreeSet method
E lower(E e)
Returns the greatest element in the set that is
TreeSet method
E floor(E e)
Returns the greatest element in the set that is <=e, or null if there is no such element
TreeSet method
E ceiling(E e)
Returns the smallest element in the set that is >=e, or null if there is no such element
TreeSet method
E higher(E e)
Returns the smallest element in the set that is >e, or null if there is no such element
ArrayDeque
A double-ended queue that stores its elements in a resizable array
Like a LinkedList, but more efficient
ArrayDeque method
boolean add(E e)
Adds an element to the back of the queue and returns true or throws an exception
ArrayDeque method
E element()
Returns next element or throws an exception if empty queue
ArrayDeque method
boolean offer(E e)
Adds an element to the back of the queue and returns whether successful
ArrayDeque method
E remove()
Removes and returns next element or throws an exception if empty queue
ArrayDeque method
void push(E e)
Adds an element to the front of the queue
ArrayDeque method
E poll()
Removes and returns next element or
returns null if empty queue
ArrayDeque method
E peek()
Returns next element or returns null if
empty queue
ArrayDeque method
E pop()
Removes and returns next element or throws an exception if empty queue
HashMap
Stores keys in a hash table
Adding elements and retrieving the element by key both have constant time.
TreeMap
Stores keys in a sorted tree structure
Adding and checking if a key is present are both O(log n).
What is special about Map in this discussion?
It does not extend Collection
Map method
void clear()
Removes all keys and values from the map.
Map method
boolean isEmpty()
Returns whether the map is empty.
Map method
int size()
Returns the number of entries (key/value pairs) in the map.
Map method
V get(Object key)
Returns the value mapped by key or null if none is mapped.
Map method
V put(K key, V value)
Adds or replaces key/value pair. Returns previous value or null.
Map method
V remove(Object key)
Removes and returns value mapped to key. Returns null if none.
Map method
boolean containsKey(Object key)
Returns whether key is in map.
Map method
boolean containsValue(Object)
Returns value is in map.
Map method
Set keySet()
Returns set of all keys.
Collection values()
Returns Collection of all values.
Which of the data structures discussed cannot contain null elements?
TreeSet cannot contain null elements
TreeMap cannot contain null keys, but CAN contain null values
ArrayDeque cannot contain null elements
Comparable interface
public interface Comparable {
public int compareTo(T o);
}
Only contains the compareTo() method
compareTo() rules
The number zero is returned when the current object is equal to the argument to compareTo().
A number less than zero is returned when the current object is smaller than the argument to compareTo().
A number greater than zero is returned when the current object is larger than the argument to compareTo().
Comparator
A functional interface that you can use to sort a collection of objects by however you specify its compare() function.
You can define it in long form, (for example):
Comparator byWeight = new Comparator() {
public int compare(Duck d1, Duck d2) {
return d1.getWeight()—d2.getWeight();
}
};
Or as a lambda:
Comparator byWeight = (d1, d2) -> d1.getWeight()—d2.getWeight();
How to use a comparator to sort
Collections.sort(listname, byWeight);
What package is Comparable in? Comparator?
Comparable is in java.lang
Comparator is in java.util
What is the method in Comparable? Comparator?
Comparable has compareTo(T obj)
Comparator has compare(T obj1, T obj2))
Method References
A way to make the code shorter by reducing some of the code that can be inferred and simply mentioning the name of the method.
How can you shorten the following line of code using a method reference?
Comparator byWeight = (d1, d2) -> DuckHelper.compareByWeight(d1, d2);
Comparator byWeight = DuckHelper::compareByWeight;
How can you shorten the following line of code using a method reference?
String str = “abc”;
Predicate lambda2 = s -> str.startsWith(s);
Predicate methodRef2 = str::startsWith;
How can you shorten the following line of code using a method reference?
Predicate lambda3 = s -> s.isEmpty();
Predicate methodRef3 = String::isEmpty;
How can you shorten the following line of code using a method reference?
Supplier lambda4 = () -> new ArrayList();
Supplier methodRef4 = ArrayList::new;
How to use
boolean removeIf(Predicate super E> filter)
If we have a List of Strings, an example is
list.removeIf(s -> s.startsWith(“A”));
How to use
void replaceAll(UnaryOperator o)
List list = Arrays.asList(1, 2, 3);
list.replaceAll(x -> x*2);
System.out.println(list); // [2, 4, 6]
Note: The lambda may only take one argument because it is a UnaryOperator
How to loop through a Collection using a lambda or method reference
list. forEach(c -> System.out.println(c));
list. forEach(System.out::println);
How to insert a new key/value pair into a Map
Map mymap = new HashMap<>();
mymap.put(“My key”, “My value”);
Note: you can use putIfAbsent() if you want to make sure you don’t overwrite a value that is already in the map
merge()
Full Version:
merge(K key, V value, BiFunction super V,? super V,? extends V> remappingFunction)
Uses the BiFunction to make a decision on changing a the value for the specified key
Returns the result of the BiFunction
What happens if you call merge() on a key with a null value or a key that doesn’t exist?
It doesn’t call the BiFunction (this would cause a NullPointerException) and it just inserts the new value in question
What happens if you call merge() on a key and the BiFunction is called and returns null?
The key is removed from the map
