Java LinkedHashSet

Java LinkedHashSet

java.util.LinkedHashSet<E> solves a very specific problem that HashSet cannot: it maintains the order in which elements were inserted while still rejecting duplicates and providing O(1) contains(). When you need a collection that is simultaneously unique, fast for membership checks, and predictable in its iteration order, LinkedHashSet is the correct default.

The distinction matters in production more than beginners expect. API responses, audit logs, and deduplication pipelines where the "first seen" order of items is meaningful — these all need LinkedHashSet, not HashSet.

What Is Java LinkedHashSet?

LinkedHashSet<E> is a concrete class in java.util that extends HashSet<E> and implements Set<E>. It adds one guarantee that HashSet cannot provide: iteration always produces elements in the order they were first inserted. Duplicates are still rejected, contains() is still O(1) average, and add() is still O(1) average — the only cost over HashSet is a small memory overhead per element for the linked list that tracks insertion order.

The diagram below shows where LinkedHashSet sits in the Collections hierarchy and how it compares to the other two Set implementations.

java.lang.Iterable<E>
    └── java.util.Collection<E>
            └── java.util.Set<E>               ← uniqueness contract
                    ├── java.util.HashSet<E>    ← hash table, NO order guarantee
                    │       └── LinkedHashSet   ← extends HashSet, INSERTION ORDER
                    └── java.util.SortedSet<E>
                            └── NavigableSet<E>
                                    └── TreeSet ← Red-Black tree, SORTED ORDER

KEY FACTS:
  Package    : java.util
  Since      : Java 1.4
  Extends    : HashSet<E>
  Backed by  : LinkedHashMap<E, Object> internally
  Ordering   : insertion order — elements iterate in the order they were first added
  Null       : allows exactly one null element
  Duplicates : rejected — add() returns false for existing elements
  Thread     : NOT thread-safe
  Initial capacity: 16 buckets (default)
  Load factor     : 0.75

The Three Set Implementations — Key Differences

FEATURE COMPARISON:

  Feature                HashSet          LinkedHashSet       TreeSet
  ---------------------- ---------------- ------------------- ------------------
  Ordering               None             Insertion order     Natural/Comparator
  add() / contains()     O(1) average     O(1) average        O(log n)
  Backed by              HashMap          LinkedHashMap        TreeMap
  Memory per element     Moderate         Slightly higher      Higher (tree node)
  Null allowed           Yes (1)          Yes (1)             No
  floor/ceiling/headSet  No               No                  Yes
  Best for               Pure speed       Order + uniqueness  Sorted unique set

When to Use LinkedHashSet

The decision between the three Set implementations follows a clear priority order.

CHOOSE LinkedHashSet WHEN:
  1. Elements must be unique AND iteration order must match insertion order
     — e.g., deduplicated list of recently visited pages, ordered unique tags
  2. Producing deterministic output from a Set for display, logging, or API responses
     — HashSet iteration order is undefined and can change between JVM runs
  3. "First seen wins" deduplication where the position of first occurrence matters
     — e.g., first unique city in a stream of user locations

CHOOSE HashSet INSTEAD WHEN:
  - Order is completely irrelevant AND maximum speed is the priority
  - HashSet is marginally faster than LinkedHashSet — no linked list to update

CHOOSE TreeSet INSTEAD WHEN:
  - Sorted order is required (ascending or via Comparator)
  - Range operations are needed: headSet(), tailSet(), floor(), ceiling()
  - The cost of O(log n) per operation is acceptable for sorted access

CHOOSE ArrayList or LinkedHashMap INSTEAD WHEN:
  - Duplicates are needed alongside ordered access (use ArrayList)
  - Key-value pairs are needed with insertion order (use LinkedHashMap)

A pattern that appears in production code:
  Use HashSet during processing (fastest contains and add),
  then wrap in new LinkedHashSet<>(hashSet) when deterministic output is needed.
  This costs one O(n) conversion instead of paying the LinkedHashSet overhead for
  the entire processing phase.

