ArrayDeque

When you work with collections, it is important to adapt their functionality to the problem you're solving. Many collections have an implemented behavior that makes it easy for you to work with them. Two widely used behaviors are demonstrated by Queue collections and Stack collections.

In this topic, we will learn to work with collections like Stacks and Queues with the help of ArrayDeque.

Stack and queue

There are two types of collections with specific behavior that you will use very often in your tasks: queues and stacks.

• Queue: it uses the FIFO behavior – the First-In-First-Out principle. In such collections, data is always added to the end and removed always from the beginning. You can see the pattern whenever you go to a supermarket and stand in a checkout queue. The first person to arrive will always be the first to be served. Its fundamental methods are enqueue (add at the end) and dequeue (remove from the beginning).

• Stack: it uses the LIFO behavior – the Last-In-First-Out principle. According to it, the last element to be added will be the first to be removed, that is, the elements are stacked. You can consider an example of putting your books into a box: you put them one on top of the other, and you will first take the top one when getting them out of of the box. Its fundamental methods are push (add at the top), pop (remove from the top), and peek, which returns the top element.

We can get the queue behavior thanks to Kotlin's MutableList, and it works as follows: using add() to enqueue, that is, add to the end and removeFirst() to remove the first element of a list. The trick is that each of the operations acts on different sides (head and tail) of the collection.

fun main() {
    val queue = mutableListOf<Int>()

    queue.add(1)
    queue.add(2)
    queue.add(3)
    queue.add(4)
    println(queue) // [1, 2, 3, 4]

    queue.removeFirst()
    queue.removeFirst()
    println(queue) // [3, 4]
}

Also, we can simulate the Stack behavior with MutableList using add() to add an element at the end and removeLast() to remove the last element. The trick is that both operations act on the same side of the collection: in this case, the tail, or the end.

fun main() {
    val stack = mutableListOf<Int>()

    stack.add(1)
    stack.add(2)
    stack.add(3)
    stack.add(4)
    println(stack) // [1, 2, 3, 4]

    stack.removeLast()
    stack.removeLast()
    println(stack) // [1, 2]
}

ArrayDeque

An ArrayDeque is a collection that implements both the Queue (First-In-First-Out) principle and the Deque (double-ended queue, First-In-First-Out, Last-In-First-Out) principles; it is also known as Array Double Ended Queue or Array Deck. It allows you to add and remove elements from both sides or ends of the collection: the collection provides methods for convenient access to the both sides. It also implements the MutableList interface and supports efficient get/set operations by index. So, with it, you can also use all the familiar MutableList methods.

Now, why do we need ArrayDeque if we can perform similar tasks using MutableList? You should use ArrayDeque whenever you need the functionality of a “double-ended queue”, queue, or stack: its methods have been semantically adapted to functionally comply with such tasks.

Let's see an example of this kind of collection.

fun main() {
    val deque = ArrayDeque<Int>()

    // as a queue, FIFO on both sides
    deque.addLast(1)
    deque.addLast(2)
    deque.addLast(3)
    println(deque) // [1, 2, 3]
    deque.removeFirst()
    deque.removeFirst()
    println(deque) // [3]

    // as a stack, LIFO on one side, i.e., the end
    deque.addLast(1)
    deque.addLast(2)
    println(deque) // [3, 1, 2]
    deque.removeLast()
    deque.removeLast()
    println(deque) // [3]
    // or LIFO on the other side, i.e., the start
    deque.addFirst(1)
    deque.addFirst(2)
    println(deque) // [2, 1, 3]
    deque.removeFirst()
    deque.removeFirst()
    println(deque) // [3]

}

Adding elements

Imagine that you want to add elements to a collection. You can do it at the beginning or at the end. Remember, if you want a queue, you must add elements at the end (the queue in a supermarket); if you want a stack, you can add them at the beginning (a stack of dirty dishes). Here are some methods to perform these tasks:

• add(): adds the specified element at the end of the list and returns true. You can pass the index as a parameter to add the element at a certain position. The index will be a positive number. It returns true because the list is always modified as the result of this operation.

• addAll(): adds all elements (collection) at the end or, if you pass an index, at this index position. It returns true because the list is always modified as the result of this operation.

• addFirst(): prepends the specified element to the collection. It means, adds it at the beginning. It returns Unit.

• addLast(): appends the specified element to the deque. It means, adds it at the end. It returns Unit.

fun main() {
    val deque = ArrayDeque<Int>()

    deque.add(1)
    deque.add(2)
    deque.add(3)
    println(deque) // [1, 2, 3]
    deque.add(1, 4)
    println(deque) // [1, 4, 2, 3]
    deque.addAll(listOf(5, 6, 7))
    println(deque) // [1, 4, 2, 3, 5, 6, 7]
    deque.addFirst(8)
    println(deque) // [8, 1, 4, 2, 3, 5, 6, 7]
    deque.addLast(9)
    println(deque) // [8, 1, 4, 2, 3, 5, 6, 7, 9]
}

