Java tutorials > Core Java Fundamentals > Data Structures and Collections > What is the difference between `List`, `Set`, and `Map`?

What is the difference between `List`, `Set`, and `Map`?

This tutorial explains the fundamental differences between three essential Java data structures: List, Set, and Map. Understanding these differences is crucial for choosing the right data structure for a specific task, optimizing performance, and writing efficient Java code. We will cover their core characteristics, use cases, and provide code examples to illustrate their behavior.

Core Differences at a Glance

  • List: An ordered collection of elements that allows duplicate values. Elements can be accessed by their index.
  • Set: An unordered collection of unique elements. It does not allow duplicate values.
  • Map: A collection that stores elements as key-value pairs. Each key must be unique, but values can be duplicated. It does not maintain any specific order.

List in Detail

Lists are ordered collections. The ArrayList is a common implementation. Elements are stored in the order they are added. Duplicates are permitted. Elements can be accessed by their index using the get() method. Other common List implementations include LinkedList and Vector.

import java.util.ArrayList;
import java.util.List;

public class ListExample {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("Apple");
        list.add("Banana");
        list.add("Apple"); // Duplicate allowed
        list.add("Orange");

        System.out.println(list); // Output: [Apple, Banana, Apple, Orange]
        System.out.println(list.get(1)); // Output: Banana
    }
}

Set in Detail

Sets are unordered collections that do not allow duplicate elements. HashSet is a common implementation. When you try to add a duplicate element, it's simply ignored. The order of elements in a Set is not guaranteed and may vary. Other common Set implementations include TreeSet (which maintains elements in sorted order) and LinkedHashSet (which maintains insertion order).

import java.util.HashSet;
import java.util.Set;

public class SetExample {
    public static void main(String[] args) {
        Set<String> set = new HashSet<>();
        set.add("Apple");
        set.add("Banana");
        set.add("Apple"); // Duplicate ignored
        set.add("Orange");

        System.out.println(set); // Output: [Orange, Banana, Apple] (Order not guaranteed)
    }
}

Map in Detail

Maps store data in key-value pairs. Each key must be unique within the map. Values, however, can be duplicated. HashMap is a commonly used implementation. If you try to insert a duplicate key with a different value, the existing value is overwritten. The get() method retrieves the value associated with a specific key. Other common Map implementations include TreeMap (which maintains keys in sorted order) and LinkedHashMap (which maintains insertion order).

import java.util.HashMap;
import java.util.Map;

public class MapExample {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        map.put("Apple", 1);
        map.put("Banana", 2);
        map.put("Orange", 3);
        map.put("Apple", 4); // Overwrites the previous value for "Apple"

        System.out.println(map); // Output: {Orange=3, Banana=2, Apple=4}
        System.out.println(map.get("Apple")); // Output: 4
    }
}

Real-Life Use Case Section

  • List: Managing a playlist of songs (order matters, duplicates allowed).
  • Set: Storing a collection of unique user IDs (duplicates are not meaningful).
  • Map: Representing a dictionary where words (keys) are associated with their definitions (values). Or storing configuration settings where the setting name is the key and the setting value is the value.

Best Practices

  • Choose the right data structure: Select the data structure that best fits the requirements of your task in terms of order, uniqueness, and access patterns.
  • Consider performance: Be aware of the time complexity of different operations (e.g., adding, removing, searching) for each data structure.
  • Use generics: Specify the type of elements stored in the collection to avoid ClassCastExceptions and improve code readability.

Interview Tip

Be prepared to discuss the time and space complexity of common operations on each data structure (e.g., adding, removing, searching, iterating). For example, searching for an element in an unsorted List has O(n) complexity, while searching in a HashSet has (on average) O(1) complexity. Understanding the different implementations of each interface (e.g., ArrayList vs. LinkedList for List) and when to use each is also important.

When to use them

  • List: When you need to maintain the order of elements and allow duplicates.
  • Set: When you need to store unique elements and order is not important.
  • Map: When you need to store key-value pairs and quickly retrieve values based on their keys.

Memory Footprint

The memory footprint of each data structure depends on the number of elements stored and the underlying implementation. Generally, Lists can have a smaller memory footprint than Sets or Maps for the same number of unique elements, especially if duplicates are frequent. Hash-based implementations (HashSet, HashMap) consume extra memory for hash table management. LinkedLists consume extra memory for storing pointers to the next and previous node. ArrayList typically allocates extra memory to avoid frequent array resizing which impacts the memory footprint.

Alternatives

While List, Set, and Map are fundamental, other specialized collections exist, such as Queue, Deque, and custom data structures tailored to specific needs. Arrays can also be used when the size is known in advance and mutability is not required. Libraries like Guava provide more advanced collection implementations.

Pros and Cons

List:
  • Pros: Ordered, allows duplicates, easy access by index.
  • Cons: Searching can be slow (O(n) in unsorted lists), inserting/deleting in the middle can be inefficient.
Set:
  • Pros: Stores unique elements, fast lookups (O(1) on average for HashSet).
  • Cons: Unordered (unless using TreeSet or LinkedHashSet), doesn't allow duplicates.
Map:
  • Pros: Fast lookups by key (O(1) on average for HashMap), stores key-value pairs.
  • Cons: Keys must be unique, no inherent ordering (unless using TreeMap or LinkedHashMap).

Concepts behind the snippet

  • Interface: List, Set, and Map are interfaces in Java's Collections Framework.
  • Implementation: ArrayList, LinkedList, HashSet, TreeSet, HashMap, and TreeMap are some common classes that implement these interfaces.
  • Generics: Using generics (e.g., List) allows you to specify the type of objects that the collection will hold, providing compile-time type safety.

← What is the difference between `==` and `.equals()`? What is the difference between abstract class and interface? →

FAQ

  • When should I use a LinkedList instead of an ArrayList?

    Use a LinkedList when you need frequent insertions or deletions in the middle of the list, as these operations are more efficient in a LinkedList (O(1)) than in an ArrayList (O(n)). ArrayLists are better for random access (getting an element by index).
  • How do I iterate over a Set?

    You can iterate over a Set using an Iterator or a for-each loop: Set set = new HashSet<>(); // Add elements to the set for (String element : set) { System.out.println(element); }
  • How do I ensure that my custom objects can be used as keys in a HashMap?

    Your custom class must override the equals() and hashCode() methods correctly. The hashCode() method must return the same value for two objects that are equal according to the equals() method. If you don't do this properly, you may not be able to retrieve objects from the map correctly.