How LinkedHashSet Works Internally

LinkedHashSet is implemented as a thin wrapper around LinkedHashMap — just like HashSet wraps HashMap. The crucial difference is the backing map.

HASHSET internals:
  HashMap<E, Object> map
  — hash table only, no ordering

LINKEDHASHSET internals:
  LinkedHashMap<E, Object> map
  — hash table PLUS a doubly-linked list threading all entries in insertion order

Every add(e) call maps to:
  map.put(e, PRESENT)
  LinkedHashMap.put() does two things:
    1. Adds the key to the hash table bucket (same as HashMap)
    2. Appends the entry to the tail of the linked list

STRUCTURE AFTER:
  set.add("C"); set.add("A"); set.add("B"); set.add("A"); // duplicate

  HASH TABLE:
    bucket[2]: Entry("C") → null
    bucket[7]: Entry("A") → null
    bucket[4]: Entry("B") → null

  DOUBLY-LINKED LIST (tracks insertion order):
    HEAD → [Entry("C")] ↔ [Entry("A")] ↔ [Entry("B")] → null
                                                               TAIL

  Iteration traverses the linked list — always C, A, B.
  "A" duplicate was rejected: map.put("A", PRESENT) returned PRESENT (old value),
  so add() returned false and NO new entry was appended to the linked list.

  set.size()  → 3  (C, A, B)
  iteration   → C, A, B  (insertion order preserved)

The diagram below shows the full internal structure for a LinkedHashSet with four elements.

LINKEDHASHSET WITH ELEMENTS ["Mumbai", "Delhi", "Chennai", "Bengaluru"]:

  HASH TABLE (array of buckets):
    bucket[3]:  Entry("Mumbai")    → null
    bucket[7]:  Entry("Delhi")     → null
    bucket[1]:  Entry("Chennai")   → Entry("Bengaluru") → null  (collision)
    ...rest:    null

  LINKED LIST (insertion order):
    HEAD
     ↓
    [before=HEAD | "Mumbai"    | after=Delhi]
         ↓
    [before=Mumbai | "Delhi"   | after=Chennai]
         ↓
    [before=Delhi | "Chennai"  | after=Bengaluru]
         ↓
    [before=Chennai | "Bengaluru" | after=TAIL]
     ↓
    TAIL

  Each Entry has FOUR references:
    hash, key, value (PRESENT)  ← HashMap fields
    before, after               ← LinkedHashMap linked-list fields

  Iterator traverses before→after pointers — O(1) per step, O(n) total.
  Result: Mumbai, Delhi, Chennai, Bengaluru — always, regardless of bucket layout.

Core Operations with Examples

add() — Insertion Order Guaranteed

Output:
=== add() return values ===
add(/home)        : true
add(/products)    : true
add(/cart)        : true
add(/home)        : false — duplicate
add(/checkout)    : true
add(/products)    : false — duplicate
add(/confirmation): true

Insertion order preserved: [/home, /products, /cart, /checkout, /confirmation]
Size (unique only): 5

=== Iteration order comparison ===
LinkedHashSet (insertion order): [/home, /products, /cart, /checkout, /confirmation]
HashSet       (no order)       : [/cart, /home, /checkout, /products, /confirmation]

=== Null element ===
Set with null: [first, null, third]
null at its insertion position: index 1

contains(), remove(), and Bulk Operations

Output:
=== contains() — O(1) average ===
contains(DarkMode)   : true
contains(ChatSupport): false

=== remove() — preserves order of remaining ===
Before     : [DarkMode, BetaSearch, NewCheckout, LiveTracking, AIRecommendations]
After remove(BetaSearch): [DarkMode, NewCheckout, LiveTracking, AIRecommendations]

=== removeIf() — insertion order preserved ===
After removeIf(starts with New): [DarkMode, LiveTracking, AIRecommendations]

