Collections Flashcards
What is the collection framework hierarchy, and how do they relate to each other>
What is List interface in collection framework?
The collection framework provides a core set of interfaces to define different collection behaviors. One of the core interfaces is the List interface. A List is a collection where its elements are ordered in a sequence. Lists allow us to have duplicate elements and fine-grain control over where elements are inserted in the sequence. Like arrays, the position of a List is known as the index and is 0 based. Unlike arrays, which have a static size, Lists are dynamically sized.
The collection framework provides many List implementations but we’ll focus on the ArrayList and LinkedList. The ArrayList is the overall preferred implementation for most use cases but the LinkedList performs better than an ArrayList if your program mostly inserts and deletes elements.
List<Integer> intList = new ArrayList<>(); // Empty `List` intList.add(4); // 4 intList.add(6); // 4, 6 intList.add(3); // 4, 6, 3 intList.set(1, 3); // 4, 3, 3 int a = intList.get(2); // a = 3 int b = intList.indexOf(3); // b = 1 List<Integer> subIntList = intList.subList(1,3); // subIntList -> 3, 3
How can we iterate through a list?
for (Integer number: intList) {
System.out.println(number);
}What are the Set interface and its implementations?
Another core interface provided by the collection framework is the Set interface. A Set is a collection of unique elements and all of its methods ensure this stays true.
- The HashSet implementation has the best performance when retrieving or inserting elements but cannot guarantee any ordering among them.
- The TreeSet implementation does not perform as well on insertion and deletion of elements but does keep the elements stored in order based on their values (this can be customized).
- The LinkedHashSet implementation has a slightly slower performance on insertion and deletion of elements than a HashSet but keeps elements in insertion order.
How do we create and use HashSet?`
Set<Integer> intSet = new HashSet<>(); // Empty set intSet.add(6); // true - 6 intSet.add(0); // true - 0, 6 (no guaranteed ordering) intSet.add(6); // false - 0, 6 (no change, no guaranteed ordering) boolean isNineInSet = intSet.contains(9); // false boolean isZeroInSet = intSet.contains(0); // true
What is a queue interface?
The Queue core interface in the collection framework, is a collection that stores elements that can be accessed at some later point to process (like waiting in line at the bank teller). A Queue accesses elements in a (usually) First In First Out (FIFO) manner where elements are inserted at the tail (back) of the collection and removed from the head (front).
What are the methods of queue interface?
A Queue has two types of access methods for inserting, removing, and getting but not removing the head of the Queue.
The following methods throw an exception when:
add() - there is no space for the element remove() - there are no elements to remove element() - there are no elements to get
The following methods return a special value:
offer() - false there is no space for the element poll() - null there are no elements to remove peek() - null there are no elements to get
The methods that return a special value should be used when working with a statically sized Queue and the exception throwing methods when using a dynamic Queue.
What are the important implementations of queue interface?
LinkedList and PriorityQueue.
LinkedList be used as a List implementation and it’s also perfect when needing a basic Queue implementation. Being able to use a LinkedList as both a List and Queue implementation is a perfect example of the compatibility within the collection framework.
The PriorityQueue ensures the top element is the smallest relative to the data type’s natural ordering (or some custom comparison algorithm you provide).
How do we use queues?
Queue<String> stringQueue = new LinkedList<>();
stringQueue.add("Mike"); // true - state of queue -> "Mike"
stringQueue.offer("Jeff"); // true - state of queue -> "Mike", "Jeff"
String a = stringQueue.remove() // Returns "Mike" - state of queue -> 1
String b = stringQueue.poll() // Returns "Jeff" - state of queue -> empty
String c = stringQueue.peek() // Returns null
String d = stringQueue.element() // Throws NoSuchElementExceptionHow do we iterate over queues?
// Assuming `stringQueue` has elements -> "Mike", "Jack", "John"
for (String name: stringQueue) {
System.out.println(name);
}
// OUTPUT TERMINAL: "Mike", "Jack", "John"
One thing to note about a PriorityQueue is that an enhanced for-loop (or Iterator) makes no guarantee in the ordering of elements after the head.
What is the Deque collection interface?
A Deque is a collection that allows us to manipulate elements from both the front and end of the collection.
What are the methods and exceptions of Deque interface?
The Deque interface has two types of methods for manipulating the front and back of the collection.
The following methods throw an exception when:
- addFirst(), addLast() - there is no space to add an element.
- removeFirst(), removeLast() - there is no element to remove.
- getFirst(), getLast() - there is no element to get.
The following methods return a special value:
- offerFirst(), offerLast() - false when there is no space to add an element. // returns boolean
- pollFirst(), pollLast() - null when there is no element to remove.
- peekFirst(), peekLast() - null when there is no element to get.
What are the implementations of Deque class?
A Deque has many implementations and we’ll focus on the LinkedList and ArrayDeque implementations. The LinkedList, although not the most optimized, is flexible enough to not only be used as a List and Queue but also a Deque. The ArrayDeque is the preferred implementation when needing to manipulate elements at the front and end of a collection.
A sample implementation of Deque interface?
Deque<String> stringDeque = new LinkedList<>();
stringDeque.addFirst("A"); // Front -> "A" <- end
stringDeque.offerFirst("B"); // Return `true` - front -> "B", "A" <- end
stringDeque.offerLast("Z"); // Returns `true` - front -> "B", "A", "Z" <- end
String a = stringDeque.removeFirst() // Returns "B" - front -> "A", "Z"
String b = stringDeque.pollLast() // Returns "Z" - front -> "A" <- back
String c = stringDeque.removeLast() // Returns "A" - empty deque
String d = stringDeque.peekFirst() // Returns null
String e = stringDeque.getLast() // Throws NoSuchElementExceptionHow do we iterate over Deque?
We can iterate Deque from front to back using an enhanced for-loop and we can use the descendingIterator() method and use the Iterator returned to go from back to front.
// Assuming `stringDeque` has elements front -> "Mike", "Jack", "John" <- back
Iterator<String> descItr = stringDeque.descendingIterator();
while(descItr.hasNext()) {
System.out.println(descItr.next());
}
// OUTPUT TERMINAL: "John", "Jack", "Mike"
What are the some other collection methods?
addAll() - receives a Collection argument and adds all the elements.
isEmpty() - return true if the collection is empty, false otherwise.
iterator() - returns an Iterator over the collection.
size() - returns the number of elements in the collection.
stream() - returns a Stream over the elements in the collection.
toArray() - returns an array with all elements in the collection.
What is a map?
Map defines a generic interface for an object that holds key-value pairs as elements. The key is used to retrieve (like the index in an array or List) some value. A key must be unique and map to exactly one value. A Map can be thought of as a Java interface for a Hash Table data structure.
HashMap?
The HashMap defines no specific ordering for the keys and is the most optimized implementation for retrieving values
LinkedHashMap?
The LinkedHashMap keeps the keys in insertion order and is slightly less optimal than the HashMap.
TreeMap?
The TreeMap keeps keys in their natural order (or some custom order defined using a Comparator). This implementation has a significant performance decrease compared to HashMap and LinkedHashMap but is great when needing to keep keys sorted.
What methods do we use to access elements in a map?
put(): Sets the value that key maps to. Note that this method replaces the value key mapped to if the key was already present in the Map.
get(): Gets, but does not remove, the value the provided key argument points to if it exists. This method returns null if the key is not in the Map. Let’s see how we can use them:
Map<String, String> myMap = new HashMap<>();
myMap.put("Hello", "World") // { "Hello" -> "World" }
myMap.put("Name", "John") // { "Hello" -> "World" }, { "Name" -> "John" }
String result = myMap.get("Hello") // returns "World"
String noResult = myMap.get("Jack") // return `null`
Iterating over a map?
// Given a map, `myMap`, with the following key-value pairs { "Hello" -> "World" }, { "Name" -> "John"}
for (Map.Entry<String, String> pair: myMap.entrySet()){
System.out.println("key: "+pair.getKey()+", value: "+pair.getValue());
}
// OUTPUT TERMINAL:
// key: Name, value: John
// key: Hello, value: World
