Sets and Lists

Sets

Just like in math, Java has something called a set. The formal definition of a set is: an un-ordered collection of unique elements. This means that we cannot have duplicate elements in our set and that no order is retained while storing and using the set. Note, that an array can be defined as an ordered collection of elements.

The reason we use sets is that they are extremely fast. Adding, removing and finding elements in a set of any size happens almost instantly, whereas the time to do these things with an array depends on the array size.

There are a few different types of sets but here is an example of the most commonly used one.

import java.util.Set;
import java.util.HashSet;
// Need to import these

Set<Integer> t = new HashSet<Integer>;

Operations on Sets

Now that we know how to create a set we need to know how to use them! How we can add, remove and find elements within our set.

To add something to our set we can do the following.

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

Set<Integer> t = new HashSet<Integer>;
t.add(5);
t.add(7);
t.add(5);
t.add(8);

System.out.println(t);
// This will print [5,7,8]
// Note that 5 is NOT added twice

To remove something from a set we can do the following.

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

Set<Integer> t = new HashSet<Integer>;
t.add(5);
t.add(7);
t.add(5);
t.add(8);

t.remove(8);

System.out.println(t);
// This will print [5,7]

Finally to see if an element exists in a set we can use .contains().

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

Set<Integer> t = new HashSet<Integer>;
t.add(5);
t.add(7);

boolean setHas = t.contains(5);

System.out.println(setHas); // prints true

Some other useful methods are .clear() and .isEmpty()

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

Set<Integer> t = new HashSet<Integer>;
t.add(5);
t.add(7);

t.clear();
boolean setEmpty = t.isEmpty();

System.out.println(setHas); // prints true

Lastly to get the size of a set we use .size().

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

Set<Integer> t = new HashSet<Integer>;
t.add(5);
t.add(7);

System.out.println(t.size()); // prints 2

Other Kinds of Sets

The set that we used above was called a HashSet and is the standard set that we use. However there are a few other kinds:

• TreeSet: this is a set ordered from least to greatest
• LinkedHashSet: this is a set that maintains the order of elements when they are added.

The sets use the same methods as seen above but are stored in memory differently. In some cases they may not perform as quickly as a HashSet.

import java.util.Set;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.TreeSet;

Set<Integer> t = new LinkedHashSet<Integer>;
Set<Integer> x = new TreeSet<Integer>;

Lists

Lists are similar to arrays but allow for a dynamic size. This means we can add and remove elements from our list (unlike arrays). They are useful in cases when we are unsure about how many elements we will need to store.

To create a new list we do the following:

import java.util.ArrayList;

ArrayList<Integer> t = new ArrayList<Integer>();

We can add elements into our list using .add()

import java.util.ArrayList;

ArrayList<Integer> t = new ArrayList<Integer>();
t.add(5);
t.add(4);

To index elements we follow the same rules as arrays but some different syntax. .get() for lists acts the same as the [] for arrays.

import java.util.ArrayList;

ArrayList<Integer> t = new ArrayList<Integer>();
t.add(5);
t.add(4);
System.out.println(t.get(0)); //Prints 5
System.out.println(t.get(1)); //Prints 4

To change a specific index in our list we must use .set()

import java.util.ArrayList;

ArrayList<Integer> t = new ArrayList<Integer>();
t.add(5);
t.add(4);

t.set(1,100);

System.out.println(t.get(0)); //Prints 5
System.out.println(t.get(1)); //Prints 100
```
A useful method to take note of is **.subList(x,y)**. This will return to us a list that is from index x to index y.
```java
import java.util.ArrayList;

ArrayList<Integer> t = new ArrayList<Integer>();
t.add(1);
t.add(4);
t.add(5);
t.add(7);
t.add(9);
t.add(100);

System.out.println(t.subList(1,3));
//Prints [4,5]
// The last index (in our case 3) is not included 
```
## Types of Lists
Similarly to sets there is another kind of list in Java called a LinkedList, if you'd like to read more about this please [click here](https://www.tutorialspoint.com/java/java_linkedlist_class.htm).