Learn about collections and the Collection Framework in Java.

Collections: Lesson

The last of the core interfaces in the collections framework is the `Deque` interface (pronounced "Deck"). A deque (short for "double-ended queue") is a type of queue that allows us to access elements from the front and the back of the queue.

The `Deque` interface has two types of methods for manipulating the front and back of the collection.

The following are some of the available methods and the exceptions they throw:
- `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.
- `pollFirst()`, `pollLast()` - `null` when there is no element to remove.
- `peekFirst()`, `peekLast()` - `null` when there is no element to get.

A `Deque` has many implementations, but 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`](https://www.codecademy.com/resources/docs/java/queue?page_ref=catalog), but also a `Deque`. The `ArrayDeque` is the preferred implementation when needing to manipulate elements at the front and back of a collection. 

Let's look at an `ArrayDeque` implementation of a `Deque`:

```java
Deque<String> stringDeque = new ArrayDeque<>();
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 NoSuchElementException
```
In the example above, we:
- Called `addFirst()`, `offerFirst()`, and `offerLast()` to add elements. Note that the `offer()` methods return a boolean.
- Called `removeFirst()`, `pollLast()`, and `removeLast()` to remove elements.
- Called `peekFirst()` and `getLast()` to get but not remove the element at the front and back of deque respectively.

If we iterate through a `Deque` using an enhanced for-loop, the elements would be processed from front to back like a standard `Queue`. However, we can also iterate through a `Deque` from front to back by using an [`Iterator`](https://www.codecademy.com/resources/docs/java/iterator?page_ref=catalog) from the `descendingIterator()` method and a while-loop like so:

```java
// Assuming `stringDeque` has elements front -> "Mike", "Jack", "John" <- back

Deque<String> stringDeque = new ArrayDeque<>();
stringDeque.addLast("Mike");
stringDeque.addLast("Jack");
stringDeque.addLast("John");

Iterator<String> iterator = stringDeque.descendingIterator();

while(iterator.hasNext()) {
  System.out.println(iterator.next());
}
// OUTPUT TERMINAL:  "John", "Jack", "Mike"
```



Let's practice creating a `Deque` and iterating through it.


Deque

Previously, we saw the collections framework hierarchy and how [`Collection`](https://www.codecademy.com/resources/docs/java/collection?page_ref=catalog) is the root of it. There exists another interface that didn't quite fit into that hierarchy but is an extremely important part of the collection framework: the `Map`.

[`Map`](https://www.codecademy.com/resources/docs/java/map?page_ref=catalog) defines a generic interface for an object that holds key-value pairs as elements. The _key_ is used to retrieve some value (like the index in an array or `List`). A key must be unique and map to exactly one value. There are many implementations of `Map`, but we'll focus on the [`HashMap`](https://www.codecademy.com/resources/docs/java/hashmap?page_ref=catalog) implementation. 

The `HashMap` defines no specific ordering for the keys and is the most optimized implementation for retrieving values. This is Java's implementation of a [hash table](https://www.codecademy.com/resources/docs/general/data-structures/hash-table?page_ref=catalog). 

A `Map` has the following methods for accessing its elements:

`put()`: Sets the value that a key maps to. Note that this method replaces the value a 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:
```java
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`
```
In the example above, we:
- Created a `Map` reference that maps a `String` key to a `String` value using the `HashMap` implementation. Note that a `Map` needs a type argument for the key and value.
- Added key-value pairs to `myMap` using `put()` where the first argument is the key and the second is the value the key maps to.
- Retrieved the value the key "Hello" maps to using `get()`. The `String` "World" is returned since the key "Hello" exists. `get()` returns `null` because the key "Jack" does not exist.

We can iterate over a `Map` with an enhanced `for-loop` like so:
```java
// Given a map, `myMap`, with the following key-value pairs { "Hello" -> "World" }, { "Name" -> "John"}
for (String s: myMap.keySet()){
  System.out.println("key: "+s+", value: "+myMap.get(s));
}
// OUTPUT TERMINAL:
// key: Name, value: John
// key: Hello, value: World
```
In the example above, we:
- Called `keySet()` to return the `Set` of the keys contained in this `HashMap`.
- Iterated through the set of keys of this map. 
- Called `myMap.get(s)` to get the value associated with key `s`. 

Let's practice working with `Map`. 


Great job learning about the collections framework! In this lesson we've covered:
- The collection framework hierarchy and its core interfaces.
- The root [`Collection`](https://www.codecademy.com/resources/docs/java/collection?page_ref=catalog) interface of the hierarchy.
- The `List` interface and its [`ArrayList`](https://www.codecademy.com/resources/docs/java/array-list?page_ref=catalog) and `LinkedList` implementations.
- The [`Set`](https://www.codecademy.com/resources/docs/java/set?page_ref=catalog) interface and its [`HashSet`](https://www.codecademy.com/resources/docs/java/hashset?page_ref=catalog), `LinkedHashSet`, and `TreeSet` implementations.
- The [`Queue`](https://www.codecademy.com/resources/docs/java/queue?page_ref=catalog) interface and its `LinkedList` and [`PriorityQueue`](https://www.codecademy.com/resources/docs/java/priorityqueue?page_ref=catalog) implementations. 
- The `Deque` interface and its `LinkedList` and `ArrayDeque` implementations. 
- The [`Map`](https://www.codecademy.com/resources/docs/java/map?page_ref=catalog) interface and its [`HashMap`](https://www.codecademy.com/resources/docs/java/hashmap?page_ref=catalog), `LinkedHashMap`, and [`TreeMap`](https://www.codecademy.com/resources/docs/java/treemap?page_ref=catalog) implementations.
- The `Collections` utility algorithm `static` methods like [`sort()`](https://www.codecademy.com/resources/docs/java/collections/sort?page_ref=catalog), `binarySearch()`, [`max()`](https://www.codecademy.com/resources/docs/java/collections/max?page_ref=catalog), [`min()`](https://www.codecademy.com/resources/docs/java/collections/min?page_ref=catalog), and [`reverse()`](https://www.codecademy.com/resources/docs/java/collections/reverse?page_ref=catalog).
- Collection stream pipelines and aggregate operations with lambdas.

Knowing these topics will help you create enterprise-level programs and handle data more efficiently by not needing to "reinvent the wheel" and fully utilize the power of the collections framework.  


Review

The [`Queue`](https://www.codecademy.com/resources/docs/java/queue?page_ref=catalog) core interface in the collections framework is a collection that implements the Queue data structure. A `Queue` is a First In First Out (FIFO) data structure in which elements are inserted at the _tail_ (back) of the collection and removed from the _head_ (front). Think of it like a line (queue) of people waiting to make a purchase: the first people that arrive on the line (queue) will be the first ones to be able to make a purchase. 

A `Queue` has two types of access methods for inserting, removing, and getting (but not removing) the element at 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`. 

Like the other collections framework interfaces, `Queue` has many implementations. We'll focus on `LinkedList` and [`PriorityQueue`](https://www.codecademy.com/resources/docs/java/priorityqueue?page_ref=catalog). We've seen `LinkedList` be used as a `List` implementation, but it's also perfect when needing a basic `Queue` implementation. Being able to use a `LinkedList` as both a `List` and a `Queue` is a perfect example of the compatibility within the collections framework. The `PriorityQueue` ensures the top element is the smallest relative to the data type's natural ordering (or some custom ordering policy you provide).

Let's look at an example of `Queue` with a `LinkedList` implementation:
```java
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 NoSuchElementException
```
In the example above we:
- Created a new `String Queue` reference with a `LinkedList` implementation.
- Called `add()` and `offer()` to insert elements into the `Queue`. Note the state of the `Queue` after each call. 
- Called `remove()` and `poll()` to remove and retrieve the element at the front of the `Queue`.
- Called `peek()` and `element()` to retrieve but not remove the element at the front of the `Queue`. Note the results when `stringQueue` is empty.

We can iterate through a `Queue` using the enhanced `for-loop`. For example:
```java
// 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.

Let's practice creating a `Queue` and iterating through it.


Queue

We've discussed the core interfaces and their implementations, but the thing that keeps the collections framework polymorphic (compatible) is the [`Collection`](https://www.codecademy.com/resources/docs/java/collection?page_ref=catalog) interface. The `Collection` interface provides a generic, general-purpose API when our program needs a collection of elements and doesn't care about what type of collection it is.

Implementing classes may implement `Collection` methods and add restrictions to them like a [`Set`](https://www.codecademy.com/resources/docs/java/set?page_ref=catalog) does to only contain unique elements. Also, implementing classes or extending interfaces do not need to implement all methods and instead will throw an `UnsupportOperationException` when a `Collection` method is not implemented correctly. 

We've seen `add()` and `remove()`, but some other methods `Collection` defines are:
- [`addAll()`](https://www.codecademy.com/resources/docs/java/collection?page_ref=catalog) - receives a `Collection` argument and adds all the elements. 
- [`isEmpty()`](https://www.codecademy.com/resources/docs/java/collection?page_ref=catalog) - returns `true` if the collection is empty, `false` otherwise.
- `iterator()` - returns an [`Iterator`](https://www.codecademy.com/resources/docs/java/iterator?page_ref=catalog) over the collection.
- [`size()`](https://www.codecademy.com/resources/docs/java/collection?page_ref=catalog) - returns the number of elements in the collection.
- `stream()` - returns a `Stream` over the elements in the collection.
- [`toArray()`](https://www.codecademy.com/resources/docs/java/collection?page_ref=catalog) - returns an array with all elements in the collection.

Here is an example of how we can use some of these methods:
```java
Collection<Integer> collection = new ArrayList<>();
collection.add(4);
collection.add(8);

boolean isEmpty = collection.isEmpty(); // false
int collectionSize = collection.size(); // 2

Integer[] collectionArray = collection.toArray(new Integer[0]);
```
In the example above, we:
- Created an `Integer Collection` with an `ArrayList` implementation.
- Called `add()` to add elements to the end of the `Collection`.
- Called `isEmpty()` to check if `collection` has elements.
- Called `size()` to get the number of elements in `collection`.
- Called `toArray()` to transform our collection into an array. Note the `new Integer[0]` argument that specifies the type of array we want returned. 

We can iterate through a `Collection` with an enhanced `for-loop` as we've seen with the other core interfaces. 

Let's practice working with `Collection`.


Collection

Another core interface provided by the collections framework is the [`Set`](https://www.codecademy.com/resources/docs/java/set?page_ref=catalog) interface. A `Set` is a collection of unique elements and all of its methods ensure this stays true. The collections framework provides different implementations of a `Set` (we'll focus on a subset of them) that each have different use cases. 

The [`HashSet`](https://www.codecademy.com/resources/docs/java/hashset?page_ref=catalog) 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.  

Let's look at how we can create `Set` with a `HashSet` implementation:
```java
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
```
In the example above, we:
- Created a `Set` reference named `intSet` with a `HashSet` implementation.
- Called `add()`, which adds elements to the `Set` and returns `true` if an element was successfully added or `false` if not.
- Called `add()`, noting that the program will not throw an error if we try to insert a non-unique element into the set. 
- Called `contains(9)`, which returns `false` because the `9` does not exist in `intSet`.
- Called `contains(0)`, which returns `true` because the `0` does exist in `intSet`.

All of these methods work for other `Set` implementations too.  

We can iterate through a `Set` using the enhanced `for-loop` and notice that we can't guarantee the ordering of elements looped. For example:
```java
// Assuming `intSet` has elements -> 1, 5, 9, 0, 23
for (Integer number: intSet) {
  System.out.println(number);
}
// OUTPUT TERMINAL: 5 0 23 9 1
```
Let's practice creating a `Set` and iterating through it.


In Java, we often need to write programs that work with groups (or collections) of objects. Recall that an array is an object that holds multiple objects of the same type (also known as its _elements_) but is limited by its fixed size and functionality. Java provides a _Collections Framework_ to help overcome the limits of an array and provide more complex functionality to meet different collection needs. 

The collections framework provides data structures (through interfaces and implementing classes) and algorithms, which perform common tasks on collections. The collections framework allows us to focus on the important parts of our program and not on low-level implementation details (like needing to implement a dynamic sizing collection).

The collections framework provides a hierarchical relationship between its interfaces, making the various implementations compatible with each other and thus making our code scalable and flexible. All the interfaces in the collections framework are generic, which allows us to use optimized and tested "plumbing" for our specific data types. 

As we go through the lesson, we will explore the collections framework interfaces and implementations, their relationship to generics, and the operations we can perform. 


a chart showing the Collections hierarchy

Introduction

We've seen the many benefits of the collections framework and how they provide ready-to-use implementations so we don't have to create them ourselves. What should we do when we need to sort a collection or get some statistic like the maximum or minimum element in the collection? The collections framework provides the [`Collections`](https://www.codecademy.com/resources/docs/java/collections?page_ref=catalog) class that has many `static` methods that perform these types of operations for us. 

Here are some of the methods provided by the `Collections` class:
- `binarySearch()`: Performs [binary search](https://www.codecademy.com/learn/fscp-22-search-graph-search-algorithms/modules/wdcp-22-binary-search-and-search-trees/cheatsheet) over a `List` to find the specified object and returns the index if found. This method is overloaded to also accept a [`Comparator`](https://www.codecademy.com/resources/docs/java/comparator) to define a custom ordering policy. Note: this method only provides the correct value if the elements in the `List` are sorted. 
- [`max()`](https://www.codecademy.com/resources/docs/java/collections/max?page_ref=catalog): Returns the maximum element in the [`Collection`](https://www.codecademy.com/resources/docs/java/collection?page_ref=catalog). This method is overloaded to also accept a `Comparator` to define a custom ordering policy. 
- [`min()`](https://www.codecademy.com/resources/docs/java/collections/min?page_ref=catalog): Returns the minimum element in the `Collection`. This method is overloaded to also accept a `Comparator` to define a custom ordering policy. 
- [`reverse()`](https://www.codecademy.com/resources/docs/java/collections/reverse?page_ref=catalog): Reverses the order of elements in the `List` passed in as an argument. 
- [`sort()`](https://www.codecademy.com/resources/docs/java/collections/sort?page_ref=catalog): Sorts the `List` passed in as an argument. This method is overloaded to also accept a `Comparator` to define a custom ordering policy.
 
These utility methods for the collections framework make performing complex calculations or gaining insight into the collection of data we have easy and efficient. 

Let's practice using some `Collections` methods.


Algorithms

The collections 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 elements are ordered in a sequence. `List`s 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, `List`s are dynamically sized. 

The collections framework provides many `List` implementations, but we'll focus on the [`ArrayList`](https://www.codecademy.com/resources/docs/java/array-list?page_ref=catalog) 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 at the beginning or end of a list.

Let's create a `List` using an `ArrayList` as its implementation and see some operations:
```java
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
```
In the example above, we:
- Created a `List` reference named `intList` with an `ArrayList` implementation.
- Called `add()`, which appends elements to the end of the `List`. We can see the state of `intList` after each call. 
- Called `intList.set(1, 3)`, which replaces the element at index `1` (the second element in 0-based indexing) with `3`. 
- Called `get()`, which gets the value at index `2` (the third element in 0-based indexing). 
- Called `indexOf()`, which returns the index of the first occurrence of `3` (the first `3` is at index `1`).
-Called `subList()`, which returns a sublist in a new `List` with the elements specified by the starting index `1` (inclusive) and ending index `3` (exclusive). 

We can iterate through a `List` using the enhanced `for-loop`. For example:
```java
// Assuming `intList` has elements -> 1, 5, 2, 6, 1
for (Integer number: intList) {
  System.out.println(number);  
}
// OUTPUT TERMINAL: 1 5 2 6 1
```
In the example above, we used the enhanced `for-loop`, which iterates through the elements in `intList` from index `0` to the end of the list. Note that we use the `int` wrapper class `Integer` to iterate through the elements in `intList`. However, we could have also used an 'int'. 

Let's practice creating a `List` and iterating through it.


List

As we've worked with different types of [`Collection`](https://www.codecademy.com/resources/docs/java/collection?page_ref=catalog)s and [`Map`](https://www.codecademy.com/resources/docs/java/map?page_ref=catalog)s, we've seen how important and verbose `for-loops` can get. For example, this code will produce a new `Integer List` where even numbers are doubled:
```java
// Given `intList` with the following elements: 5, 4, 1, 3, 7, 8
List<Integer> evenList = new ArrayList<>();
for(Integer i: intList) {
  if(i % 2 == 0) {
    evenList.add(i*2);
  }
}
// evenList will have elements 8, 16
```
In the example above, we filtered down `intList` to only include even numbers (`i % 2 == 0`) and then doubled their value and stored them in `evenList`. We can perform the same operation using `Stream`s. A `Stream` is a sequence of elements created from a `Collection` source. A Stream can be used as input to a _pipeline_, which defines a set of _aggregate operations_ (methods that apply transformations to a `Stream` of data). The output of an aggregate operation serves as the input of the next operation (these are known as _intermediate operations_) until we reach a _terminal operation_, which is the final operation in a pipeline that produces some non-`Stream` output. 

Before we continue, we need a brief understanding of _lambda functions_ in Java. A lambda eliminates the need to create (extremely verbose) anonymous classes to implement methods. With lambdas, we can define the method with its parameter(s) and its return value in a small block of code. Let's look at the example above rewritten using aggregate operations. 
```java
List<Integer> evenList = intList.stream()
  .filter((number) -> {return number % 2 == 0;})
  .map(evenNum -> evenNum*2)
  .collect(Collectors.toList());
```  
In the example above, we:
- Called `stream()` which returns a sequential `Stream` with elements from `intList`.
- Created a (small) pipeline with a single intermediate operation `filter()` and the terminal operation `collect()`.
- Called `filter()` which returns a `Stream` with elements that pass some filter condition. An element passes a filter condition by returning `true` when called on the filter method. We defined the filter method to return `true` if the number is even. 
- Defined a lambda to provide the filter method to `filter()`. The lambda defines all the parameters before the arrow (`->`) symbol and defines the function's body after.
- Called `map()` which will return a new `Stream` with elements that have had some method applied to them. 
- Defined the `map()` method using a lambda where we have `evenNum` as a parameter and return the result of multiplying `evenNum` by 2. You can omit the parameter parentheses `()` when there is only one parameter and omit the curly braces `{}` and `return` when the lambda body is one line.
- Called `collect()` (terminal operation), which takes the `Stream` and collects the elements back into some Container (we use a `List`). Java provides a `Collectors` class with `static` utility methods to use as an argument to `collect()`. 

Great job getting this far. It's important to note that there is a lot more information about lambda and `Stream` that is outside the scope of this lesson. We encourage you to explore the Java docs to learn more.

Let's practice creating a pipeline with `filter`, `map`, and `collect()`.
