Chapter 3: Generics & Collections Flashcards
Lists (Review from OCA)
- ArrayList can contain objects, not primitives
- When underlying List is actually an array (e.g. from doing Arrays.asList(…)) then you can’t delete an element since you can’t remove element from an array, but you can change a value in the list and the underlying array changes value too
- To do a binary search you need to sort the List first. If not found value is -1 + -(position where it should be)
Type erasure
Java classes are compiled into one class file with Object references and all the necessary down casting from Object in the corresponding client code
Generic Interface
e.g. public interface Shippable {void ship(T t)}
How you can implement:
- Specify the generic type in the implementing class (e.g. ShippableImpl implements Shippable {void ship(Robot r)}
- Create a generic class e.g. class ShippableGeneric<u> implements Shippable<u> {...}</u></u>
- Or could not use generics at all and use Object</u></u>
Generic Methods
Specify the generic parameter before the return type. Note, it is still possible to pass in a raw list and Java won’t know to throw a compilation error due to type erasure. This can throw a RuntimeException
Unbounded wildcard
Unbounded wildcard: ?
List> indicates that it can be a list of anything
List is immutable with unbounded generic
Upper bound wildcard
List extends Number>
The list becomes logically immutable (i.e. you’re not allowed to add anything to the List, as Java doesn’t know what type it should be). (Although you can add null to the list and remove elements)
We can use extends even if the type is an interface
Lower bound
It allows you to safely add to the List knowing what the object will be.
Java collections
List: ordered collection of elements (allowing duplicates)
Set: collection (no duplicates and not ordered)
Queue: orders elements in a specific order for processing
Map: Maps keys to values with no duplicate key allowed. Note Map doesn’t implement Collection interface
Methods from Collection interface
add( E element): returns boolean if the addition was successful
remove (Object object): removes a single matching value and returns if it was successful. Also remove(int i) removing the value at the ith index.
isEmpty():
size();
clear():
contains(Object object): calls equals on each element
ArrayList
Resizable array: Good for reading values, not as fast when writing
LinkedList
Implements List & Queue. It’s good as you can access add and remove from the beginning and end in constant time. But dealing with an arbitrary index takes linear time. Uses Nodes to point to next item.
Stack
Extends Vector (it’s very old) You can add or remove elements from the top of the stack. Should use ArrayDeque now!
List methods
void add(E element) adds to end void add(int index, E element) add at index and shifts the rest by 1 int indexOf(Object obj) returns -1 if element not found int lastIndexOf(Obj obj) same as above E set (int index, E e) replaces element and returns original
HashSet
Stores values in a HashMap, so you can use hashCode() method to retrieve efficiently. Adding and retrieving are both constant time, but you lose the ordering
TreeSet
Set is always in sorted order. But efficiency is O(log n)
Implements NavigableSet.
NavigableSet methods
E lower (E e) returns greatest < e or null E floor (E e) returns greatest <= e or null E ceiling (E e) returns smallest >= e or null E higher (E e) returns smallest > e or null
ArrayDeque
You can insert and remove elements from the front or back. ArrayDeque stores elements in a resizable array and is more efficient than a LinkedList bool add(E e) Adds an element to the back of the queue E element() Returns next element or throws Exception bool offer(E e) Adds an element to the back of the queue and returns if it was successful E remove() Removes and returns next element void push(E e) Adds an element to the front of the Queue E poll() Removes and returns next element or null E peek() Returns next element or null if empty queue E pop() Removes and returns next element or throws Exception
HashMap
Stores keys in a hash table, so can use hashCode to retrieve values more efficiently
LinkesHashMap
Can preserve the order that things were added
TreeMap
Stores in a sorted tree structure
Keys are sorted in order
Map methods
Set keySet() Collection values() containsKey() containsValue() Note: Map doesn't implement Collection, so doesn't have the method .contains()
Collections allowing null
Most do, except anything which uses .compareTo(), which is anything starting with Tree e.g. TreeSet (although TreeMap can have null values, just not null keys)
ArrayDeque also not allowed null since it has a special meaning for poll()
Comparable interface
1 method compareTo()
Returns 0 if equal,
< 0 if current is smaller
> 0 is current is larger
Comparator
Functional interface with 1 method compare()
Method references
Class::method returns a functional interface. Java infers the version of the method by looking at what it is supposed to return. Note you can only use when there are no references to other objects. Can use a constructor reference as well e.g. ArrayList::new
Map merge
merge(Key, Value, BiFunction). BiFunction here is for the old and the new value. Value here is the new value that you might set it as.
Helps us decide between two values. If you want to update values in a map, but want additional logic on what the value should be. If there are nulls, it just uses the new value. If the result of the merge is null, it will remove the key.
