The ArrayQueue is a data structure for representing a sequence that allows us to efficiently add to one end of the sequence and remove from the other end. The ArrayDeque data structure allows for efficient addition and removal at both ends. This structure implements the List interface by using the same circular array technique used to represent an ArrayQueue.

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$ . Remember that 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 \ge n/ 2)$ , we shift the elements $a[i], . . . , a[n − 1]$ right by one position.

Visual demonstration

See the below illustration of add(i, x) and remove(x) operations on an ArrayDeque. Arrows denote elements being copied.

Python 3.10.4

class ArrayDeque(BaseList):
    def __init__(self, iterable=[]):
        self._initialize()
        self.add_all(iterable)
    def add(self, i, x): 
        if i < 0 or i > self.n: raise IndexError()
        if self.n == len(self.a): self._resize()
        if i < self.n/2:
            self.j = (self.j-1) % len(self.a)
            for k in range(i):
                self.a[(self.j+k)%len(self.a)] = self.a[(self.j+k+1)%len(self.a)]
        else:
            for k in range(self.n, i, -1):
                self.a[(self.j+k)%len(self.a)] = self.a[(self.j+k-1)%len(self.a)]
        self.a[(self.j+i)%len(self.a)] = x
        self.n += 1

By doing the shifting in 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 a resize() operation) is $O(1 + \text{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 + \text{min}\{i, n − i\})$ time to shift elements.

Python 3.10.4

class ArrayDeque(BaseList):
    def __init__(self, iterable=[]):
        self._initialize()
        self.add_all(iterable)
    def remove(self, i): 
        if i < 0 or i >= self.n: raise IndexError()
        x = self.a[(self.j+i)%len(self.a)]
        if i < self.n / 2:
            for k in range(i, 0, -1):
                self.a[(self.j+k)%len(self.a)] = self.a[(self.j+k-1)%len(self.a)]
            self.j = (self.j+1) % len(self.a)
        else:
            for k in range(i, self.n-1): 
                self.a[(self.j+k)%len(self.a)] = self.a[(self.j+k+1)%len(self.a)]
        self.n -= 1
        if len(self.a) >= 3*self.n: self._resize()
        return x

Summary

The following theorem summarizes the performance of the ArrayDeque data structure:

Theorem: 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; and
add(i, x) and remove(i) in $O(1+\text{min}\{i,n−i\})$ 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().

Python 3.10.4

"""Some base classes inherited by others"""
class BaseCollection(object):
    """Base class for everything"""
    def __init__(self):
        super(BaseCollection, self).__init__()
    
    def size(self):
        """This implementation works for almost every class in ODS"""
        return self.n
    
    def __len__(self):
        return self.size()
    
    def __str__(self):
        return "[" + ",".join([str(x) for x in self]) + "]"
    
    def __repr__(self):
        return self.__class__.__name__ \
            + "(["+ ",".join([repr(x) for x in self]) +"])"
class BaseSet(BaseCollection):
    """Base class for Set implementations"""
    def __init__(self):
        super(BaseSet, self).__init__()
                
    def add_all(self, a):
        for x in a:
            self.add(x)
            
    def __in__(self, x):
        return self.find(x) is not None
    def __eq__(self, a):
        if len(a) != len(self): return False
        for x in self:
            if not x in a: return False
        for x in a:
            if not x in self: return False
        return True
    def __ne__(self, a):
        return not self == a
class BaseList(BaseCollection):
    """Base class for List implementations"""
    def __init__(self):
        super(BaseList, self).__init__()
        
    def append(self, x):
        self.add(self.size(), x)
    def add_all(self, iterable):
        for x in iterable:
            self.append(x)
    def clear(self):
        """This can be overridden with more efficient implementations"""
        while self.size() > 0:
            self.remove(self.size()-1)
    def add_first(self, x):
        return self.add(0, x)
        
    def remove_first(self):
        return self.remove(0)
        
    def add_last(self, x):
        return self.add(self.size(), x)
    
    def remove_last(self):
        return self.remove(self.size()-1)
        
    def insert(i, x):
        self.add(i, x)
 
    def __iter__(self):
        """This implementation is good enough for array-based lists"""
        for i in range(len(self)):
            yield(self.get(i))
    def __eq__(self, a):
        if len(a) != len(self): return False
        it1 = iter(a)
        it2 = iter(self)
        for i in range(len(a)):
            if it1.next() != it2.next(): return False
        return True
    def __ne__(self, a):
        return not self == a
    
    def index(self, x):
        i = 0
        for y in self:
            if y == x:
                return i
            i += 1
        raise ValueError('%r is not in the list' % x)
    
    def remove_value(self, x):
        try:
            return self.remove(self.index(x))
        except ValueError:
            return False
    def __getitem__(self, key):
        return self.get(key)
    def __setitem__(self, key, value):
        return self.set(key, value)
    def __delitem__(self, i):
       self.remove(i)

Explanation

Let’s start our explanation from the start of main() in the main.py file.

Line 60: It creates an instance of the ArrayDeque class, which is a double-ended queue (deque) that can store objects of type Integer.
Line 62: It shows the empty deque.
Lines 63–65: It adds values to the deque.
Line 66: It prints the deque.
Line 68–69: It removes an element at index 1 and then prints the deque after removal.
Line 72–73: It clears the deque and prints the deque after the clear() method.

1.Overview

2.Array-Based Lists

3.Linked Lists

4.Skiplists

5.Hash Tables

6.Binary Trees

7.Random Binary Search Trees

8.Scapegoat Trees

9.Red-Black Trees

10.Heaps

11.Sorting Algorithms

12.Graphs

13.Data Structures for Integers

14.External Memory Searching

15.Wrap Up

ArrayDeque: Fast Deque Operations Using an Array

The `ArrayDeque` operations

Visual demonstration

Summary

ArrayDeque: Fast Deque Operations Using an Array

The ArrayDeque operations

Visual demonstration

Summary

The `ArrayDeque` operations