A Guide to LinkedHashSet in Java

1. Overview

In this article, we’ll explore the LinkedHashSet class of the Java Collections API. We’ll dive into the features of this data structure and demonstrate its functionalities.

2. Introduction to LinkedHashSet

The LinkedHashSet is a generic data structure that belongs to the Java.util library. It’s a direct descendant of the HashSet data structure, hence, contains non-duplicate elements at every given time.

In addition to having a doubly-linked list running through all of its entries, its implementation is different from that of the HashSet in that it maintains a predictable iteration order. The iteration order is defined by the insertion order of the elements into the set.

The LinkedHashSet saves the client from the unpredictable ordering provided by HashSet, without incurring the complexity that comes with a TreeSet.

While its performance is likely to be just slightly less than that of HashSet, due to the added expense of maintaining the linked list, it has constant-time (O1) performance for add(), contains() and remove() operations.

3. Create a LinkedHashSet

There are several constructors available to create a LinkedHashSet. Let’s have a look at each one of them:

3.1. Default No-Arg Constructor

Set<String> linkedHashSet = new LinkedHashSet<>();
assertTrue(linkedHashSet.isEmpty());

3.2. Create with an Initial Capacity

The initial capacity represents the initial length of the LinkedHashSet. Providing an initial capacity prevents any unnecessary resizing of the Set as it grows. The default initial capacity is 16:

LinkedHashSet<String> linkedHashSet = new LinkedHashSet<>(20);

3.3. Create from a Collection

We can also use the content of a Collection to populate a LinkedHashSet object at the point of creation:

@Test
 void whenCreatingLinkedHashSetWithExistingCollection_shouldContainAllElementOfCollection(){
      Collection<String> data = Arrays.asList("first", "second", "third", "fourth", "fifth");
      LinkedHashSet<String> linkedHashSet = new LinkedHashSet<>(data);

      assertFalse(linkedHashSet.isEmpty());
      assertEquals(data.size(), linkedHashSet.size());
      assertTrue(linkedHashSet.containsAll(data) && data.containsAll(linkedHashSet));
 }

3.4. Create with Initial Capacity and Load Factor

When the size of the LinkedHashSet grows to exceed the value of the initial capacity, the new capacity is the multiplication of the load factor and the previous capacity. In the below snippet, the initial capacity is set to 20 and the load factor is 3.

LinkedHashSet<String> linkedHashSet = new LinkedHashSet<>(20, 3);

The default load factor is 0.75.

4. Adding an Element to the LinkedHashSet

We can either add a single element or a Collection of elements to the LinkedHashSet by using the add() and addAll() methods respectively.  An element will be added if it doesn’t already exist in the Set. These methods return true when an element is added to the set, otherwise, they return false.

4.1. Add a Single Element

Here’s an implementation to add an element to a LinkedHashSet:

@Test
void whenAddingElement_shouldAddElement(){
    Set<Integer> linkedHashSet = new LinkedHashSet<>();
    assertTrue(linkedHashSet.add(0));
    assertFalse(linkedHashSet.add(0));
    assertTrue(linkedHashSet.contains(0));

}

4.2. Add a Collection of Elements

As mentioned earlier, we can also add a Collection of elements to a LinkedHashSet:

@Test
void whenAddingCollection_shouldAddAllContentOfCollection(){
    Collection<Integer> data = Arrays.asList(1,2,3);
    LinkedHashSet<Integer> linkedHashSet = new LinkedHashSet<>();

    assertTrue(linkedHashSet.addAll(data));
    assertTrue(data.containsAll(linkedHashSet) && linkedHashSet.containsAll(data));
 }

The rule of not adding duplicates also applies to the addAll() method as demonstrated below:

@Test
void whenAddingCollectionWithDuplicateElements_shouldMaintainUniqueValuesInSet(){
    LinkedHashSet<Integer> linkedHashSet = new LinkedHashSet<>();
    linkedHashSet.add(2);
    Collection<Integer> data = Arrays.asList(1, 1, 2, 3);

    assertTrue(linkedHashSet.addAll(data));
    assertEquals(3, linkedHashSet.size());
    assertTrue(data.containsAll(linkedHashSet) && linkedHashSet.containsAll(data));
}