=== Set operations ===
User permissions: [READ, WRITE, DELETE, ADMIN, EXPORT]
Role permissions: [READ, WRITE, COMMENT]
Granted (intersection): [READ, WRITE]
Exclusive to user     : [DELETE, ADMIN, EXPORT]
Union (all)           : [READ, WRITE, DELETE, ADMIN, EXPORT, COMMENT]

Deduplication While Preserving First-Occurrence Order

This is the most common production use case for LinkedHashSet — converting a list with duplicates into a list of unique elements in the order they first appeared.

Output:
Raw (with duplicates): [laptop, laptop bag, laptop, laptop stand, laptop cooling pad, laptop bag, laptop, laptop sleeve]
Deduplicated (first-seen order): [laptop, laptop bag, laptop stand, laptop cooling pad, laptop sleeve]
Back to List: [laptop, laptop bag, laptop stand, laptop cooling pad, laptop sleeve]

HashSet dedup (no order)       : [laptop stand, laptop bag, laptop, laptop cooling pad, laptop sleeve]
LinkedHashSet dedup (ordered)  : [laptop, laptop bag, laptop stand, laptop cooling pad, laptop sleeve]

Raw scores: [92, 85, 92, 78, 85, 100, 78, 95]
Unique scores (first-seen order): [92, 85, 78, 100, 95]
Stream distinct (same result)   : [92, 85, 78, 100, 95]

Basic Example

This example shows the core behaviour of LinkedHashSet: it rejects duplicates like any Set, but it always iterates elements in the order they were first added.

Output

[Delhi, Mumbai, Chennai]
Size: 3

How it works:

1. ›LinkedHashSet behaves like a HashSet for uniqueness — adding "Delhi" a second time has no effect because it is already present.
2. ›Unlike HashSet, it also remembers the order elements were first inserted, so printing it always shows Delhi, Mumbai, Chennai in that exact order.
3. ›This combination — no duplicates plus predictable order — is why LinkedHashSet is a common choice when you need to deduplicate a list of items while keeping their first-seen order.

Performance Considerations

Iteration difference: LinkedHashSet iterates in O(n) by following linked-list before/after pointers — it does not scan empty buckets. HashSet iterates in O(n + capacity) because it scans all bucket slots including empty ones. For a HashSet pre-sized to 10,000 that holds 5 elements, iteration touches 10,000 slots. LinkedHashSet touches only the 5 elements.

Memory cost: Each entry in LinkedHashSet carries two extra references compared to HashSet — the before and after pointers for the doubly-linked list. On a 64-bit JVM with compressed references, this is approximately 8 extra bytes per entry. For most applications this is negligible. For extremely large sets in memory-constrained environments, HashSet is the leaner choice.

Thread safety: LinkedHashSet is not thread-safe. For concurrent ordered-set access, there is no direct concurrent equivalent. The common workaround is Collections.synchronizedSet(new LinkedHashSet<>()) or, for high-concurrency, use ConcurrentHashMap.newKeySet() (which provides no ordering) and manage ordering separately.

Best Practices

Declare the variable as Set<E> or LinkedHashSet<E> based on whether ordered iteration is part of the contract. If a method signature uses Set<E>, callers can pass any Set implementation. If ordered iteration is required by the caller — for display, for deterministic test output, for serialisation — declare LinkedHashSet<E> explicitly so the ordering guarantee is visible in the API. Using Set<E> for a variable that must preserve insertion order hides a contract that callers may rely on.

Use new LinkedHashSet<>(collection) for order-preserving deduplication. It processes the entire collection in one O(n) pass, preserves the first occurrence of each element, and is cleaner than manual loop-based deduplication. new ArrayList<>(new LinkedHashSet<>(list)) is the idiomatic one-liner for converting a list with duplicates to a deduplicated list in first-occurrence order.

