00:00

Help Us Improve

We're sorry this tutorial wasn't helpful. Please tell us what we can do better.

Difference Between LinkedHashSet and TreeSet in Java

LinkedHashSet and TreeSet are both Set implementations with a predictable iteration order, but the order means different things:

  • LinkedHashSet keeps elements in insertion order, using a hash table plus a linked list. Operations are O(1).
  • TreeSet keeps elements sorted (natural order or a Comparator), using a red-black tree. Operations are O(log n), and it offers navigation methods such as first, ceiling and headSet.

1. Comparison Table

AspectLinkedHashSetTreeSet
OrderInsertion orderSorted (ascending, or by comparator)
Internal structureLinkedHashMap (hash table + doubly linked list)TreeMap (red-black tree)
add / remove / containsO(1) averageO(log n)
Duplicate detectionhashCode() + equals()compareTo() or compare()
NullOne null allowedNot allowed (with natural ordering)
Element requirementAny objectMust be Comparable, or supply a Comparator
InterfacesSequencedSetNavigableSet, SortedSet, SequencedSet
Range / navigationNofirst, last, floor, ceiling, headSet, subSet…
Thread-safeNoNo (ConcurrentSkipListSet is the concurrent sorted set)

2. Insertion Order vs Sorted Order

OrderingDemo.java 
import java.util.*;

public class OrderingDemo {
    public static void main(String[] args) {
        List<Integer> scores = List.of(72, 95, 61, 88, 95, 40, 72);

        Set<Integer> linked = new LinkedHashSet<>(scores);
        TreeSet<Integer> tree = new TreeSet<>(scores);
        System.out.println("LinkedHashSet : " + linked + "  (insertion order)");
        System.out.println("TreeSet       : " + tree + "  (sorted)");

        // Navigation methods: only TreeSet
        System.out.println("first / last  : " + tree.first() + " / " + tree.last());
        System.out.println("ceiling(80)   : " + tree.ceiling(80) + ", floor(80): " + tree.floor(80));
        System.out.println("headSet(72)   : " + tree.headSet(72) + ", tailSet(72): " + tree.tailSet(72));
        System.out.println("descendingSet : " + tree.descendingSet());

        // Custom ordering with a Comparator
        TreeSet<String> names = new TreeSet<>(Comparator.comparing(String::length).thenComparing(Comparator.naturalOrder()));
        names.addAll(List.of("Ravi", "Asha", "Meera", "Jo", "Kiran"));
        System.out.println("by length     : " + names);
    }
}
Output
LinkedHashSet : [72, 95, 61, 88, 40]  (insertion order)
TreeSet       : [40, 61, 72, 88, 95]  (sorted)
first / last  : 40 / 95
ceiling(80)   : 88, floor(80): 72
headSet(72)   : [40, 61], tailSet(72): [72, 88, 95]
descendingSet : [95, 88, 72, 61, 40]
by length     : [Jo, Asha, Ravi, Kiran, Meera]

Only TreeSet can answer questions such as "the smallest score at least 80" (ceiling) or "all scores below 72" (headSet) efficiently.

3. Nulls, Comparable and compareTo

NullAndCompare.java 
import java.util.*;

public class NullAndCompare {
    record Item(String name) { }   // not Comparable

    public static void main(String[] args) {
        Set<String> linked = new LinkedHashSet<>();
        linked.add(null);
        System.out.println("LinkedHashSet accepts null: " + linked.contains(null));

        try {
            new TreeSet<String>().add(null);
        } catch (NullPointerException e) {
            System.out.println("TreeSet.add(null): NullPointerException");
        }

        try {
            new TreeSet<Item>().add(new Item("pen"));
        } catch (ClassCastException e) {
            System.out.println("TreeSet of non-Comparable: ClassCastException");
        }

        // TreeSet uses compareTo, not equals, to detect duplicates
        TreeSet<String> ci = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
        ci.addAll(List.of("Java", "JAVA", "java"));
        System.out.println("case-insensitive TreeSet: " + ci);
    }
}
Output
LinkedHashSet accepts null: true
TreeSet.add(null): NullPointerException
TreeSet of non-Comparable: ClassCastException
case-insensitive TreeSet: [Java]
  • TreeSet must compare elements, so null and non-Comparable objects fail without a suitable comparator.
  • It treats elements as duplicates when compareTo returns 0, even if equals says otherwise. Keep comparators consistent with equals unless that is what you intend.

4. When to Use Which

  • LinkedHashSet: unique elements in the order they arrived, with the fastest operations (de-duplicating input, recent unique items).
  • TreeSet: unique elements kept sorted, or when you need range queries and nearest-element lookups (leaderboards, schedules, price bands).
  • If you only need sorted output occasionally, a HashSet plus sorting at the end can be cheaper than maintaining a TreeSet.

5. Summary

  • LinkedHashSet: insertion order, O(1), one null allowed, uses equals/hashCode.
  • TreeSet: sorted order, O(log n), no null, uses compareTo/comparator.
  • Only TreeSet provides navigation and range views.
  • Neither is thread-safe.

Related Tutorials