Data Structures with Generic Types in Python/

...

/

ArrayDeque: Fast Deque Operations Using an Array

ArrayDeque: Fast Deque Operations Using an Array

Discover how to remove and add an element in a data structure.

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.

Press + to interact
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].

Press + to interact
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 ...

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy