Course contentsShow
← Java
Lesson 1207 of 2,87027. Queue and Deque ImplementationsFree lesson

Array Growth and Capacity Doubling

How ArrayDeque dynamically resizes its backing array when full, doubling capacity each time.

Array Growth and Capacity Doubling

You'll learn how ArrayDeque automatically expands its internal array when it runs out of space.

The Core Idea

When you keep adding elements to an ArrayDeque, eventually its circular array buffer fills up completely. At that point, the deque can't accept more elements without more space. Instead of failing or losing data, ArrayDeque automatically creates a new, larger array and copies all existing elements into it.

The key strategy: capacity doubling. Each time the array grows, it doubles in size. If your array holds 8 elements and fills up, the new array will hold 16. Fill that, and it grows to 32, then 64, and so on.

Why Doubling?

Think of moving to a bigger house. You could move every time you get one new item (exhausting!), or you could move to a house twice as big, giving you room to grow. Doubling minimizes how often resizing happens while keeping memory usage reasonable.

When the backing array is full:

  1. A new array is allocated with double the capacity
  2. All elements are copied from the old array to the new one
  3. The head and tail pointers are adjusted
  4. The old array is discarded

The Trade-off

Resizing is an expensive O(n) operation—every element must be copied. But because capacity doubles, it happens less frequently as the deque grows. If you add n elements, resizing only occurs log₂(n) times, which keeps the amortized cost of adding elements efficient.

Key Takeaway: ArrayDeque dynamically grows by doubling its internal array capacity when full, balancing performance and memory usage through infrequent but predictable resizing operations.