Course contentsShow
← Java
Lesson 1142 of 2,87026. Map ImplementationsFree lesson

LinkedHashMap Overview: Ordering in Maps

Understand how LinkedHashMap extends HashMap to maintain predictable iteration order using a doubly-linked list.

LinkedHashMap Overview: Ordering in Maps

You'll learn how LinkedHashMap extends HashMap to maintain predictable iteration order by adding a doubly-linked list structure.

The Problem with HashMap

You've learned that HashMap provides excellent O(1) performance but offers no ordering guarantees. When you iterate over a HashMap, the order of entries is unpredictable and based on internal hash bucket positions. Sometimes you need both fast lookup and predictable iteration order.

How LinkedHashMap Solves This

LinkedHashMap extends HashMap and adds one crucial feature: a doubly-linked list connecting all entries. Every key-value pair in the map is linked to both its predecessor and successor, forming a chain that preserves insertion order.

Think of it like a library where books are organized by their Dewey Decimal number (the hash) for quick lookup, but they're also connected by invisible threads in the order they were added to the collection. You can find any book quickly using its number, and you can follow the thread to see them in chronological order.

Two Flavors of Ordering

LinkedHashMap supports two ordering modes:

  1. Insertion order (default): Entries appear in the order they were first added
  2. Access order: Entries move to the end when accessed (useful for LRU caches)

The Cost of Ordering

Maintaining the linked list adds memory overhead—each entry needs two extra pointers (previous and next). Performance for basic operations remains O(1) on average, just like HashMap, but iteration is faster because you follow the linked list instead of scanning all hash buckets.

Key Takeaway:
LinkedHashMap combines HashMap's fast O(1) operations with predictable iteration order by maintaining a doubly-linked list of entries, making it ideal when you need both performance and ordering.