Table of Contents

1. Introduction
2. LinkedHashSet vs HashSet vs TreeSet
3. Internal Implementation
4. Insertion Order Preservation
5. Access Order (LRU Cache)
6. Common Operations and Examples
7. Performance Characteristics
8. Use Cases
9. Best Practices
10. Complete Examples

Introduction

LinkedHashSet is a hash table and linked list implementation of the Set interface with predictable iteration order. It maintains a doubly-linked list running through all its entries, which defines the iteration ordering.

Key Characteristics:

• Insertion Order: Maintains the order in which elements were inserted
• No Duplicates: Like all Set implementations, doesn't allow duplicates
• Null Elements: Allows one null element
• Performance: Similar to HashSet but with slightly lower performance due to maintaining linked list

LinkedHashSet vs HashSet vs TreeSet

Comparison Table:

Feature	LinkedHashSet	HashSet	TreeSet
Ordering	Insertion order	No order	Natural sorting / Custom comparator
Implementation	Hash table + Linked list	Hash table	Red-Black tree
Performance	O(1) for basic operations	O(1) for basic operations	O(log n) for basic operations
Null elements	Allows one null	Allows one null	Doesn't allow null (if natural ordering)
Use Case	Maintain insertion order	General purpose set	Sorted set requirements

Code Comparison:

