The ArrayDeque allows for efficient addition and removal at both ends of the data sequence. This structure implements the List interface by using the same circular array technique used to represent an ArrayQueue,

The get(i) and set(i,x) operations on an ArrayDeque are straightforward. They get or set the array element a[(j+i)%a.length].

The implementation of add(i,x) is a little more interesting. As usual, we first check if a is full and, if necessary, call resize() to resize a. We want this operation to be fast when i is small (close to 0) or when i is large (close to n). Therefore, we check if i < n/2. If so, we shift the elements a[0],...,a[i-1] left by one position. Otherwise (i≥n/2), we shift the elements a[0],...,a[n-1] right by one position. See Fig.1 for an illustration of add(i,x) and remove(x) operations on an ArrayDeque.

By doing the shifting this way, we guarantee that add(i,x) never has to shift more than min{i,n-i} elements. Thus, the running time of the add(i,x) operation (ignoring the cost of resize() operation) is O(1 + min{i,n-i}).

The implementation of the remove(i) operation is similar. It either shifts elements a[0],...,a[i-1] right by one position or shifts the elements a[i+1],...,a[n-1] left by one position depending on whether i < n/2. Again, this means that remove(i) never spends more than O(1+min{i,n-i}) time to shift elements.

Fig.1 A sequence of add(i,x) and remove(x) operations on an ArrayDeque. Arrows denote elements being copied.

The following theorem summarizes the performance of the ArrayDeque structure.

An ArrayDeque implements the List interface. Ignoring the cost of calls to resize(), an ArrayDeque supports the operations

• get(i) and set(i,x) in O(1) time per operation
• add(i,x) and remove(i) in O(1+min{i,n-1}) time per operation.

Furthermore, beginning with an empty ArrayDeque, performing any sequence of m add(i,x) and remove(i) operations results in a total of O(m) time spent during all calls to resize().