ArrayDeque in Kotlin

1. Overview

Kotlin’s ArrayDeque is a resizable array-based implementation of the Deque interface. It functions as a double-ended queue, allowing us to add elements or remove them from either the front or the back of the queue. Compared to using a LinkedList, it offers a more efficient alternative with less memory overhead and faster runtime for most operations.

In this article, we’ll explore the basics of using ArrayDeque in Kotlin 1.4, including how to create and initialize an ArrayDeque, how to add and remove elements from the front and back of the queue, and how to access elements in the queue.

2. Deque Data Structure

A deque allows us to insert and remove elements from both ends with constant time complexity. It combines the features of a stack and a queue, enabling us to add and remove elements from both ends. This makes it useful for implementing algorithms that require efficient insertion and removal operations.

The deque data structure can be implemented using an array or a linked list. An array-based implementation provides faster access to elements but may require resizing the array if the deque grows beyond its initial size. A linked list-based implementation does not require resizing but may be slower due to the overhead of maintaining pointers between nodes. Kotlin’s implementation uses a resizable Array and stores content in a circular buffer resizing the Array only when it’s full.

3. Creating an ArrayDeque

There are several ways we can create an ArrayDeque. The most basic way is to create a new instance of ArrayDeque:

val deque = ArrayDeque<Int>() 

This creates an empty ArrayDeque that can hold elements of type Int.

If we want to create an ArrayDeque with a specific initial capacity, we can use the following syntax:

val deque = ArrayDeque<Int>(initialCapacity) 

Where the initialCapacity parameter specifies the initial size of the array used to store elements in the deque. If we know the expected size of the deque, providing an initial capacity can improve performance by reducing the number of array resizing operations.

We can also create an ArrayDeque from an existing collection, such as a list or set, using the following syntax:

val deque = ArrayDeque(listOf(1, 2, 3, 4))

This creates an ArrayDeque with the list elements in the same order they appear in the list. Its capacity is equal to the number of elements of the provided collection.

4. Adding Elements

Whenever we add elements to an ArrayDeque, its internal implementation ensures that the underlying array has sufficient capacity for the new element. If the current capacity is reached, existing data is copied to a new array of an increased capacity.

To add an element to the beginning of an ArrayDeque, we can use the addFirst() method:

val deque = ArrayDeque(listOf(2, 3, 4))
deque.addFirst(1)

val deque = ArrayDeque(listOf(2, 3, 4))
deque.addLast(5)

5. Removing Elements

Unlike adding elements, removing elements from an ArrayDeque does not resize the underlying array data structure. Therefore, ArrayDeque’s capacity only grows in size and never shrinks.

To remove the first element of an ArrayDeque, we can use the removeFirst() method. It returns the removed element itself:

val deque = ArrayDeque(listOf(2, 3, 4))
val removedElement: Int = deque.removeFirst()

@Test
fun `throws NoSuchElementException exception removing first element from an empty array deque`() {
    val deque = ArrayDeque<Int>()
    assertThrows<NoSuchElementException> {
        deque.removeFirst()
    }
}

val deque = ArrayDeque<Int>()
val removedElement: Int? = deque.removeFirstOrNull()

6. Retrieving Elements

Internally ArrayDeque tracks the index of its head element, allowing for O(1) time complexity of retrieving elements anywhere in the underlying array.

To retrieve the first element of an ArrayDeque without removing it, we can use the first() method:

val deque = ArrayDeque(listOf(2, 3, 4))
val firstElement: Int = deque.first()

Retrieving the first element of an empty ArrayDeque would cause NoSuchElementException to be thrown:

@Test
fun `throws NoSuchElementException exception when retrieving first element from an empty array deque`() {
    val deque = ArrayDeque<Int>()
    assertThrows<NoSuchElementException> {
        deque.first()
    }
}

There’s also a safe way to retrieve the first element from an empty ArrayDeque using firstOrNull(), which returns null if the deque is empty:

val deque = ArrayDeque<Int>()
val firstElement: Int? = deque.firstOrNull()

We can also use the get() method to retrieve an element at a specific index in the ArrayDeque. It throws IndexOutOfBoundException if there is no such element at the requested index:

val deque = ArrayDeque(listOf(2, 3, 4))
val secondElement: Int = deque.get(1)

@Test
fun `throws IndexOutOfBoundsException retrieving element at non existing index`() {
    val deque = ArrayDeque(listOf(2, 3, 4))
    assertThrows<IndexOutOfBoundsException> {
        deque.get(4)
    }
}

7. Conclusion

In this article, we’ve explored the ArrayDeque data structure introduced in Kotlin 1.4. We’ve covered the basics of creating an ArrayDeque, adding and removing elements from the deque, and retrieving elements from the deque.

The ArrayDeque class provides a high-performance implementation of the deque data structure using an array-based implementation. This makes it useful for implementing algorithms that require efficient insertion and removal operations. Using the ArrayDeque class in our Kotlin programs, we can use its performance benefits and simplify our code.

The source code of all these examples can be found over on GitHub.