import java.util.*; public class SetComparison { public static void main(String[] args) { // HashSet - No order guarantee Set<String> hashSet = new HashSet<>(); hashSet.add("Apple"); hashSet.add("Banana"); hashSet.add("Cherry"); hashSet.add("Date"); System.out.println("HashSet: " + hashSet); // Order not guaranteed // LinkedHashSet - Insertion order maintained Set<String> linkedHashSet = new LinkedHashSet<>(); linkedHashSet.add("Apple"); linkedHashSet.add("Banana"); linkedHashSet.add("Cherry"); linkedHashSet.add("Date"); System.out.println("LinkedHashSet: " + linkedHashSet); // Insertion order // TreeSet - Natural sorting order Set<String> treeSet = new TreeSet<>(); treeSet.add("Apple"); treeSet.add("Banana"); treeSet.add("Cherry"); treeSet.add("Date"); System.out.println("TreeSet: " + treeSet); // Sorted order } }

Output:

HashSet: [Apple, Cherry, Date, Banana] # Random order LinkedHashSet: [Apple, Banana, Cherry, Date] # Insertion order TreeSet: [Apple, Banana, Cherry, Date] # Sorted order

Internal Implementation

Data Structure:

LinkedHashSet uses:

• HashMap for storage (like HashSet)
• Doubly-linked list for maintaining order

// Simplified internal structure public class LinkedHashSet<E> extends HashSet<E> implements Set<E> { // Internal LinkedHashMap that maintains order private transient LinkedHashMap<E, Object> map; // Dummy value to associate with Object in backing Map private static final Object PRESENT = new Object(); public LinkedHashSet() { map = new LinkedHashMap<>(); } public boolean add(E e) { return map.put(e, PRESENT) == null; } // Other methods delegate to the LinkedHashMap }

Insertion Order Preservation

Basic Insertion Order Example:

import java.util.*; public class InsertionOrderExample { public static void main(String[] args) { LinkedHashSet<String> fruits = new LinkedHashSet<>(); // Add elements in specific order fruits.add("Apple"); fruits.add("Banana"); fruits.add("Cherry"); fruits.add("Date"); fruits.add("Elderberry"); System.out.println("Initial order: " + fruits); // Adding duplicate - order remains same fruits.add("Apple"); System.out.println("After adding duplicate: " + fruits); // Adding new element - goes to end fruits.add("Fig"); System.out.println("After adding new element: " + fruits); // Remove and add - goes to end fruits.remove("Cherry"); fruits.add("Cherry"); System.out.println("After remove and add: " + fruits); } }

Output:

Initial order: [Apple, Banana, Cherry, Date, Elderberry] After adding duplicate: [Apple, Banana, Cherry, Date, Elderberry] After adding new element: [Apple, Banana, Cherry, Date, Elderberry, Fig] After remove and add: [Apple, Banana, Date, Elderberry, Fig, Cherry]

Maintaining Order with Custom Objects:

import java.util.*; class Student { private int id; private String name; public Student(int id, String name) { this.id = id; this.name = name; } // Important: Override equals and hashCode for proper Set behavior @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Student student = (Student) o; return id == student.id; } @Override public int hashCode() { return Objects.hash(id); } @Override public String toString() { return "Student{id=" + id + ", name='" + name + "'}"; } } public class CustomObjectOrder { public static void main(String[] args) { LinkedHashSet<Student> students = new LinkedHashSet<>(); students.add(new Student(101, "Alice")); students.add(new Student(102, "Bob")); students.add(new Student(103, "Charlie")); students.add(new Student(104, "Diana")); System.out.println("Students in insertion order:"); for (Student student : students) { System.out.println(student); } // Adding duplicate student (same ID) students.add(new Student(102, "Robert")); // Won't be added System.out.println("\nAfter trying to add duplicate:"); for (Student student : students) { System.out.println(student); } } }

Output:

Students in insertion order: Student{id=101, name='Alice'} Student{id=102, name='Bob'} Student{id=103, name='Charlie'} Student{id=104, name='Diana'} After trying to add duplicate: Student{id=101, name='Alice'} Student{id=102, name='Bob'} Student{id=103, name='Charlie'} Student{id=104, name='Diana'}

Access Order (LRU Cache)

While LinkedHashSet itself doesn't support access order, its backing implementation LinkedHashMap does. We can create an LRU Cache using access order.

LRU Cache Implementation:

import java.util.*; public class LRUCache<K, V> extends LinkedHashMap<K, V> { private final int capacity; public LRUCache(int capacity) { // accessOrder = true means access order, false means insertion order super(capacity, 0.75f, true); this.capacity = capacity; } @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return size() > capacity; } public static void main(String[] args) { LRUCache<Integer, String> cache = new LRUCache<>(3); cache.put(1, "Apple"); cache.put(2, "Banana"); cache.put(3, "Cherry"); System.out.println("Initial cache: " + cache.keySet()); // Access element 2 - moves to end (most recently used) cache.get(2); System.out.println("After accessing key 2: " + cache.keySet()); // Access element 1 - moves to end cache.get(1); System.out.println("After accessing key 1: " + cache.keySet()); // Add new element - removes least recently used (key 3) cache.put(4, "Date"); System.out.println("After adding key 4: " + cache.keySet()); } }

Output:

Initial cache: [1, 2, 3] After accessing key 2: [1, 3, 2] After accessing key 1: [3, 2, 1] After adding key 4: [2, 1, 4]

Common Operations and Examples

1. Basic Operations:

import java.util.*; public class BasicOperations { public static void main(String[] args) { LinkedHashSet<Integer> numbers = new LinkedHashSet<>(); // Add elements numbers.add(10); numbers.add(20); numbers.add(30); numbers.add(40); numbers.add(50); System.out.println("After adding: " + numbers); // Check contains System.out.println("Contains 30: " + numbers.contains(30)); System.out.println("Contains 35: " + numbers.contains(35)); // Remove element numbers.remove(20); System.out.println("After removing 20: " + numbers); // Size and empty check System.out.println("Size: " + numbers.size()); System.out.println("Is empty: " + numbers.isEmpty()); // Iteration maintains order System.out.print("Iteration: "); for (Integer num : numbers) { System.out.print(num + " "); } System.out.println(); // Convert to array (maintains order) Integer[] array = numbers.toArray(new Integer[0]); System.out.println("Array: " + Arrays.toString(array)); } }

Output:

After adding: [10, 20, 30, 40, 50] Contains 30: true Contains 35: false After removing 20: [10, 30, 40, 50] Size: 4 Is empty: false Iteration: 10 30 40 50 Array: [10, 30, 40, 50]

2. Set Operations with Order Preservation:

import java.util.*; public class SetOperations { public static void main(String[] args) { LinkedHashSet<String> set1 = new LinkedHashSet<>( Arrays.asList("A", "B", "C", "D", "E")); LinkedHashSet<String> set2 = new LinkedHashSet<>( Arrays.asList("C", "D", "E", "F", "G")); System.out.println("Set 1: " + set1); System.out.println("Set 2: " + set2); // Union - maintains order from first set, then second LinkedHashSet<String> union = new LinkedHashSet<>(set1); union.addAll(set2); System.out.println("Union: " + union); // Intersection - maintains order from first set LinkedHashSet<String> intersection = new LinkedHashSet<>(set1); intersection.retainAll(set2); System.out.println("Intersection: " + intersection); // Difference - maintains order from first set LinkedHashSet<String> difference = new LinkedHashSet<>(set1); difference.removeAll(set2); System.out.println("Difference (set1 - set2): " + difference); } }

Output:

Set 1: [A, B, C, D, E] Set 2: [C, D, E, F, G] Union: [A, B, C, D, E, F, G] Intersection: [C, D, E] Difference (set1 - set2): [A, B]

3. Removing Duplicates While Preserving Order:

import java.util.*; public class RemoveDuplicates { public static <T> List<T> removeDuplicatesPreserveOrder(List<T> list) { LinkedHashSet<T> set = new LinkedHashSet<>(list); return new ArrayList<>(set); } public static void main(String[] args) { List<String> namesWithDuplicates = Arrays.asList( "Alice", "Bob", "Charlie", "Alice", "David", "Bob", "Eve" ); System.out.println("Original list: " + namesWithDuplicates); List<String> uniqueNames = removeDuplicatesPreserveOrder(namesWithDuplicates); System.out.println("After removing duplicates: " + uniqueNames); // Example with integers List<Integer> numbersWithDuplicates = Arrays.asList(3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5); System.out.println("Original numbers: " + numbersWithDuplicates); List<Integer> uniqueNumbers = removeDuplicatesPreserveOrder(numbersWithDuplicates); System.out.println("After removing duplicates: " + uniqueNumbers); } }

Output:

Original list: [Alice, Bob, Charlie, Alice, David, Bob, Eve] After removing duplicates: [Alice, Bob, Charlie, David, Eve] Original numbers: [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5] After removing duplicates: [3, 1, 4, 5, 9, 2, 6]

Performance Characteristics

Time Complexity:

Operation	Time Complexity
add()	O(1)
remove()	O(1)
contains()	O(1)
next() (iteration)	O(1)
Size	O(1)

Memory Overhead:

• Slightly more memory than HashSet due to maintaining linked list
• Each element has additional previous/next pointers

Performance Comparison Example:

import java.util.*; public class PerformanceComparison { public static void main(String[] args) { final int SIZE = 100000; // HashSet Set<Integer> hashSet = new HashSet<>(); long startTime = System.nanoTime(); for (int i = 0; i < SIZE; i++) { hashSet.add(i); } long hashSetTime = System.nanoTime() - startTime; // LinkedHashSet Set<Integer> linkedHashSet = new LinkedHashSet<>(); startTime = System.nanoTime(); for (int i = 0; i < SIZE; i++) { linkedHashSet.add(i); } long linkedHashSetTime = System.nanoTime() - startTime; // TreeSet Set<Integer> treeSet = new TreeSet<>(); startTime = System.nanoTime(); for (int i = 0; i < SIZE; i++) { treeSet.add(i); } long treeSetTime = System.nanoTime() - startTime; System.out.println("Performance Comparison (nanoseconds):"); System.out.println("HashSet: " + hashSetTime); System.out.println("LinkedHashSet: " + linkedHashSetTime); System.out.println("TreeSet: " + treeSetTime); System.out.println("LinkedHashSet is " + (linkedHashSetTime - hashSetTime) + " ns slower than HashSet"); } }

Use Cases

1. Maintaining Insertion Order:

import java.util.*; public class TaskManager { private LinkedHashSet<String> completedTasks; public TaskManager() { completedTasks = new LinkedHashSet<>(); } public void completeTask(String task) { completedTasks.add(task); System.out.println("Task completed: " + task); } public void displayCompletedTasks() { System.out.println("Tasks completed in order:"); int count = 1; for (String task : completedTasks) { System.out.println(count++ + ". " + task); } } public static void main(String[] args) { TaskManager manager = new TaskManager(); manager.completeTask("Design database schema"); manager.completeTask("Implement user authentication"); manager.completeTask("Write unit tests"); manager.completeTask("Deploy to production"); // Try to complete duplicate task manager.completeTask("Implement user authentication"); manager.displayCompletedTasks(); } }

Output:

Task completed: Design database schema Task completed: Implement user authentication Task completed: Write unit tests Task completed: Deploy to production Task completed: Implement user authentication Tasks completed in order: 1. Design database schema 2. Implement user authentication 3. Write unit tests 4. Deploy to production

2. URL History in Web Browser:

import java.util.*; public class BrowserHistory { private LinkedHashSet<String> history; private final int maxHistorySize; public BrowserHistory(int maxHistorySize) { this.maxHistorySize = maxHistorySize; this.history = new LinkedHashSet<>(maxHistorySize, 0.75f); } public void visitUrl(String url) { if (history.size() >= maxHistorySize) { // Remove oldest entry String oldest = history.iterator().next(); history.remove(oldest); } history.add(url); } public void displayHistory() { System.out.println("Browser History (newest last):"); int count = 1; for (String url : history) { System.out.println(count++ + ". " + url); } } public static void main(String[] args) { BrowserHistory browser = new BrowserHistory(5); browser.visitUrl("https://www.google.com"); browser.visitUrl("https://www.github.com"); browser.visitUrl("https://www.stackoverflow.com"); browser.visitUrl("https://www.reddit.com"); browser.visitUrl("https://www.twitter.com"); browser.displayHistory(); // Visit existing URL - moves to end browser.visitUrl("https://www.github.com"); browser.displayHistory(); // Add new URL when full browser.visitUrl("https://www.linkedin.com"); browser.displayHistory(); } }

Output:

Browser History (newest last): 1. https://www.google.com 2. https://www.github.com 3. https://www.stackoverflow.com 4. https://www.reddit.com 5. https://www.twitter.com Browser History (newest last): 1. https://www.google.com 2. https://www.stackoverflow.com 3. https://www.reddit.com 4. https://www.twitter.com 5. https://www.github.com Browser History (newest last): 1. https://www.stackoverflow.com 2. https://www.reddit.com 3. https://www.twitter.com 4. https://www.github.com 5. https://www.linkedin.com

3. Recent Items List:

import java.util.*; public class RecentItems<T> { private LinkedHashSet<T> items; private final int capacity; public RecentItems(int capacity) { this.capacity = capacity; this.items = new LinkedHashSet<>(capacity, 0.75f); } public void addItem(T item) { if (items.contains(item)) { items.remove(item); } else if (items.size() >= capacity) { // Remove least recent (first element) T first = items.iterator().next(); items.remove(first); } items.add(item); } public List<T> getRecentItems() { return new ArrayList<>(items); } public List<T> getRecentItems(int count) { List<T> result = new ArrayList<>(); Iterator<T> iterator = items.iterator(); for (int i = 0; i < count && iterator.hasNext(); i++) { result.add(iterator.next()); } return result; } public static void main(String[] args) { RecentItems<String> recentFiles = new RecentItems<>(5); recentFiles.addItem("document1.txt"); recentFiles.addItem("image.png"); recentFiles.addItem("spreadsheet.xlsx"); recentFiles.addItem("presentation.ppt"); recentFiles.addItem("notes.txt"); System.out.println("Recent files: " + recentFiles.getRecentItems()); // Add existing file - moves to end recentFiles.addItem("document1.txt"); System.out.println("After reopening document1: " + recentFiles.getRecentItems()); // Add new file when full recentFiles.addItem("config.properties"); System.out.println("After adding config: " + recentFiles.getRecentItems()); // Get only 3 most recent System.out.println("3 most recent: " + recentFiles.getRecentItems(3)); } }

Output:

Recent files: [document1.txt, image.png, spreadsheet.xlsx, presentation.ppt, notes.txt] After reopening document1: [image.png, spreadsheet.xlsx, presentation.ppt, notes.txt, document1.txt] After adding config: [spreadsheet.xlsx, presentation.ppt, notes.txt, document1.txt, config.properties] 3 most recent: [spreadsheet.xlsx, presentation.ppt, notes.txt]

Best Practices

1. Choose the Right Set Implementation:

// Use LinkedHashSet when: // - You need to maintain insertion order // - You need predictable iteration order // - You need both Set behavior and order // Use HashSet when: // - Order doesn't matter // - Maximum performance needed // Use TreeSet when: // - You need sorted order // - You need range operations

2. Proper equals() and hashCode():

class Product { private String id; private String name; public Product(String id, String name) { this.id = id; this.name = name; } @Override public boolean equals(Object o) { if (this == o) return true; if (!(o instanceof Product)) return false; Product product = (Product) o; return Objects.equals(id, product.id); } @Override public int hashCode() { return Objects.hash(id); } // Always implement toString() for debugging @Override public String toString() { return "Product{id='" + id + "', name='" + name + "'}"; } }

3. Initial Capacity and Load Factor:

public class LinkedHashSetConfiguration { public static void main(String[] args) { // Default constructor - initial capacity 16, load factor 0.75 LinkedHashSet<String> defaultSet = new LinkedHashSet<>(); // Specify initial capacity LinkedHashSet<String> capacitySet = new LinkedHashSet<>(100); // Specify initial capacity and load factor LinkedHashSet<String> configuredSet = new LinkedHashSet<>(100, 0.6f); // Create from existing collection (maintains order) List<String> list = Arrays.asList("A", "B", "C", "A", "D"); LinkedHashSet<String> fromCollection = new LinkedHashSet<>(list); System.out.println("From collection: " + fromCollection); } }

Complete Examples

Complete Working Example:

import java.util.*; public class LinkedHashSetCompleteExample { public static void main(String[] args) { System.out.println("=== LinkedHashSet Complete Example ===\n"); // Example 1: Basic Order Preservation basicOrderExample(); // Example 2: Custom Objects with Order customObjectsExample(); // Example 3: Practical Use Case - Shopping Cart shoppingCartExample(); // Example 4: Advanced - LRU Cache Simulation lruCacheSimulation(); } public static void basicOrderExample() { System.out.println("1. Basic Order Preservation:"); LinkedHashSet<String> colors = new LinkedHashSet<>(); // Add colors in specific order String[] colorArray = {"Red", "Blue", "Green", "Yellow", "Purple", "Blue", "Red"}; for (String color : colorArray) { colors.add(color); System.out.println("Added: " + color + " -> Set: " + colors); } System.out.println("Final order: " + colors); System.out.println(); } public static void customObjectsExample() { System.out.println("2. Custom Objects with Order:"); LinkedHashSet<Employee> employees = new LinkedHashSet<>(); employees.add(new Employee(101, "John Doe", "Engineering")); employees.add(new Employee(102, "Jane Smith", "Marketing")); employees.add(new Employee(103, "Bob Johnson", "Sales")); employees.add(new Employee(101, "John Doe", "HR")); // Duplicate ID System.out.println("Employees in insertion order:"); for (Employee emp : employees) { System.out.println(emp); } System.out.println(); } public static void shoppingCartExample() { System.out.println("3. Shopping Cart Example:"); ShoppingCart cart = new ShoppingCart(); cart.addItem("Laptop", 999.99); cart.addItem("Mouse", 25.99); cart.addItem("Keyboard", 75.50); cart.addItem("Mouse", 25.99); // Duplicate cart.addItem("Monitor", 299.99); cart.displayCart(); cart.removeItem("Mouse"); cart.displayCart(); System.out.println("Total: $" + cart.getTotal()); System.out.println(); } public static void lruCacheSimulation() { System.out.println("4. LRU Cache Simulation:"); LRUSimulation cache = new LRUSimulation(3); cache.access("A"); cache.access("B"); cache.access("C"); cache.displayCache(); cache.access("A"); // Move A to most recent cache.displayCache(); cache.access("D"); // Should remove B (least recently used) cache.displayCache(); cache.access("C"); // Move C to most recent cache.displayCache(); } } // Supporting classes class Employee { private int id; private String name; private String department; public Employee(int id, String name, String department) { this.id = id; this.name = name; this.department = department; } @Override public boolean equals(Object o) { if (this == o) return true; if (!(o instanceof Employee)) return false; Employee employee = (Employee) o; return id == employee.id; } @Override public int hashCode() { return Objects.hash(id); } @Override public String toString() { return String.format("Employee[ID=%d, Name=%-12s, Dept=%-12s]", id, name, department); } } class ShoppingCart { private LinkedHashSet<CartItem> items; public ShoppingCart() { items = new LinkedHashSet<>(); } public void addItem(String name, double price) { CartItem item = new CartItem(name, price); if (!items.add(item)) { System.out.println("Item '" + name + "' already in cart"); } } public void removeItem(String name) { items.remove(new CartItem(name, 0)); } public void displayCart() { System.out.println("Shopping Cart:"); if (items.isEmpty()) { System.out.println(" (empty)"); } else { int count = 1; for (CartItem item : items) { System.out.printf(" %d. %-15s $%.2f\n", count++, item.getName(), item.getPrice()); } } } public double getTotal() { return items.stream().mapToDouble(CartItem::getPrice).sum(); } } class CartItem { private String name; private double price; public CartItem(String name, double price) { this.name = name; this.price = price; } @Override public boolean equals(Object o) { if (this == o) return true; if (!(o instanceof CartItem)) return false; CartItem cartItem = (CartItem) o; return Objects.equals(name, cartItem.name); } @Override public int hashCode() { return Objects.hash(name); } public String getName() { return name; } public double getPrice() { return price; } } class LRUSimulation { private LinkedHashSet<String> cache; private final int capacity; public LRUSimulation(int capacity) { this.capacity = capacity; this.cache = new LinkedHashSet<>(capacity, 0.75f); } public void access(String item) { if (cache.contains(item)) { cache.remove(item); } else if (cache.size() >= capacity) { // Remove least recently used (first element) String lru = cache.iterator().next(); cache.remove(lru); System.out.println("Evicted: " + lru); } cache.add(item); System.out.println("Accessed: " + item); } public void displayCache() { System.out.println("Cache (LRU -> MRU): " + cache); } }

Expected Output:

=== LinkedHashSet Complete Example === 1. Basic Order Preservation: Added: Red -> Set: [Red] Added: Blue -> Set: [Red, Blue] Added: Green -> Set: [Red, Blue, Green] Added: Yellow -> Set: [Red, Blue, Green, Yellow] Added: Purple -> Set: [Red, Blue, Green, Yellow, Purple] Added: Blue -> Set: [Red, Blue, Green, Yellow, Purple] Added: Red -> Set: [Red, Blue, Green, Yellow, Purple] Final order: [Red, Blue, Green, Yellow, Purple] 2. Custom Objects with Order: Employees in insertion order: Employee[ID=101, Name=John Doe , Dept=Engineering ] Employee[ID=102, Name=Jane Smith , Dept=Marketing ] Employee[ID=103, Name=Bob Johnson , Dept=Sales ] 3. Shopping Cart Example: Item 'Mouse' already in cart Shopping Cart: 1. Laptop $999.99 2. Mouse $25.99 3. Keyboard $75.50 4. Monitor $299.99 Shopping Cart: 1. Laptop $999.99 2. Keyboard $75.50 3. Monitor $299.99 Total: $1375.48 4. LRU Cache Simulation: Accessed: A Accessed: B Accessed: C Cache (LRU -> MRU): [A, B, C] Accessed: A Cache (LRU -> MRU): [B, C, A] Evicted: B Accessed: D Cache (LRU -> MRU): [C, A, D] Accessed: C Cache (LRU -> MRU): [A, D, C]

Key Takeaways

1. LinkedHashSet maintains insertion order - elements are iterated in the order they were added
2. No duplicates - like all Set implementations, it doesn't allow duplicate elements
3. Good performance - O(1) for basic operations, slightly slower than HashSet due to linked list maintenance
4. Perfect for order-sensitive scenarios - task management, history tracking, recent items
5. Combines benefits of HashSet (performance) and LinkedList (order)
6. Use when you need both Set semantics and predictable iteration order

LinkedHashSet is an excellent choice when you need the uniqueness guarantee of a Set combined with predictable iteration order, making it ideal for many real-world applications where order matters.