Prefer LinkedHashSet over HashSet when writing unit tests that compare set contents. Tests that assert assertEquals(expectedSet, actualSet) with HashSet may produce confusing failure messages — the order of elements in the string representation is non-deterministic. LinkedHashSet produces consistent string output, making test failures readable. Wrap the actual result in new LinkedHashSet<>(actual) in assertions where order matters.

Do not use LinkedHashSet as a substitute for List when duplicates are intentional. LinkedHashSet is a Set — it rejects duplicates. If the business logic needs to count occurrences, maintain position including duplicates, or allow the same element at multiple positions, use a List. LinkedHashSet is only correct when uniqueness and ordered iteration are both required simultaneously.

Common Mistakes

Mistake 1 — Expecting Re-insertion to Update Position

Mistake 2 — Using LinkedHashSet When TreeSet Is Needed for Sorted Order

Mistake 3 — Mutating an Element's hashCode-Relevant Field After Insertion

Mistake 4 — Using LinkedHashSet for Thread-Safe Ordered Sets Without Synchronisation

Interview Questions

Q1. What is LinkedHashSet in Java and how does it differ from HashSet?

LinkedHashSet extends HashSet and adds one guarantee: iteration always produces elements in the order they were inserted. HashSet makes no ordering guarantee — elements can iterate in any order, and that order may change after rehashing. Internally, LinkedHashSet is backed by LinkedHashMap instead of HashMap. LinkedHashMap maintains a doubly-linked list threading all entries in insertion order alongside the hash table. This linked list is what LinkedHashSet's iterator traverses, giving O(n) iteration with predictable order. Both HashSet and LinkedHashSet provide O(1) average add(), remove(), and contains().

Q2. What is the internal structure of LinkedHashSet?

LinkedHashSet is backed by a LinkedHashMap<E, Object> where each element becomes a key and a shared static PRESENT dummy object is the value. LinkedHashMap extends HashMap and maintains a doubly-linked list of all entries using before and after pointers on each Entry. When add(element) is called, LinkedHashMap.put(element, PRESENT) adds the entry to both the hash table bucket and the tail of the doubly-linked list. Iteration follows the linked list from head to tail, producing insertion order. Removal updates both the hash table and the linked list pointers in O(1).

Q3. Does re-inserting an existing element change its position in LinkedHashSet?

No. add(element) on an already-present element returns false and makes no structural change — the element stays at its original insertion position. If you need the element to move to the end (as in an LRU-style structure), you must explicitly remove(element) first and then add(element) again. This is a common misconception and a common interview follow-up question — the answer is: LinkedHashSet preserves the position of the first insertion, not the most recent access.

Q4. Why does LinkedHashSet iterate faster than HashSet for full traversals?

HashSet iteration is O(n + capacity) because it scans all bucket slots in the backing HashMap array, including empty slots. For a HashSet with capacity 10,000 but only 5 elements, iteration examines 10,005 slots. LinkedHashSet iteration is O(n) because it follows the doubly-linked list pointers — it touches only the n live entries, skipping all empty buckets entirely. For sets with low load relative to capacity, LinkedHashSet's iterator is measurably faster despite the slightly higher per-entry memory cost.

Q5. When would you choose LinkedHashSet over a List for storing unique ordered elements?

Use LinkedHashSet when contains() or remove() is called frequently and the number of elements is large enough that O(n) list-scan would be slow. LinkedHashSet.contains() is O(1); ArrayList.contains() is O(n). For displaying a deduplicated stream of events in arrival order, or checking membership in a "visited" set while maintaining traversal order, LinkedHashSet handles both in one data structure. Use ArrayList when duplicates are intentional or when index-based access (get(i)) is needed — LinkedHashSet has no get(index) method.

Q6. How does LinkedHashSet handle the equals() and hashCode() contract?

Identically to HashSet — because it inherits the same HashMap-based lookup mechanism through LinkedHashMap. Two elements that are equal by equals() must produce the same hashCode(). If hashCode() is not overridden alongside equals(), two logically equal objects land in different buckets, and the set stores both — silently violating uniqueness. The linked list in LinkedHashMap does not help with this — it only tracks insertion order of keys that the hash table has already accepted. Correct equals() and hashCode() implementation is as critical for LinkedHashSet as it is for HashSet.

