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

Operation	Time Complexity	Explanation
add()	O(1) average	Hash-based
remove()	O(1) average	Direct bucket removal
contains()	O(1) average	Hash lookup
iterate()	O(n)	Visit all elements

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

---

LinkedHashSet vs HashSet

Feature	LinkedHashSet	HashSet
Order	Maintains insertion order	No order guarantee
Underlying Data Structure	Hash table + linked list	Hash table
Duplicates	Not allowed	Not allowed
Null Elements	Allows one null	Allows one null
Performance (Add/Remove/Search)	Slightly slower than HashSet due to linked list overhead	Fastest (O(1) average)
Iteration	Predictable order (insertion order)	Unpredictable order
Memory Usage	Slightly higher (extra linked list pointers)	Lower (only hash table)
When to Use	When insertion order matters	When order does not matter, and performance is critical

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