Array Deque

Implementing an ArrayDeque wasn’t hard nor easy – it just required work. For me, I had to review once again what’s the abstract data type ArrayDeque and how basing on how it functions, I got an idea how to implement it. Coding it, was the challenging part. It was “How do I translate what I know into code?” So, I searched in the net, and got the idea. An ArrayDeque is basically a list that has certain functions for us to manipulate it. So, I started with the easy ones such as adding and removing the first and last. set, get, add and remove was a little tricky because I had to work within the list, as compared to the former where I add or remove in the first or last element. After watching a couple of videos, I understand how it works, and implemented it. Also, I was able to get help from my classmates so I’m also thankful for that one. Having interaction with others can surely help in the learning process! (Oh I miss face to face classes :()

The main operations and their time complexities in ArrayDeque are as follows:

• add_first(x) – O(1)
• add_last(x) – O(1)
• add(x, i) – O(1 + min(i, i – n)) or O(n)
• remove_first(x) – O(1)
• remove_last(x) – O(1)
• remove(i) – O(1 + min(i, i – n)) or O(n)
• get(i) – O(1)
• set(x, i) – O(1)

Here is the code I used:

class ArrayDeque:
  def __init__(self):
    self.__array = []
    self.__size = 0

  def _len(self): 
    return len(self.__array)

  def is_empty(self):
    return len(self.__array) == 0
  
  def first(self):
    if self.is_empty():
      raise Exception("The array is empty!")

    return self.__array[0]

  def last(self):
    if self.is_empty():
      raise Exception("The array is empty!")

    return self.__array[-1]

  def add_first(self, item):
    self.__array = [item] + self.__array
    self.__size += 1
  
  def add_last(self, item):
    self.__array = self.__array + [item]
    self.__size += 1

  def add(self, item, index):
    if self.__size == 0:
      raise Exception("Array is empty! Cannot add item to index.")
    if (index > self.__size) or (index < 0):
      raise Exception("The index is out of bounds!")

    self.__array = self.__array[:index] + [item] + self.__array[index:]
    self.__size += 1

  def remove_first(self):
    self.__array = self.__array[1:]
    self.__size -= 1  

  def remove_last(self):
    self.__array = self.__array[:-1]
    self.__size -= 1

  def remove(self, index):
    if self.__size == 0:
      raise Exception("Array is empty! Cannot remove item to index.")
    if index >= self.__size:
      raise Exception("The index is out of bounds!")

    self.__array = self.__array[:index] + self.__array[index + 1:]
    self.__size -= 1

  def get(self, index):
    if self.__size == 0:
      raise Exception("The array is empty! Cannot get item from array with given index.")
    if index >= self.__size:
      raise Exception("The index is out of bounds! Cannot get item from array with given index.")
    
    return self.__array[index]

  def set(self, index, item):
    if self.__size == 0:
      raise Exception("The array is empty! Cannot set item to index.")
    if index >= self.__size:
      raise Exception("The index is out of bounds!")

    self.__array[index] = item

  def show_array(self):
    return self.__array


# tests

# ad = arraydeque.ArrayDeque()

# print(ad.is_empty())

# ad.add_first(5)
# ad.add_last(8)
# print(ad.show_array())
# ad.remove_last()
# ad.set(0,6)
# print(ad.show_array())

# ad.add(1,3)
# print(ad.show_array())
# ad.add(2,7)
# print(ad.show_array())
# ad.remove(1)
# print(ad.show_array())

# print(ad.first())

# print(ad.last())