# Set Types

## TreeSet And LinkedHashSet:

## 1 ) TreeSet in Java

TreeSet provides an implementation of the SortedSet Interface and SortedSet extends Set Interface. It behaves like simple set with the exception that it stores elements in sorted format.Following are the features of TreeSet.

* TreeSet uses tree data structure for storage.
* Objects are stored in sorted, ascending order. But we can iterate in descending order using method TreeSet.descendingIterator().
* Access and retrieval times are very fast which make TreeSet an excellent choice for storage of large volume of data in sorted format.
* TreeSet doesn’t use hashCode() and equals() methods to compare it’s elements. It uses compare() (or compareTo()) method to determine the equality of two elements.

**Important Methods of treeset class:**

* **boolean add(E e):** This method adds the specified element to this set if it is not already present.
* **E ceiling(E e):** This method returns the least element in this set greater than or equal to the given element, or null if there is no such element.
* **boolean contains(Object o):** This method returns true if this set contains the specified element.
* **E floor(E e):** This method Returns the greatest element in this set less than or equal to the given element, or null if there is no such element.
* **E pollFirst():** This method retrieves and removes the first (lowest) element, or returns null if this set is empty.
* **E pollLast():** This method retrieves and removes the last (highest) element, or returns null if this set is empty.
* **boolean remove(Object o):**&#x54;his method removes the specified element from this set if it is present.

The following is a very simple TreeSet implementation including TreeSet is sorting,iteration in a TreeSet, retrieving first and last element and remove an element.

```java
// Java program to demonstrate working TreeSet collection 
import java.util.Iterator;
import java.util.TreeSet; 

public class TreeSetExample 
{ 
	public static void main(String[] args) 
	{ 
		TreeSet<Integer> ts = new TreeSet<Integer>(); 
		ts.add(10); 
		ts.add(61); 
		ts.add(87); 
		ts.add(39); 

		Iterator<Integer> iterator = ts.iterator(); 
		System.out.print("Tree set data: "); 

		// note that 87 being largest element, appears in 
		// the last. 
		while (iterator.hasNext()) 
			System.out.print(iterator.next() + " "); 
		System.out.println(); 

		// to check if treeset is empty or not. 
		if (ts.isEmpty()) 
			System.out.print("Tree Set is empty."); 
		else
			System.out.println("Tree Set size: " + ts.size()); 

		// To get the smallest element from the set 
		System.out.println("First data: " + ts.first()); 

		// To get the largest value from set 
		System.out.println("Last data: " + ts.last()); 

		// remove 61 from set. 
		if (ts.remove(61)) 
			System.out.println("Data is removed from tree set"); 
		else
			System.out.println("Data doesn't exist!"); 

		System.out.print("Now the tree set contain: "); 
		iterator = ts.iterator(); 

		// Displaying the Tree set data 
		while (iterator.hasNext()) 
			System.out.print(iterator.next() + " "); 

		System.out.println(); 
		System.out.println("Now the size of tree set: " + 
						ts.size()); 

		// Remove all 
		ts.clear(); 
		if (ts.isEmpty()) 
			System.out.print("Tree Set is empty."); 
		else
			System.out.println("Tree Set size: " + ts.size()); 
	} 
} 
```

```
Tree set data: 10 39 61 87 
Tree Set size: 4
First data: 10
Last data: 87
Data is removed from tree set
Now the tree set contain: 10 39 87 
Now the size of tree set: 3
Tree Set is empty.
```

### Example :

```java
package certification.collections;

import java.util.Collections;
import java.util.Set;
import java.util.TreeSet;

class Emp implements Comparable<Emp> {
	private int id;
	private String name;

	public Emp(int id, String name) {
		super();
		this.id = id;
		this.name = name;
	}

	public int getId() {
		return id;
	}

	public void setId(int id) {
		this.id = id;
	}

	public String getName() {
		return name;
	}

	public void setName(String name) {
		this.name = name;
	}

	@Override
	public int compareTo(Emp o) {
		return this.getName().compareTo(o.getName());
	}

	@Override
	public String toString() {
		return "Emp [id=" + id + ", name=" + name + "]";
	}

}

public class TreeSetEx {
	public static void main(String[] args) {

		Set<Integer> integers = new TreeSet<Integer>(Collections.reverseOrder());

		integers.add(12);
		integers.add(-2);

		integers.add(13);

		integers.add(4);

		System.out.println(integers);

		// for(Integer integer : integers) {
		// System.out.println(integer);
		// }

		Emp emp = new Emp(1, "Mohit");
		Emp emp1 = new Emp(2, "Rohit");
		Emp emp2 = new Emp(3, "Amit");
		Emp emp3 = new Emp(4, "Desp");

		Set<Emp> emps = new TreeSet<Emp>();

		emps.add(emp);
		emps.add(emp1);
		emps.add(emp2);
		emps.add(emp3);

		System.out.println(emps);

	}

}

```

