# 12.1 Lists and Sets in Java

In this section, we will learn about how to use Java's built-in `List` and `Set` data structures as well as build our own `ArraySet`.

### Getting Started

{% embed url="<https://youtu.be/DWr8YNXPH6k>" %}

In this course, we've already built two kinds of lists: `AList` and `SLList`. We also built an interface `List61B` to enforce specific list methods `AList` and `SLList` had to implement. You can find the code at the following links:

* [`List61B`](https://github.com/Berkeley-CS61B/lectureCode-sp23/blob/main/lec9_inheritance2/List61B.java)
* [`AList`](https://github.com/Berkeley-CS61B/lectureCode-sp23/blob/main/lec8_inheritance1/AList.java)
* [`SLList`](https://github.com/Berkeley-CS61B/lectureCode-sp23/blob/main/lec9_inheritance2/SLList.java)

This is how we might use `List61B` type:

```java
List61B<Integer> L = new AList<>();
L.addLast(5);
L.addLast(10);
L.addLast(15);
L.print();
```

### Lists in Real Java Code

We built a list from scratch, but Java provides a built-in `List` interface and several implementations, e.g. `ArrayList`. Remember, since `List` is an interface we can't instantiate it! We must instantiate one of its implementations.

To access this, we can use the full name ('canonical name') of classes/interfaces:

```java
java.util.List<Integer> L = new java.util.ArrayList<>();
```

However, this is a bit verbose. Instead, we can import java libraries:

```java
import java.util.List;
import java.util.ArrayList;

public class Example {
    public static void main(String[] args) {
        List<Integer> L = new ArrayList<>();
        L.add(5);
        L.add(10);
        System.out.println(L);
    }
}
```

### Sets

Sets are a collection of unique elements - you can only have one copy of each element. Unlike Lists, there is also no sense of order: you can't index into a set, nor can you control where each element is inserted into the set.

#### Java Sets

Java has the `Set` interface along with implementations, e.g. `HashSet`. Remember to import them if you don't want to use the full name!

```java
import java.util.Set;
import java.util.HashSet;
```

Example use:

```java
Set<String> s = new HashSet<>();
s.add("Tokyo");
s.add("Lagos");
System.out.println(s.contains("Tokyo")); // true
```

#### Python Equivalent

In python, we simply call `set()`. To check for `contains` we don't use a method but the keyword `in`. Here's an example:

```python
s = set()
s.add("Tokyo")
s.add("Lagos")
print("Tokyo" in s) // True
```

### DIY: ArraySet

Our goal is to make our own set, `ArraySet`, with the following methods:

* `add(value)`: add the value to the set if not already present
* `contains(value)`: check to see if ArraySet contains the key
* `size()`: return number of values

If you would like to try it yourself, find 'Do It Yourself' `ArraySet starter code` [here](https://github.com/Berkeley-CS61B/lectureCode-sp23/blob/main/lec11_inheritance4/DIY/ArraySet.java). In the lecture clip below, Professor Hug goes develops the solution:

{% embed url="<https://youtu.be/gX9KFdZBg-k>" %}