Removing elements

The next step is removing elements of the collection: you can either "serve a person in the supermarket queue" – process the first item – or "clean the top dish first" in the queue of dirty dishes. Here are some methods to perform these tasks:

• remove(): removes a single instance of the specified element from the collection if it is present. It will returns true if the element has been successfully removed and false if it is not present in the collection.

• removeAll(): removes all of the collection elements that are also contained in the specified collection. It will return true if any of the specified elements was removed from the collection and false if the collection was not modified.

• removeAt(): removes the element at the specified index from the list. It will return the element that has been removed or throws IndexOutOfBoundsException if the index from the element is out of bounds.

• removeFirst(): removes the first element from the deque and returns that removed element or throws NoSuchElementException if the deque is empty.

• removeFirstOrNull(): removes the first element from the deque and returns that removed element or returns null if the deque is empty.

• removeLast(): removes the last element from the deque and returns that removed element or throws NoSuchElementException if the deque is empty.

• removeLastOrNull(): removes the last element from the deque and returns that removed element or returns null if the deque is empty.

fun main() {
    val deque = ArrayDeque<Int>()

    deque.addAll(listOf(1, 2, 3, 4, 5, 6, 7, 8, 9))
    println(deque) // [1, 2, 3, 4, 5, 6, 7, 8, 9]
    deque.remove(5)
    println(deque) // [1, 2, 3, 4, 6, 7, 8, 9]
    deque.removeAll(listOf(1, 2))
    println(deque) // [3, 4, 6, 7, 8, 9]
    deque.removeAt(2)
    println(deque) // [3, 4, 7, 8, 9]
    deque.removeFirst()
    println(deque) // [4, 7, 8, 9]
    deque.removeLast()
    println(deque) // [4, 7, 8]
    deque.clear()
    deque.removeFirstOrNull()
    println(deque) // []
    deque.removeLastOrNull()
    println(deque) // []
}

Getting elements

Imagine that you want to know who is queuing at the supermarket or what the first or last dirty plate in the pile is without processing it. You can get elements of a collection with:

• get(): returns the element at the specified index in the list (and also you can use []) or throws IndexOutOfBoundsException if the index from the element is out of bounds.

• first(): returns the first element or throws NoSuchElementException if the deque is empty.

• firstOrNull(): returns the first element or null if the deque is empty.

• last(): returns the last element or throws NoSuchElementException if the deque is empty.

• lastOrNull(): returns the last element or null if the deque is empty.

fun main() {
    val deque = ArrayDeque<Int>()

    deque.addAll(listOf(1, 2, 3, 4, 5, 6, 7, 8, 9))
    println(deque) // [1, 2, 3, 4, 5, 6, 7, 8, 9]
    println(deque[2]) // 3
    println(deque.first()) // 1
    println(deque.last()) // 9
    deque.clear()
    println(deque.firstOrNull()) // null
    println(deque.lastOrNull()) // null
    println(deque[50]) // exception java.lang.IndexOutOfBoundsException: Index: 50, Size: 9
}

ArrayDeque vs MutableList, which should you choose?

ArrayDeque and MutableList have different performance characteristics for various operations. Let's consider the main differences:

1. Adding/removing elements at the beginning:

   • ArrayDeque: Adding or removing an element from the start of the queue typically occurs in constant time O(1). This is due to the bidirectional structure of ArrayDeque.

   • MutableList: Adding or removing an element from the start of the list requires shifting all subsequent elements, making these operations proportional to the size of the list — O(n).

2. Adding/removing elements at the end:

   • ArrayDeque: Just like at the beginning, adding or removing an element from the end of the queue usually happens in constant time O(1).

   • MutableList: Adding an element to the end of the list typically happens in constant time O(1), except when array resizing is required. Removing from the end of the list also happens in O(1).

3. Accessing elements:

   • ArrayDeque: Accessing an arbitrary element by index might take longer than in MutableList because the internal representation of ArrayDeque is a circular buffer.

   • MutableList: Access to elements by index occurs in constant time O(1).

In practice, the choice between ArrayDeque and MutableList depends on which operations are most frequent and critical for your application. If you often need to add or remove elements from the beginning of a collection, ArrayDeque will be preferable. However, if the main operation is accessing elements by index, then MutableList might be a more suitable choice.

Conclusion

In this topic, we have learned how to use ArrayDeque to manage collections simulating an Array Double Ended Queue or Array Deck and thus to be able to use stacks and queues to solve our problems. It is important to understand that specifying the behavior sometimes helps us find the most appropriate collection for each task. Remember, ArrayDeque offers all the MutableList methods you already know as well as the specific methods for the chosen behaviors. It is an important type of collection for you to use in your future projects.

Now is the time to do some tasks to check what you have learned. Are you ready?