LinkedHashSet in Java

Introduction

In the Java Collections Framework, the Set interface represents a collection of unique elements (no duplicates allowed). While HashSet is the most commonly used implementation due to its blazing-fast O(1) performance, it has a distinct characteristic: it does not guarantee any iteration order.

If you need a Set that prevents duplicates, provides O(1) lookup times, and remembers the exact order in which elements were added, LinkedHashSet is the data structure you are looking for.

Core Concept: Deep Dive and Architecture

How It Works Internally

To understand LinkedHashSet, you must first understand how HashSet works. A HashSet is essentially a wrapper around a HashMap, where the elements of the Set act as the keys of the Map, and the values are filled with a dummy constant object.

Similarly, LinkedHashSet is simply a wrapper around a LinkedHashMap.

public class LinkedHashSet<E> extends HashSet<E> implements Set<E>, Cloneable, java.io.Serializable

Because it relies on a LinkedHashMap internally, it inherits its properties:

1. Hashing Array: It uses an array of buckets to achieve O(1) time complexity for add(), remove(), and contains().
2. Doubly-Linked List: It maintains a doubly-linked list running through all its entries. This list is responsible for maintaining the insertion order.

When you iterate over a LinkedHashSet, you are traversing this doubly-linked list, ensuring that elements are returned in the exact order they were inserted.

Code Examples

1. Beginner Example: The Basics

This example illustrates the primary difference between HashSet and LinkedHashSet.

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

public class SetComparison {
    public static void main(String[] args) {
        
        // HashSet: No order guaranteed
        Set<String> hashSet = new HashSet<>();
        hashSet.add("Zebra");
        hashSet.add("Apple");
        hashSet.add("Mango");
        System.out.println("HashSet Output: " + hashSet); 
        // Output might be: [Apple, Zebra, Mango]

        // LinkedHashSet: Maintains insertion order
        Set<String> linkedHashSet = new LinkedHashSet<>();
        linkedHashSet.add("Zebra");
        linkedHashSet.add("Apple");
        linkedHashSet.add("Mango");
        
        // Duplicates are ignored, and do not affect the original position
        linkedHashSet.add("Apple"); 

        System.out.println("LinkedHashSet Output: " + linkedHashSet);
        // Output will always be: [Zebra, Apple, Mango]
    }
}

2. Intermediate Example: Removing Duplicates from a List While Preserving Order

A very common interview and real-world task is to take a List containing duplicate elements and remove the duplicates without scrambling the original order of the elements. LinkedHashSet is the perfect tool for this.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;

public class Deduplication {
    public static void main(String[] args) {
        List<Integer> numbersWithDuplicates = Arrays.asList(5, 2, 8, 2, 5, 1, 8);
        
        // Feed the list into a LinkedHashSet
        Set<Integer> uniqueNumbers = new LinkedHashSet<>(numbersWithDuplicates);
        
        // Convert back to a list if needed
        List<Integer> deduplicatedList = new ArrayList<>(uniqueNumbers);
        
        System.out.println("Original: " + numbersWithDuplicates);
        System.out.println("Deduplicated: " + deduplicatedList);
        // Output: [5, 2, 8, 1]
    }
}

Performance and Complexity

| Operation | LinkedHashSet Complexity | HashSet Complexity | TreeSet Complexity | | :--- | :--- | :--- | :--- | | add() | O(1) | O(1) | O(log N) | | contains() | O(1) | O(1) | O(log N) | | remove()| O(1) | O(1) | O(log N) | | Ordering | Insertion Order | Unordered | Sorted (Natural Order) |

Note: While LinkedHashSet provides O(1) operations, its constant factor is slightly higher than HashSet due to the overhead of updating the before and after pointers of the internal doubly-linked list on every insertion and deletion. It also consumes slightly more memory.

Common Mistakes Beginners Make

1. Forgetting to Override equals() and hashCode()

The Mistake: Using custom objects in a LinkedHashSet without overriding equals() and hashCode(). The Set will fall back to memory addresses, allowing logical duplicates to be added. The Fix: Always generate equals() and hashCode() methods in your custom classes when storing them in any Hash-based collection.

2. Assuming Thread Safety

The Mistake: Using LinkedHashSet across multiple threads concurrently. The Fix: LinkedHashSet is not thread-safe. If multiple threads modify it concurrently, you must wrap it: Collections.synchronizedSet(new LinkedHashSet<>()).

Interview Q&A

Q1: How does a LinkedHashSet handle the insertion of a duplicate element? Answer: It silently rejects the duplicate element. More importantly, attempting to add a duplicate element does not change its position in the insertion order. The original element remains exactly where it was.

Q2: What is the underlying data structure of a LinkedHashSet? Answer: It is backed by a LinkedHashMap. The elements you add to the Set act as the keys in the underlying map.

Q3: When should I choose LinkedHashSet over TreeSet? Answer: Choose LinkedHashSet when you want O(1) operations and simply need to remember the order in which elements were added. Choose TreeSet when you specifically need the elements to be sorted (e.g., alphabetically, ascending) and are okay with slower O(log N) operations.

Summary

• LinkedHashSet is a unique collection that implements Set and extends HashSet.
• It guarantees uniqueness (no duplicates).
• It maintains insertion order using an internal doubly-linked list (via LinkedHashMap).
• It provides O(1) time complexity for basic operations (add, remove, contains).
• It is the ideal data structure for deduplicating ordered data.