The ArrayDeque and LinkedList Classes – Collections: Part II

The ArrayDeque<E> and LinkedList<E> Classes

The ArrayDeque<E> and LinkedList<E> classes implement the Deque<E> interface. The ArrayDeque<E> class provides better performance than the LinkedList<E> class for implementing FIFO queues, and is also a better choice than the java.util.Stack class for implementing stacks.

An ArrayDeque<E> is also an Iterable<E>, and iteration is always from the head to the tail. The class provides the descendingIterator() method for iterating in reverse order. Since deques are not lists, positional access is not possible, nor can they be sorted. They are also not thread-safe, and null values are not allowed as elements.

The ArrayDeque<E> class provides the following constructors, analogous to the ones in the ArrayList<E> class:

ArrayDeque()
ArrayDeque(int numOfElements)

The first constructor creates a new, empty ArrayDeque with an initial capacity to hold 16 elements.

The second constructor creates a new, empty ArrayDeque with initial capacity required to hold the specified number of elements.

Click here to view code image

ArrayDeque(Collection<? extends E> c)

Creates a new ArrayDeque containing the elements in the specified collection. The ordering in the ArrayDeque is determined by the iteration order of the iterator for the collection passed as an argument.

The LinkedList<E> class provides constructors that are analogous to the first and the last constructors.

Example 15.8 illustrates the methods for inserting, examining, and removing elements from a deque. The program output shows how each method affects the deque when inserting, examining, and removing elements from either the head or the tail of a deque.

Example 15.8 Demonstrating Deque Operations

Click here to view code image

import java.util.ArrayDeque;
import java.util.Deque;
public class DequeOperations {
  public static void main(String[] args) {
    Deque<String> deque = new ArrayDeque<String>();
    System.out.println(“After creating the deque: ” + deque);
    // Insert elements:
    deque.offerFirst(“A (H)”);               // Insert at the head
    System.out.println(“After inserting at the head: ” + deque);
    deque.offerLast(“B (T)”);                // Insert at the tail
    System.out.println(“After inserting at the tail: ” + deque);
    deque.push(“C (H)”);                     // Insert at the head
    System.out.println(“After inserting at the head: ” + deque);
    deque.addFirst(“D (H)”);                 // Insert at the head
    System.out.println(“After inserting at the head: ” + deque);
    deque.addLast(“E (T)”);                  // Insert at the tail
    System.out.println(“After inserting at the tail: ” + deque);
    // Examine element:
    System.out.println(“Examine at the head: ” + deque.getFirst());
    System.out.println(“Examine at the tail: ” + deque.getLast());
    System.out.println(“Examine at the head: ” + deque.peekFirst());
    System.out.println(“Examine at the tail: ” + deque.peekLast());
    // Remove elements:
    deque.removeFirst();                     // Remove from the head
    System.out.println(“After removing from the head: ” + deque);
    deque.removeLast();                      // Remove from the tail
    System.out.println(“After removing from the tail: ” + deque);
    deque.pollFirst();                       // Remove from the head
    System.out.println(“After removing from the head: ” + deque);
    deque.pollLast();                        // Remove from the tail
    System.out.println(“After removing from the tail: ” + deque);
    deque.pop();                             // Remove from the head
    System.out.println(“After removing from the head: ” + deque);
  }
}

Output from the program:

Click here to view code image

After creating the deque: []
After inserting at the head: [A (H)]
After inserting at the tail: [A (H), B (T)]
After inserting at the head: [C (H), A (H), B (T)]
After inserting at the head: [D (H), C (H), A (H), B (T)]
After inserting at the tail: [D (H), C (H), A (H), B (T), E (T)]
Examine at the head: D (H)
Examine at the tail: E (T)
Examine at the head: D (H)
Examine at the tail: E (T)
After removing from the head: [C (H), A (H), B (T), E (T)]
After removing from the tail: [C (H), A (H), B (T)]
After removing from the head: [A (H), B (T)]
After removing from the tail: [A (H)]
After removing from the head: []

Example 15.9 illustrates using an ArrayDeque both as a LIFO stack and as a FIFO queue. Elements from an array are pushed onto the stack at (3), and then popped from the stack at (5). The call to the isEmpty() method in the while loop at (4) determines whether the stack is empty. The output shows that the elements were popped in the reverse order to the order in which they were inserted—that is, LIFO ordering.

Similarly, elements from an array are inserted at the tail of a FIFO queue at (8), and then removed from the head of the FIFO queue at (10). The call to the isEmpty() method in the while loop at (4) determines whether the FIFO queue is empty. The output shows that the elements were removed in the same order they were inserted—that is, FIFO ordering.

Note that in Example 15.9 the stack grows at the head of the deque, but the FIFO queue grows at the tail of the deque.

Example 15.9 Using Deques as a LIFO Stack and as a FIFO Queue

Click here to view code image

import java.util.ArrayDeque;
import java.util.Arrays;
/** Executes tasks. */
public class TaskExecutor2 {
  public static void main(String[] args) {
    String[] elementArray = {“sway”, “and”, “twist”, “stacks”, “tall”};     // (1)
    System.out.println(“Array of elements: ” + Arrays.toString(elementArray));
    // Using ArrayDeque as a stack:                                            (2)
    ArrayDeque<String> stack = new ArrayDeque<>();
    for (String string : elementArray)
      stack.push(string);                             // (3) Push elements.
    System.out.println(“Stack before: TOP->” + stack + “<-BOTTOM”);
    System.out.print(“Popping stack: “);
    while (!stack.isEmpty()) {                        // (4)
      System.out.print(stack.pop() + ” “);            // (5) Pop elements.
    }
    System.out.println(“\n”);
    // Using ArrayDeque as a FIFO queue:                 (6)
    elementArray = new String[] {“Waiting”, “in”, “queues”, “is”, “boring”};// (7)
    System.out.println(“Array of elements: ” + Arrays.toString(elementArray));
    ArrayDeque<String> fifoQueue = new ArrayDeque<>();
    for (String string : elementArray)
      fifoQueue.offerLast(string);                    // (8) Insert at tail.
    System.out.println(“Queue before: HEAD->” + fifoQueue  + “<-TAIL”);
    System.out.print(“Polling queue: “);
    while (!fifoQueue.isEmpty()) {                    // (9)
      String string = fifoQueue.pollFirst();          // (10) Remove from head.
      System.out.print(string.toUpperCase() + ” “);
    }
    System.out.println();
  }
}

Output from the program:

Click here to view code image

Array of elements: [sway, and, twist, stacks, tall]
Stack before: TOP->[tall, stacks, twist, and, sway]<-BOTTOM
Popping stack: tall stacks twist and sway

Array of elements: [Waiting, in, queues, is, boring]
Queue before: HEAD->[Waiting, in, queues, is, boring]<-TAIL
Polling queue: WAITING IN QUEUES IS BORING