### Output :

```java
[13, 12, 4, -2]
[Emp [id=3, name=Amit], Emp [id=4, name=Desp], Emp [id=1, name=Mohit], Emp [id=2, name=Rohit]]

```



## 2) LinkedHashSet in Java with Examples

A LinkedHashSet is an ordered version of HashSet that maintains a doubly-linked List across all elements. When the iteration order is needed to be maintained this class is used. When iterating through a HashSet the order is unpredictable, while a LinkedHashSet lets us iterate through the elements in the order in which they were inserted. When cycling through LinkedHashSet using an iterator, the elements will be returned in the order in which they were inserted.

**Syntax:**

```
LinkedHashSet<String> hs = new LinkedHashSet<String>();
```

* Contains unique elements only like HashSet. It extends HashSet class and implements Set interface.
* Maintains insertion order.

```java
import java.util.LinkedHashSet;

public class LinkedHashSetExample {
	public static void main(String[] args) {
		LinkedHashSet<String> linkedset = new LinkedHashSet<String>();

		// Adding element to LinkedHashSet
		linkedset.add("A");
		linkedset.add("B");
		linkedset.add("C");
		linkedset.add("D");

		// This will not add new element as A already exists
		linkedset.add("A");
		linkedset.add("E");

		System.out.println("Size of LinkedHashSet = " + linkedset.size());
		System.out.println("Original LinkedHashSet:" + linkedset);
		System.out.println("Removing D from LinkedHashSet: " + linkedset.remove("D"));
		System.out.println("Trying to Remove Z which is not " + "present: " + linkedset.remove("Z"));
		System.out.println("Checking if A is present=" + linkedset.contains("A"));
		System.out.println("Updated LinkedHashSet: " + linkedset);
	}
}
```

```
Size of LinkedHashSet = 5
Original LinkedHashSet:[A, B, C, D, E]
Removing D from LinkedHashSet: true
Trying to Remove Z which is not present: false
Checking if A is present=true
Updated LinkedHashSet: [A, B, C, E]
```



## **Differences Between HashSet, LinkedHashSet and TreeSet:**

| FEATURES                 | HASHSET                                                                      | LINKEDHASHSET                                                                                                                                                                                                                 | TREESET                                                                                                                                                                     |
| ------------------------ | ---------------------------------------------------------------------------- | ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | --------------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
| Internal Working         | HashSet internally uses HashMap for storing objects                          | LinkedHashSet uses LinkedHashMap internally to store objects                                                                                                                                                                  | TreeSet uses TreeMap internally to store objects                                                                                                                            |
| When To Use              | If you don’t want to maintain insertion order but want store unique objects  | If you want to maintain insertion order of elements then you can use LinkedHashSet                                                                                                                                            | If you want to sort the elements according to some Comparator then use TreeSet                                                                                              |
| Order                    | HashSet does not maintain insertion order                                    | LinkedHashSet maintains insertion order of objects                                                                                                                                                                            | While TreeSet orders of the elements according to supplied Comparator. Default, It’s objects will be placed in their natural ascending order.                               |
| Complexity of Operations | HashSet gives O(1) complicity for insertion, removing and retrieving objects | LinkedHashSet gives insertion, removing and retrieving operations performance in order O(1).                                                                                                                                  | While TreeSet gives performance of order O(log(n)) for insertion, removing and retrieving operations.                                                                       |
| Performance              | HashSet performance is better according to LinkedHashSet and TreeSet.        | The performance of LinkedHashSet is slow to TreeSet. The performance LinkedHashSet is almost similar to HashSet but slower because, LinkedHashSet maintains LinkedList internally to maintain the insertion order of elements | TreeSet performance is better to LinkedHashSet excluding insertion and removal operations because, it has to sort the elements after each insertion and removal operations. |
| Compare                  | HashSet uses equals() and hashCode() methods to compare the objects          | LinkedHashSet uses equals() and hashCode() methods to compare it’s objects                                                                                                                                                    | TreeSet uses compare() and compareTo() methods to compare the objects                                                                                                       |
| Null Elements            | HashSet allows only one null objects                                         | LinkedHashSet allows only one null objects.                                                                                                                                                                                   | TreeSet not allow a any null objects. If you insert null objects into TreeSet, it throws NullPointerException                                                               |
| Syntax                   | HashSet obj = new HashSet();                                                 | LinkedHashSet obj = new LinkedHashSet();                                                                                                                                                                                      | TreeSet obj = new TreeSet();                                                                                                                                                |