Notice that the data variable contains duplicate values of 1 and the LinkedHashSet already contains the Integer value 2 before invoking the addAll() method.

5. Iterating Through a LinkedHashSet

Like every other descendant of the Collection library, we can iterate through a LinkedHashSet. Two types of iterators are available in a LinkedHashSet: Iterator and Spliterator.

While the former is only able to traverse and perform any basic operation on a Collection, the latter splits the Collection into subsets and performs different operations on each subset in parallel, thereby making it thread-safe.

5.1. Iterating with an Iterator

@Test
void whenIteratingWithIterator_assertThatElementIsPresent(){
    LinkedHashSet<Integer> linkedHashSet = new LinkedHashSet<>();
    linkedHashSet.add(0);
    linkedHashSet.add(1);
    linkedHashSet.add(2);

    Iterator<Integer> iterator = linkedHashSet.iterator();
    for (int i = 0; i < linkedHashSet.size(); i++) {
        int nextData = iterator.next();
        assertEquals(i, nextData);
    }
}

5.2. Iterating with a Spliterator

@Test
void whenIteratingWithSpliterator_assertThatElementIsPresent(){
    LinkedHashSet<Integer> linkedHashSet = new LinkedHashSet<>();
    linkedHashSet.add(0);
    linkedHashSet.add(1);
    linkedHashSet.add(2);

    Spliterator<Integer> spliterator = linkedHashSet.spliterator();
    AtomicInteger counter = new AtomicInteger();
    spliterator.forEachRemaining(data -> {
       assertEquals(counter.get(), (int)data);
       counter.getAndIncrement();
    });
}

6. Remove Elements from the LinkedHashSet

Here are the different ways to remove an element from the LinkedHashSet:

6.1. remove()

This method removes an element from the Set given that we know the exact element we want to remove. It accepts an argument that’s the actual element we want to remove and returns true if successfully removed, otherwise false:

@Test
void whenRemovingAnElement_shouldRemoveElement(){
    Collection<String> data = Arrays.asList("first", "second", "third", "fourth", "fifth");
    LinkedHashSet<String> linkedHashSet = new LinkedHashSet<>(data);

    assertTrue(linkedHashSet.remove("second"));
    assertFalse(linkedHashSet.contains("second"));
}

6.2. removeIf()

The removeIf() method removes an element that satisfies specified predicate conditions. The example below removes all elements in the LinkedHashSet that are greater than 2:

@Test
void whenRemovingAnElementGreaterThanTwo_shouldRemoveElement(){
    LinkedHashSet<Integer> linkedHashSet = new LinkedHashSet<>();
    linkedHashSet.add(0);
    linkedHashSet.add(1);
    linkedHashSet.add(2);
    linkedHashSet.add(3);
    linkedHashSet.add(4);

    linkedHashSet.removeIf(data -> data > 2);
    assertFalse(linkedHashSet.contains(3));
    assertFalse(linkedHashSet.contains(4));
}

6.3. Removing with an Iterator

The iterator is also another option we can use to remove elements from the LinkedHashSet. The remove() method of the Iterator removes the element that the Iterator is currently on:

@Test
void whenRemovingAnElementWithIterator_shouldRemoveElement(){
    LinkedHashSet<Integer> linkedHashSet = new LinkedHashSet<>();
    linkedHashSet.add(0);
    linkedHashSet.add(1);
    linkedHashSet.add(2);

    Iterator<Integer> iterator = linkedHashSet.iterator();
    int elementToRemove = 1;
    assertTrue(linkedHashSet.contains(elementToRemove));
    while(iterator.hasNext()){
        if(elementToRemove == iterator.next()){
           iterator.remove();
       }
    }
    assertFalse(linkedHashSet.contains(elementToRemove));
}

7. Conclusion

In this article, we studied the LinkedHashSet data structure from the Java Collections library. We demonstrated how to create a LinkedHashSet through its different constructors, adding and removing elements, as well as iterating through it. We also, learned the underlying layers of this data structure, its advantage over the HashSet as well as the time complexity for its common operations.