LinkedHashSet
What if you need the two most useful properties of a Set at the same time: no duplicates and predictable insertion order? HashSet gives you uniqueness, but it does not guarantee the order in which elements are returned. LinkedHashSet fills that gap.
LinkedHashSet is a Set implementation that combines hash-table-based lookup with a linked structure that maintains insertion order. It is especially useful when duplicate values must be eliminated without losing the order in which unique values first appeared.
Core Idea: LinkedHashSet gives you Set behavior for uniqueness while maintaining the order in which elements were inserted.
Why Does LinkedHashSet Exist?
Consider a system receiving a sequence of programming skills:
Java Spring SQL Java Docker Spring
You want to remove duplicates, but you also want the final result to follow the order in which each skill first appeared.
Set<String> skills = new LinkedHashSet<>();
skills.add("Java");
skills.add("Spring");
skills.add("SQL");
skills.add("Java");
skills.add("Docker");
skills.add("Spring");
System.out.println(skills);
The duplicate Java and Spring entries are ignored, while the original insertion order is preserved.
Simple analogy: Imagine a guest list where every guest can appear only once, but the list records people in the exact order in which they first arrived. That is the idea behind LinkedHashSet.
LinkedHashSet Hierarchy
LinkedHashSet extends HashSet and implements the Set contract.
Collection
|
+-- Set
|
+-- HashSet
|
+-- LinkedHashSet
This relationship means LinkedHashSet provides the same fundamental Set semantics as HashSet while adding predictable insertion-order iteration.
Creating a LinkedHashSet
import java.util.LinkedHashSet;
import java.util.Set;
public class Main {
public static void main(String[] args) {
Set<String> languages =
new LinkedHashSet<>();
languages.add("Java");
languages.add("C#");
languages.add("Python");
System.out.println(languages);
}
}
Using the Set interface as the reference type keeps the code focused on the behavior the application actually needs.
Adding Elements
LinkedHashSet uses the familiar add() method.
Set<String> languages =
new LinkedHashSet<>();
languages.add("Java");
languages.add("Spring");
languages.add("SQL");
System.out.println(languages);
The add() method returns true when the Set changes and false when an equal element already exists.
Set<String> languages =
new LinkedHashSet<>();
System.out.println(languages.add("Java"));
System.out.println(languages.add("Java"));
The first call returns true. The second returns false because Java is already present.
Duplicate Elements
Like every Set implementation, LinkedHashSet does not store duplicate elements according to the collection's equality rules.
Set<Integer> numbers =
new LinkedHashSet<>();
numbers.add(10);
numbers.add(20);
numbers.add(10);
numbers.add(30);
numbers.add(20);
System.out.println(numbers);
Only one occurrence of each distinct value is retained.
Insertion Order
The defining feature of LinkedHashSet is its predictable iteration order. Elements are iterated in the order in which they were inserted.
Set<String> names =
new LinkedHashSet<>();
names.add("Bibhu");
names.add("Rahul");
names.add("Priya");
for (String name : names) {
System.out.println(name);
}
The elements are visited as Bibhu, Rahul, and Priya because that is their insertion order.
Important: LinkedHashSet maintains insertion order, not sorted order. If you need alphabetical or numerical ordering, TreeSet is the more appropriate Set implementation.
What Happens When a Duplicate Is Added?
Adding an existing element does not create a second entry and does not move the existing element to the end.
Set<String> languages =
new LinkedHashSet<>();
languages.add("Java");
languages.add("Spring");
languages.add("SQL");
// Java already exists.
languages.add("Java");
System.out.println(languages);
Java remains in its original position. The failed duplicate insertion does not change its insertion-order position.
Remember: LinkedHashSet preserves the order of first insertion of each unique element. Adding the same element again does not move it.
How LinkedHashSet Works Internally
LinkedHashSet combines two ideas: hash-based storage and linked ordering information.
LinkedHashSet
|
+-----------+-----------+
| |
Hash-based lookup Linked order
| |
hashCode() insertion sequence
|
equals()
The hash-based portion helps provide efficient average-case membership operations. The linked structure maintains the predictable order used during iteration.
This extra ordering information is the major structural difference between LinkedHashSet and HashSet.
LinkedHashSet vs HashSet
| Feature | HashSet | LinkedHashSet |
|---|---|---|
| Duplicates | Not allowed | Not allowed |
| Insertion order | Not guaranteed | Maintained |
| Sorted order | No | No |
| Average add() | O(1) | O(1) |
| Average contains() | O(1) | O(1) |
| Average remove() | O(1) | O(1) |
| Memory overhead | Lower than LinkedHashSet | Higher because ordering links are maintained |
| Typical use | Unique elements without ordering requirements | Unique elements while preserving insertion order |
The additional linked structure means LinkedHashSet generally uses more memory than HashSet. That trade-off is worthwhile when predictable iteration order matters.
Checking for an Element
The contains() method checks whether an equal element exists.
Set<String> skills =
new LinkedHashSet<>();
skills.add("Java");
skills.add("Spring");
skills.add("SQL");
if (skills.contains("Spring")) {
System.out.println("Spring exists");
}
Hashing is used to make this lookup efficient on average.
Removing Elements
Set<String> skills =
new LinkedHashSet<>();
skills.add("Java");
skills.add("Spring");
skills.add("SQL");
skills.remove("Spring");
System.out.println(skills);
The remove() method returns true when an element was actually removed and false when no equal element existed.
Checking Size and Empty State
Set<String> skills =
new LinkedHashSet<>();
skills.add("Java");
skills.add("Spring");
System.out.println(skills.size());
System.out.println(skills.isEmpty());
size() reports the number of unique elements, while isEmpty() checks whether the Set contains no elements.
Iterating Through LinkedHashSet
The enhanced for loop is a natural way to traverse a LinkedHashSet.
Set<String> skills =
new LinkedHashSet<>();
skills.add("Java");
skills.add("Spring");
skills.add("SQL");
for (String skill : skills) {
System.out.println(skill);
}
Unlike HashSet, the iteration order here is predictable: Java, Spring, then SQL.
Using Iterator
Iterator<String> iterator =
skills.iterator();
while (iterator.hasNext()) {
String skill = iterator.next();
System.out.println(skill);
}
The Iterator follows the same insertion order used by the Set's normal iteration.
Removing During Iteration
If you need to remove the current element while iterating, use the Iterator's remove() method rather than structurally modifying the Set directly through the collection reference.
Iterator<String> iterator =
skills.iterator();
while (iterator.hasNext()) {
String skill = iterator.next();
if (skill.equals("SQL")) {
iterator.remove();
}
}
This provides a controlled way to remove the element currently being processed.
LinkedHashSet and Null
LinkedHashSet permits a single null element.
Set<String> values =
new LinkedHashSet<>();
values.add("Java");
values.add(null);
values.add(null);
System.out.println(values);
Only one null is retained because duplicates are not permitted.
Remember: LinkedHashSet can contain one null element, but whether null should be used is a separate design decision.
LinkedHashSet and Custom Objects
Just like HashSet, LinkedHashSet depends on equals() and hashCode() when determining whether custom objects are duplicates.
class Product {
private int id;
public Product(int id) {
this.id = id;
}
@Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (!(obj instanceof Product)) {
return false;
}
Product other = (Product) obj;
return id == other.id;
}
@Override
public int hashCode() {
return Integer.hashCode(id);
}
}
Two Product objects with the same logical ID are therefore treated as equal.
Set<Product> products =
new LinkedHashSet<>();
products.add(new Product(101));
products.add(new Product(102));
products.add(new Product(101));
System.out.println(products.size());
The Set contains two unique products. The first Product with ID 101 determines the position of that logical element in the insertion order.
Removing Duplicates While Preserving Order
This is one of the most practical uses of LinkedHashSet.
List<String> languages =
new ArrayList<>();
languages.add("Java");
languages.add("Spring");
languages.add("Java");
languages.add("SQL");
languages.add("Spring");
languages.add("Docker");
Set<String> uniqueLanguages =
new LinkedHashSet<>(languages);
System.out.println(uniqueLanguages);
The duplicate values disappear while the first-seen order is retained.
This pattern is useful when processing user input, imported records, tags, categories, search results, or any sequence where duplicates should be removed without rearranging the surviving values.
Converting LinkedHashSet Back to a List
After removing duplicates, you may want the result as a List again.
List<String> uniqueLanguages =
new ArrayList<>(
new LinkedHashSet<>(languages)
);
System.out.println(uniqueLanguages);
The resulting List retains the insertion order established by LinkedHashSet.
LinkedHashSet and Sorting
LinkedHashSet does not automatically sort its elements.
Set<String> languages =
new LinkedHashSet<>();
languages.add("Python");
languages.add("Java");
languages.add("C#");
System.out.println(languages);
The order reflects insertion, not alphabetical ordering.
If sorted order is the requirement, use TreeSet.
Set<String> languages =
new TreeSet<>();
languages.add("Python");
languages.add("Java");
languages.add("C#");
System.out.println(languages);
Decision Rule: HashSet means unique without guaranteed order. LinkedHashSet means unique plus insertion order. TreeSet means unique plus sorted order.
LinkedHashSet vs TreeSet
| Feature | LinkedHashSet | TreeSet |
|---|---|---|
| Duplicates | Not allowed | Not allowed |
| Insertion order | Maintained | Not maintained as its ordering model |
| Sorted order | No | Yes |
| Typical add() | O(1) average | O(log n) |
| Typical contains() | O(1) average | O(log n) |
| Typical use | Unique values in first-seen order | Unique values in sorted order |
When Should You Use LinkedHashSet?
LinkedHashSet is a strong choice when both uniqueness and insertion order are meaningful parts of the requirement.
- Remove duplicates while preserving the first-seen order.
- Store unique configuration values in a predictable iteration order.
- Process unique user-provided items without rearranging them.
- Maintain unique tags or categories in the order they were discovered.
- Produce deterministic iteration output without requiring sorted ordering.
When Should You Not Use LinkedHashSet?
LinkedHashSet is not automatically the best Set implementation. Choosing it when its ordering guarantee provides no value simply adds unnecessary structural overhead.
- Use HashSet when ordering does not matter and you only need uniqueness.
- Use TreeSet when sorted ordering is required.
- Use ArrayList when duplicates and positional access are required.
- Use ArrayDeque when the problem is specifically a queue or double-ended queue.
Performance Considerations
LinkedHashSet generally provides average-case O(1) performance for fundamental hash-based operations, similar to HashSet, while maintaining additional linked information for insertion order.
| Operation | Typical Average Complexity | Notes |
|---|---|---|
| add() | O(1) | Hash-based insertion with ordering information. |
| contains() | O(1) | Hash-based membership lookup. |
| remove() | O(1) | Hash-based lookup plus linked-order maintenance. |
| size() | O(1) | Returns the current number of elements. |
| Iteration | O(n) | Traverses the maintained insertion-order chain. |
The exact performance can depend on hashing behavior, collisions, collection size, and implementation details. The practical trade-off is straightforward: LinkedHashSet pays some additional memory overhead to provide predictable ordering.
LinkedHashSet and Mutable Objects
The same caution that applies to HashSet also applies here. If fields used by equals() or hashCode() are changed after an object has been inserted, the object's hash-based lookup behavior can become problematic.
Best Practice: Avoid changing equality-defining state while an object is stored inside LinkedHashSet. Prefer immutable objects when practical.
Common Beginner Mistakes
- Confusing insertion order with sorted order: LinkedHashSet preserves insertion order; it does not sort elements.
- Expecting duplicate insertion to move an element: Adding an existing element does not move it to the end.
- Using LinkedHashSet when order is irrelevant: HashSet may be a simpler and more memory-efficient choice.
- Using LinkedHashSet for sorted data: TreeSet is designed for sorted Set behavior.
- Ignoring equals() and hashCode(): Custom objects need a consistent equality contract.
- Mutating hash-relevant fields: Changing equality-defining state after insertion can break expected lookup behavior.
- Assuming thread safety: LinkedHashSet is not inherently thread-safe.
Best Practices
- Use LinkedHashSet when uniqueness and insertion-order iteration are both requirements.
- Declare the reference using Set when implementation-specific operations are unnecessary.
- Use HashSet when ordering does not matter.
- Use TreeSet when sorted ordering is required.
- Implement equals() and hashCode() consistently for custom elements.
- Avoid mutating fields involved in equality or hashing while elements are stored in the Set.
- Do not assume LinkedHashSet is thread-safe.
Interview Insights
Question: What is LinkedHashSet?
Answer: LinkedHashSet is a Set implementation that prevents duplicates and maintains the insertion order of its elements during iteration.
Question: How is LinkedHashSet different from HashSet?
Answer: Both prevent duplicates and provide hash-based average-case operations, but LinkedHashSet additionally maintains insertion order.
Question: Does LinkedHashSet sort its elements?
Answer: No. It maintains insertion order. TreeSet should be used when sorted order is required.
Question: What happens when a duplicate element is inserted?
Answer: The duplicate is not added, add() returns false, and the existing element retains its original insertion-order position.
Question: Why does LinkedHashSet require more memory than HashSet?
Answer: LinkedHashSet maintains additional links that preserve insertion order, creating extra memory overhead compared with a basic HashSet.
Quick Revision
| Concept | Key Point |
|---|---|
| LinkedHashSet | Set implementation that combines uniqueness with insertion-order iteration. |
| Duplicates | Not allowed. |
| Insertion order | Maintained during iteration. |
| Sorted order | Not provided. |
| add() | Returns true when a new unique element is inserted. |
| contains() | Provides hash-based membership checking. |
| Null | A single null element is permitted. |
| Average add/contains/remove | Typically O(1). |
| Memory | Generally higher than HashSet because insertion-order links are maintained. |
| HashSet alternative | Use when ordering does not matter. |
| TreeSet alternative | Use when sorted order is required. |
LinkedHashSet is a great example of choosing a collection based on a precise requirement rather than simply choosing the most familiar class. If your application needs unique elements in the order they were first encountered, LinkedHashSet expresses that requirement cleanly. Once you understand the difference between HashSet, LinkedHashSet, and TreeSet, selecting the right Set implementation becomes much more straightforward. In the next chapter, we will explore TreeSet and see how Java maintains unique elements in sorted order.