Search⌘ K
AI Features
Home
Courses
Data Structures with Generic Types in Python

ArrayDeque: Fast Deque Operations Using an Array

Explore the ArrayDeque data structure to understand how it supports efficient double-ended queue operations using a circular array. Learn how add and remove operations minimize shifting elements, optimizing runtime performance. This lesson enables you to implement and manipulate ArrayDeques for quick insertions and deletions at either end.

We'll cover the following...

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.

Python 3.10.4
class ArrayDeque(BaseList):
    def __init__(self, iterable=[]):
        self._initialize()
        self.add_all(iterable)
    def _initialize(self):
        self.a = new_array(1)
        self.j = 0
        self.n = 0

The ArrayDeque operations

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

Python 3.10.4
class ArrayDeque(BaseList):
    def __init__(self, iterable=[]):
        self._initialize()
        self.add_all(iterable)
    def get(self, i):
        if i < 0 or i >= self.n: raise IndexError()
        return self.a[(i+self.j)%len(self.a)]
    def set(self, i, x):
        if i < 0 or i >= self.n: raise IndexError()
        y = self.a[(i+self.j)%len(self.a)]
        self.a[(i+self.j)%len(self.a)] = x
        return y

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 aa. Remember that we want this operation to be fast when ii is small (close to 00) or when ii is large (close to nn). Therefore, we check if i<n/2i < n/2. If so, we shift the elements a[0],... ...