LinkedHashSet

TL;DR

• LinkedHashSet extends HashSet and implements the Set interface.
• Like HashSet, it allows no duplicates.
• Crucial Difference: It maintains insertion order. The elements will iterate in the exact order you added them.

Concept

A standard HashSet places elements in random buckets based on their hash code, meaning when you iterate over it, the order looks scrambled.

LinkedHashSet solves this. Under the hood, it is backed by a LinkedHashMap. In addition to the hash table array, it maintains a doubly-linked list running through all of its entries.
This linked list defines the iteration ordering, which is the order in which elements were inserted into the set.

Performance

It offers the same $O(1)$ constant time for basic operations (add, remove, contains) as HashSet. However, performance is slightly slower than a regular HashSet because it has the extra overhead of maintaining the linked list pointers on every insertion and deletion.

Examples

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

public class LinkedHashSetExample {
    public static void main(String[] args) {
        
        // --- HashSet (Scrambled Order) ---
        Set<String> hashSet = new HashSet<>();
        hashSet.add("Zebra");
        hashSet.add("Apple");
        hashSet.add("Monkey");
        // Output might be: [Apple, Zebra, Monkey]
        System.out.println("HashSet: " + hashSet);
        
        // --- LinkedHashSet (Preserved Order) ---
        Set<String> linkedSet = new LinkedHashSet<>();
        linkedSet.add("Zebra");
        linkedSet.add("Apple");
        linkedSet.add("Monkey");
        // Output WILL ALWAYS BE: [Zebra, Apple, Monkey]
        System.out.println("LinkedHashSet: " + linkedSet);
    }
}

Interview Questions

Q: If you re-insert an existing element into a LinkedHashSet, does the insertion order change?
A: No. If you try to add an element that is already present in the LinkedHashSet, the add() operation is ignored (returns false). The original element remains untouched, and its original position in the insertion-order linked list is preserved.

Q: When should you use LinkedHashSet over HashSet or TreeSet?
A: - Use HashSet if you don’t care about order and want the absolute best performance.

• Use TreeSet if you need the elements to be inherently sorted (e.g., A-Z, 1-100).
• Use LinkedHashSet when you need to remove duplicates but strictly preserve the exact chronological order in which the data arrived.