How to Shuffle Collections in Java

The java.util.Collections class provides a static shuffle method that randomizes the order of elements in a List. It is the standard way to shuffle a list without writing your own randomization logic. The method modifies the list in place. It works with any mutable List, and it is most efficient for random-access lists such as ArrayList; for larger sequential-access lists such as LinkedList, shuffle internally copies the elements to an array before randomizing them.

The Collections.shuffle() Method and Its Contract

The simplest usage is to pass the list you want to shuffle:

List<String> cards = new ArrayList<>(List.of("Ace", "King", "Queen", "Jack"));
Collections.shuffle(cards);
System.out.println(cards);

shuffle uses a default source of randomness and runs in linear time. It needs to call set on the list, so it works with mutable list implementations such as ArrayList and LinkedList. It throws an UnsupportedOperationException for lists whose set method is not supported, such as a non-empty immutable list created with List.of() or List.copyOf().

How Shuffle Works Under the Hood

For a random-access list, the implementation uses the Fisher-Yates algorithm (also called the Knuth shuffle). It iterates from the last element down to the second, and for each position i it picks a random index between 0 and i inclusive, then swaps the elements at those positions. This guarantees every permutation is equally likely when the random source is unbiased.

// Simplified version of the algorithm for a random-access list
for (int i = list.size() - 1; i > 0; i--) {
    int j = random.nextInt(i + 1);
    Collections.swap(list, i, j);
}

For a RandomAccess list such as ArrayList, the time complexity is O(n) and the space complexity is O(1) because the shuffle is done in place. For a non-random-access list such as LinkedList, Collections.shuffle first copies the list into an array, shuffles the array, and copies the result back, so it also uses O(n) temporary space.

Using a Custom Random Source

Sometimes you need a reproducible shuffle, for example in tests or when you want to control the randomness seed. The overloaded shuffle(List<?> list, Random rnd) method accepts a Random instance. Using a Random with a fixed seed produces the same sequence of shuffles each run, which is useful for deterministic behavior in unit tests.

Random random = new Random(42L);
Collections.shuffle(cards, random);

You can also use ThreadLocalRandom.current() for better performance in concurrent scenarios, though the default overload already uses a thread-safe random source internally. Random is thread-safe, but sharing one instance across threads can cause contention; ThreadLocalRandom avoids that.

Shuffling Arrays and Other Collection Types

The Collections.shuffle method only works on List instances. To shuffle an array, you must first convert it to a List using Arrays.asList() and then shuffle that view. The resulting list is backed by the original array, so the shuffle modifies the array directly.

Integer[] numbers = {1, 2, 3, 4, 5};
Collections.shuffle(Arrays.asList(numbers));
// numbers is now shuffled

This works for boxed arrays. For a primitive array such as int[], Arrays.asList does not produce a List<Integer>; convert the values to Integer[] first if you need to shuffle them.

For other collection types like Set, there is no direct shuffle method because sets are not index-based. If you need to randomize a set, convert it to a list first, shuffle, and then optionally rebuild a LinkedHashSet to preserve the new order.

Thread Safety and Concurrent Modification

The shuffle method is not atomic. If another thread modifies the list while shuffle is running, the behavior is undefined and may throw a ConcurrentModificationException or produce an inconsistent state. To shuffle safely in a multithreaded context, either synchronize externally on the list or use a thread-safe list implementation like CopyOnWriteArrayList, but note that the latter has a high write cost.

If you need a thread-safe shuffle that does not block other readers, consider copying the list to a new array, shuffling the copy, and then publishing the result. This avoids holding a lock during the shuffle.

Performance and Memory Considerations

For ArrayList, the default shuffle is O(n) in time and O(1) in extra space. For large lists, the dominant cost is the random number generation and the swaps. Using a Random instance with a high-quality algorithm like SecureRandom will be slower but cryptographically strong, which is rarely needed for ordering. For most use cases, ThreadLocalRandom.current() or the default source is sufficient.

Memory usage is minimal for random-access lists because the shuffle operates in place. However, if you need to preserve the original order, you must create a copy of the list before shuffling. A shallow copy via new ArrayList<>(original) is enough for immutable elements; for mutable elements, the elements themselves are not copied.

Common Pitfalls and Edge Cases

One common mistake is trying to shuffle an immutable list. For example, List.of("Ace", "King") returns an immutable list, and calling Collections.shuffle on it throws UnsupportedOperationException as soon as the method tries to set an element. Always use a mutable ArrayList or LinkedList.

Another edge case is shuffling a list with only one element or zero elements; the method does nothing, which is correct. Also, the shuffle is uniform only if the random source is unbiased. Java's Random uses a linear congruential generator, which is not a cryptographic generator but is acceptable for most non-cryptographic uses.

If you need to shuffle a large list repeatedly, consider reusing a Random instance instead of creating a new one each time, to avoid allocation overhead and to keep the sequence predictable.

Choosing Between shuffle and Other Randomization Techniques

Collections.shuffle is the right tool when you need to reorder all elements randomly. If you only need a few random elements without replacement, a partial Fisher-Yates or a reservoir sampling approach may be more efficient. For example, selecting a random subset of size k from a list of n elements can be done by shuffling only the last k positions, which is cheaper than shuffling the entire list.

// Partial shuffle for the last k positions
for (int i = n - 1; i > n - k - 1; i--) {
    int j = random.nextInt(i + 1);
    Collections.swap(list, i, j);
}

This approach is useful when the list is very large and only a small sample is needed. The tradeoff is that the rest of the list remains in its original order, which may or may not be acceptable depending on the use case.