LinkedHashSet in Java
Introduction
While HashSet is extremely fast (O(1) average time), it does not maintain any insertion order. If you iterate through a HashSet, elements appear in an unpredictable, random sequence.
To address this limitation, Java provides LinkedHashSet. A LinkedHashSet extends HashSet and implements the Set interface, using a doubly linked list running through all its entries to maintain their insertion order.
Why LinkedHashSet?
If you are building an application where entries must remain unique but their sequence is important—such as a Task Scheduling Order, a Most Recently Visited Pages List, or a Playlist Sorter—LinkedHashSet is the ideal collection:
// Standard HashSet (Unordered)
Set<String> hashSet = new HashSet<>();
hashSet.add("First");
hashSet.add("Second");
System.out.println(hashSet); // Output might be: [Second, First]
// LinkedHashSet (Insertion Order Preserved)
Set<String> linkedSet = new LinkedHashSet<>();
linkedSet.add("First");
linkedSet.add("Second");
System.out.println(linkedSet); // Output is guaranteed: [First, Second]
Features of LinkedHashSet
- No Duplicates: Duplicate elements are rejected automatically.
- Insertion Order: Iteration returns elements in the exact order they were inserted.
- Allows Nulls: Permits exactly one null element.
- Constant Time Operations: basic operations (
add,remove,contains) run inO(1)average time. - Higher Memory Footprint: Uses more memory than
HashSetto store the doubly linked node pointers (beforeandafter).
Creating a LinkedHashSet
Basic Initialization
import java.util.LinkedHashSet;
import java.util.Set;
// Generic format: Set<Type> setName = new LinkedHashSet<>();
Set<String> taskQueue = new LinkedHashSet<>();
Always use Wrapper classes instead of primitive types.
Common Methods
| Method | Description | Time Complexity |
|---|---|---|
add(E e) | Adds the element to the tail of the list if not present. | O(1) average |
remove(Object o) | Removes the element and updates linked list pointers. | O(1) average |
contains(Object o) | Returns true if the element exists. | O(1) average |
size() | Returns the count of elements. | O(1) |
clear() | Removes all entries. | O(N) |
Iterating Through a LinkedHashSet
Traversing a LinkedHashSet always yields elements in their exact insertion order:
Complete Programs
Example: Maintaining a Unique List of Visited URLs in Order
import java.util.LinkedHashSet;
import java.util.Set;
public class LinkedHashSetDemo {
public static void main(String[] args) {
Set<String> visitedUrls = new LinkedHashSet<>();
// 1. Visited pages sequence
visitedUrls.add("homepage.com");
visitedUrls.add("profile.com");
visitedUrls.add("settings.com");
visitedUrls.add("homepage.com"); // Duplicate entry ignored
// 2. Traversal order check
System.out.println("Browser History (Unique & Ordered):");
for (String url : visitedUrls) {
System.out.println(url);
}
// Output matches insertion order:
// homepage.com
// profile.com
// settings.com
}
}
Best Practices
- Prefer HashSet by default: Use
HashSetinstead ofLinkedHashSetunless you specifically need insertion order, to avoid the memory overhead of the doubly linked list. - Initial Capacity Bounds: Set the initial capacity if you know the maximum size to prevent rehashing:
Common Mistakes
- Assuming Sorting:
LinkedHashSetpreserves insertion order, not alphabetical or numeric sorted order. (UseTreeSetif sorting is required). - Element Modifications: Modifying properties of an object stored in the set can corrupt the internal hash buckets, making it impossible to find.
Key Takeaways
LinkedHashSetmaintains uniqueness while preserving insertion sequence.- It uses a doubly linked list running through hash buckets.
- Higher memory overhead than
HashSetdue to storing node pointer links.
Back to Sets Home: Sets Index