FAQs

Does LinkedHashSet maintain sorted order?

No. LinkedHashSet maintains insertion order — the order elements were first added. For sorted order (alphabetical or numeric), use TreeSet. For insertion order with uniqueness, use LinkedHashSet. These are distinct guarantees. A LinkedHashSet populated with {"B", "A", "C"} iterates as B, A, C. A TreeSet with the same elements iterates as A, B, C.

How do you convert a List with duplicates to a List with unique elements in first-occurrence order?

new ArrayList<>(new LinkedHashSet<>(originalList)) is the idiomatic one-liner. new LinkedHashSet<>(originalList) deduplicates in one O(n) pass, preserving first-occurrence order. Wrapping in new ArrayList<>() gives back a list with index access. Alternatively, originalList.stream().distinct().collect(Collectors.toList()) achieves the same result for List sources.

What is the memory difference between HashSet and LinkedHashSet?

Each entry in LinkedHashSet carries two additional references compared to HashSet: the before and after pointers for the doubly-linked list. On a 64-bit JVM with compressed references, this adds approximately 8 bytes per entry. For a set of 1,000,000 elements, the overhead difference is roughly 8 MB. For most applications this is negligible; for memory-constrained services with very large sets, HashSet is the leaner choice.

Is LinkedHashSet thread-safe?

No. LinkedHashSet is not thread-safe. Concurrent modification from multiple threads can corrupt both the hash table and the doubly-linked list. For thread-safe ordered set access, wrap it: Collections.synchronizedSet(new LinkedHashSet<>()). All iteration must be done inside a synchronized block on the wrapper. For high-concurrency scenarios, there is no direct concurrent LinkedHashSet equivalent — consider ConcurrentHashMap.newKeySet() (unordered, faster) or managing a separate ordering structure alongside a concurrent set.

Can LinkedHashSet be used as a queue with unique elements?

Yes — this is a practical use case. LinkedHashSet supports add() at the tail (end), iteration in insertion order, and iterator.remove() for removal during traversal. For a queue where each item should be processed at most once, LinkedHashSet prevents re-queuing the same item and guarantees FIFO processing order. To remove and process the first element: Iterator<E> it = set.iterator(); E first = it.next(); it.remove();. For high-throughput concurrent scenarios, LinkedBlockingQueue combined with a Set is more appropriate.

How does LinkedHashSet compare to a List for tracking visited items in order?

A List preserves insertion order and allows contains(), but contains() is O(n) — scanning every element. For a visited-items tracker that checks membership on every incoming item, O(n) per check produces O(n²) total. LinkedHashSet.contains() is O(1) average. Use LinkedHashSet when both "have I seen this before?" checks and ordered traversal are needed on the same collection. Use a List only when duplicates are intentional or index-based access is required.

Summary

LinkedHashSet<E> is the correct Set implementation when two requirements must be satisfied simultaneously: no duplicate elements and a predictable iteration order that matches insertion sequence. Backed by LinkedHashMap, it maintains a doubly-linked list of all entries alongside the hash table. add(), remove(), and contains() are O(1) average — identical to HashSet. The only cost is slightly more memory per entry and a marginally slower add() due to linked-list pointer maintenance.

The canonical use case: order-preserving deduplication. new LinkedHashSet<>(list) deduplicates a list in one pass, keeping the first occurrence of each element in position. new ArrayList<>(new LinkedHashSet<>(list)) gets back a list.

For interviews: explain the LinkedHashMap backing and the doubly-linked before/after pointers, clarify that re-insertion does not move an element's position, describe the O(n) iteration advantage over HashSet due to linked-list traversal versus bucket scanning, and distinguish insertion order (LinkedHashSet) from sorted order (TreeSet).

What to Read Next