LinkedHashSet in Java

LinkedHashSet is a HashSet variant that maintains insertion order.

It is part of the java.util package and implements the Set interface.

What is LinkedHashSet in Java?

A LinkedHashSet is a collection that:

• Stores unique elements only (no duplicates)
• Maintains the insertion order
• Allows one null element
• Provides fast add, remove, and search operations (O(1) average)
• Internally uses a HashMap with a linked list to maintain order

Where LinkedHashSet Fits in Collection Hierarchy

Iterable
   └── Collection
          └── Set
                └── LinkedHashSet

Implements:

• Set
• Cloneable
• Serializable

Key Features of LinkedHashSet

• Unique elements only
• Maintains insertion order
• Allows one null
• Fast operations (O(1) average)
• No indexing like List
• Backed by HashMap + doubly linked list
• Resizes automatically (rehashing occurs when threshold is exceeded)

Internal Working of LinkedHashSet

LinkedHashSet internally uses a HashMap:

• Hashing determines the bucket
• Linked list maintains insertion order
• Each element becomes a key in HashMap with a dummy value

Internal Structure Diagram

Hash Table (Buckets) + Linked List
0 → [Java] → [Python] → [C++]
1 → [null]
2 → [HTML]

• The linked list preserves the order elements were added.
• Rehashing occurs if size exceeds capacity × load factor.

When to Use LinkedHashSet

Use LinkedHashSet when:

• You need unique elements
• Insertion order must be preserved
• Fast add, remove, and search are required

Avoid if:

• Sorting is required → Use TreeSet
• Index-based access is needed → Use ArrayList

Constructors of LinkedHashSet

Default Constructor

Creates an empty LinkedHashSet with default capacity and load factor.

LinkedHashSet<String> set = new LinkedHashSet<>();

With Initial Capacity

Creates a LinkedHashSet with a specified initial capacity to optimize memory if size is known.

LinkedHashSet<Integer> set = new LinkedHashSet<>(50);

With Initial Capacity + Load Factor

Creates a LinkedHashSet with specified capacity and load factor, controlling resizing behavior.

LinkedHashSet<String> set = new LinkedHashSet<>(32, 0.75f);

From Another Collection

Creates a LinkedHashSet containing all elements from another collection, preserving insertion order.

LinkedHashSet<String> set = new LinkedHashSet<>(list);

Common LinkedHashSet Methods

1. Add Methods

add(E e)

Adds a single element to the set; ignores duplicates.

LinkedHashSet<String> set = new LinkedHashSet<>();
set.add("Java");
set.add("Python");
set.add("Java"); // duplicate ignored
System.out.println(set); // [Java, Python]

addAll(Collection c)

Adds all elements from another collection; duplicates are ignored.

List<String> list = Arrays.asList("C++", "Python", "Go");
set.addAll(list);
System.out.println(set); // [Java, Python, C++, Go]

2. Search / Check Methods

contains(Object o)

Checks if a specific element exists in the set.

System.out.println(set.contains("Java")); // true
System.out.println(set.contains("Ruby")); // false

isEmpty()

Returns true if the set has no elements.

System.out.println(set.isEmpty()); // false

size()

Returns the total number of elements in the set.

System.out.println(set.size()); // 4

3. Remove Methods

remove(Object o)

Removes a specific element if it exists.

set.remove("Go");
System.out.println(set); // [Java, Python, C++]

clear()

Removes all elements from the set.

set.clear();
System.out.println(set); // []

removeAll(Collection c)

Removes all elements that are present in the given collection.

set.addAll(Arrays.asList("Java", "Python", "C++", "Go"));
set.removeAll(Arrays.asList("Python", "Go"));
System.out.println(set); // [Java, C++]

retainAll(Collection c)

Keeps only the elements that are present in the given collection; removes others.

set.retainAll(Arrays.asList("Java", "Ruby"));
System.out.println(set); // [Java]

4. Iteration

Iterator

Iterates through elements in insertion order using an Iterator.

Iterator<String> itr = set.iterator();
while(itr.hasNext()) {
    System.out.println(itr.next());
}

For-each Loop

Iterates over elements conveniently while preserving insertion order.

for(String s : set) {
    System.out.println(s);
}

Time Complexity

Note: Worst-case can degrade to O(n) with poor hashCode() implementation.

LinkedHashSet vs HashSet

Advantages of LinkedHashSet

• Maintains insertion order
• Unique elements
• Fast add, remove, and search (O(1) average)
• Allows null element
• Can create union, intersection, difference using addAll(), retainAll(), removeAll()

Disadvantages of LinkedHashSet

• No indexing
• Slightly higher memory usage than HashSet (linked list pointers)
• Worst-case performance degrades with poor hashing

Real-World Use Cases

• Maintain order + uniqueness (e.g., unique usernames)
• Remove duplicates while preserving order
• Cache unique items in insertion order
• Logging unique actions in order
• Tracking first occurrence of events

LinkedHashSet Example (Simple)

import java.util.LinkedHashSet;

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

        set.add("Java");
        set.add("Python");
        set.add("C++");
        set.add("Java"); // Duplicate ignored

        System.out.println(set);
    }
}

Output:

[Java, Python, C++]

Iteration Example

for(String s : set) {
    System.out.println(s);
}

Removing Duplicates While Preserving Order

List<Integer> list = Arrays.asList(10, 20, 10, 30, 20);

LinkedHashSet<Integer> unique = new LinkedHashSet<>(list);

System.out.println(unique); // [10, 20, 30]

Points to Remember

• LinkedHashSet = Unique + Ordered Set
• Maintains insertion order
• Internally uses HashMap + linked list
• Average performance: O(1)
• Use when uniqueness + order are important
• Avoid if sorting or index-based access is required