LinkedHashSet
LinkedHashSet is an implementation of the Set interface that combines the uniqueness guarantee of HashSet with the predictable iteration order of a linked list. It is used when you need unique elements while preserving insertion order. This is a common interview topic, often compared with HashSet and TreeSet.
What Is LinkedHashSet?
- Implementation of Set
- Stores unique elements only
- Maintains insertion order
- Allows one null value
- Part of java.util package
Set<String> set = new LinkedHashSet<>();
Position in Collection Hierarchy
Iterable
└── Collection
└── Set
└── LinkedHashSet
How LinkedHashSet Works Internally (Interview Favorite)
- Backed by a LinkedHashMap
- Uses hash table + doubly linked list
- Hash table → fast lookup
- Linked list → preserves insertion order
HashMap + LinkedList = LinkedHashSet
Key Characteristics of LinkedHashSet
- Maintains insertion order
- No duplicate elements
- Faster than TreeSet
- Slightly slower than HashSet
- Not synchronized (not thread-safe)
Creating a LinkedHashSet
LinkedHashSet<Integer> set = new LinkedHashSet<>();
Commonly Used Methods
set.add(10);
set.add(20);
set.add(10); // duplicate ignored
set.remove(20);
set.contains(10);
set.size();
Order Preservation Example
LinkedHashSet<String> set = new LinkedHashSet<>();
set.add("Java");
set.add("Python");
set.add("C++");
System.out.println(set);
Output:
[Java, Python, C++]
- ✔ Order preserved
- ✔ Duplicates ignored
Performance Complexity
| Operation | Time Complexity |
|---|---|
| add | O(1) |
| remove | O(1) |
| contains | O(1) |
| iteration | O(n) |
Null Handling
- Allows one null element
set.add(null);
- ✔ Allowed
- ❌ Second null ignored
LinkedHashSet vs HashSet vs TreeSet
| Feature | HashSet | LinkedHashSet | TreeSet |
|---|---|---|---|
| Order | ❌ No | ✔ Insertion | ✔ Sorted |
| Performance | Fastest | Slightly slower | Slowest |
| Null allowed | ✔ One | ✔ One | ❌ No |
| Internal DS | HashMap | LinkedHashMap | Tree |
When to Use LinkedHashSet
- Uniqueness is required
- Insertion order must be preserved
- Fast lookup needed
- Predictable iteration order
When NOT to Use LinkedHashSet
- Sorting is required
- Memory usage must be minimal
- Order does not matter (use HashSet)
Common Beginner Mistakes
- Assuming sorted order
- Using LinkedHashSet unnecessarily when HashSet is sufficient
- Ignoring memory overhead
- Forgetting equals() and hashCode() importance
Interview-Ready Answers
Short Answer
LinkedHashSet is a Set implementation that maintains insertion order.
Detailed Answer
In Java, LinkedHashSet extends HashSet and uses a LinkedHashMap internally to store unique elements while preserving insertion order. It provides constant-time performance and predictable iteration order.
Key Takeaway
LinkedHashSet = HashSet + Order Preservation. Use it when you need unique elements with predictable iteration order.