How the ArrayDeque works in Java?

ArrayDeque is an implementation of the Deque interface of the java collections framework, based on a resizable ring buffer. It offers fast operations when adding and removing elements at the start and the end of the collection. It is the de facto standard for a stack and queue implementations in modern Java. Even, the Kotlin language, who builds upon the JVM and Java standard library, doesn’t offer an equivalent to java.util.LinkedList and java.util.Stack in its standard library (it offers its own equivalents of the Java collections for the most part). Instead, it recommends the usage of ArrayDeque . It was added to the Java specification in Java 1.6.

Key characteristics:

• it’s not thread-safe
• it doesn’t allow null elements
• optimised for good cache locality
• low memory overhead (no wrapper Node objects)

ArrayDeque is a ring buffer based on an array and two pointers — head pointing to the first element and tail pointing to the positon after the last one. The first and last elements of aren’t the actual start and end of the queue. The position of head marks the logical start of the queue. The position of tail minus one marks the last element in the queue.

Modulo calculations are used to determine the positions of the head and tail indexes and they tend to “wrap”. Keeping track of those two indexes determine when a resize will be triggered, adding double the size of the array.

Tail points to the position after the last

If we have a look at the java.util.ArrayDeque source code there are a few methods which carry the main operations in the data structure and the rest of the methods exposed to the users are “wrappers” around them. The most vital ones for understanding how the ring buffer works and to increment and decrement the head and tail positions are the following (pseudo code):

inc(i, capacity) = (i + 1) % capacity
dec(i, capacity) = (i - 1 + capacity) % capacity

//capacity is elementData.length

I’m using pseudo code to explain this, as the JVM architects used some optimisations to avoid using modulo, but those functions should suffice for now.

Now, let’s replay a few real use cases, illustrated with diagrams, to display how the ring buffer / circular array works.

First usecase

1. Beginning:

head = 0
tail = 1
indexes = [0, 1, 2, 3, 4, 5, 6, 7]
array =   [_, _, _, _, _, _, _, _]

2. addLast(A)

elements[tail] = e;
tail = inc(tail, elements.length); //tail is 0 currently

head = 0
tail = 1
indexes = [0, 1, 2, 3, 4, 5, 6, 7]
array =   [A, _, _, _, _, _, _, _]

3. addLast(B)

elements[tail] = e;
tail = inc(tail, elements.length); //tail is 1 currently

head = 0
tail = 2
indexes = [0, 1, 2, 3, 4, 5, 6, 7]
array =   [A, B, _, _, _, _, _, _]

3. addFirst(X)

addFirst calls the dec method:

head = dec(head)
(capacity is 8 currently)
dec(0) = (0 - 1 + 8) % 8
head is now 7
tail = 2
indexes = [0, 1, 2, 3, 4, 5, 6, 7]
array =   [A, B, _, _, _, _, _, X]

4. removeFirst()

inc(i) is called to find the new place for head where i is the current head index (7).

head = inc(7)
inc(i) = (7 + 1) % 8
head = 0
tail = 2
indexes = [0, 1, 2, 3, 4, 5, 6, 7]
array =   [A, B, _, _, _, _, _, _]

Second usecase

Get Tsvetomir Denchev’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

This one will be a bit more complex, displaying the case where indexes wrap (tail can come before head due to modulo calculations) and a resize is triggered subsequently.

1. addLast(A), addLast(B), addLast(C), addLast(D), addLast(E), addLast(F)

head = 0
tail = 6
indexes = [0, 1, 2, 3, 4, 5, 6, 7]
array =   [A, B, C, D, E, F, _, _]

2. removeFirst(), removeFirst()

head = 2
tail = 6
indexes = [0, 1, 2, 3, 4, 5, 6, 7]
array =   [_, _, C, D, E, F, _, _]

3. addLast(G)

head = 2
tail = 7
indexes = [0, 1, 2, 3, 4, 5, 6, 7]
array =   [_, _, C, D, E, F, G, _]

4. addLast(H) — here’s the step where the tail index “wraps” — tail is now before head

tail = inc(7) = 0
head = 2
tail = 0
indexes = [0, 1, 2, 3, 4, 5, 6, 7]
array =   [_, _, C, D, E, F, G, H]

5. addLast(I)

tail = inc(i) = (i + 1) % capacity
(0 + 1) % 8 = 1
head = 2
tail = 1
indexes = [0, 1, 2, 3, 4, 5, 6, 7]
array =   [I, _, C, D, E, F, G, H]

6. addLast(J) — this one will trigger a resize and double the size of the internal array. when tail and head point to the same index a resize is triggered by ArrayDeque

tail = inc(i) = (i + 1) % capacity
(1 + 1) % 8 = 2
head = 2
tail = 2
indexes = [0, 1, 2, 3, 4, 5, 6, 7]
array =   [I, J, C, D, E, F, G, H]

new capacity = 16

head moves at the beginning
tail moves at the next free element

indexes = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
array =   [I, J, C, D, E, F, G, H, _, _, _,  _,  _,  _,  _,  _ ]
head = 0
tail = 8

head is again pointing to the first element and tail — after the last occupied

Concerning the real-world use cases for ArrayDeque — I already covered the usecases for java.util.LinkedList and java.util.Stack in my previous articles on the subject. Please, refer to them, as ArrayDeque can be used as a substitute for both and is actually highly recommended to do so.

Here are the few reasons in regards to the ArrayDeque implementation advantages which makes it more preferrable than Stack and LinkedList:

1. Better performance in the real world:

• ArrayDeque:
  - continuous memory due to internal array
  - this brings better cache locality
  - less pointer chasing
• LinkedList
  - every element is a separate object (LinkedList.Node) — thus each element is spread in different areas of the heap, not next to each other
  - cache misses
  - this brings more GC pressure

2. Less memory overhead

• each LinkedList node maintains three references — next, prev and current element
• ArrayDeque maintains an internal array of objects placed next to each other in memory

3. No synchronization overhead (when compared to Stack). Stack is a wrapper around java.util.Vector where each method is synchronized with a global lock. Thus, only a single thread can operate on the stack instance. This can performance overheads, as the threads waiting to use the stack all are blocked, thus causing lock contention.

ArrayDeque is not thread safe. We can use it in a single-threaded context without the synchronization overhead which java.util.Stack has.

There’s a thread-safe equivalent without a global lock called ConcurrentLinkedQueue. It is a whole other topic.

ArrayDeque doesn’t allow null values which prevent NullPointerException s. We can use Optionals to handle empty values.