Update: Yes, shifting the elements when deleting would be good.

Update 2: If prepend cannot be achieved in O(1) O(n) is ok.

In this first problem, your task is to complete the implementation of the ArrayList class below. There is a caveat though. Python does not support regular arrays; instead, they support lists. In fact, their list data structure is actually implemented using logic that is very similar to the one you are being asked to implement in this lab. To mitigate this limitation, you are provided with an Array class, which you are required to use to implement ArrayList. An example of how to use this class is provided below.

Array Class:

ArrayList Class:

class Array: def __init__(self, size): self.data = [None] * size IIIIIII def _getitem_(self, idx): "'"'Implements 'value = self[idx] assert(isinstance(idx, int)) if idx = len(self.data): raise IndexError return self.data[idx] def _setitem_(self, idx, value): "Implements 'self[idx] assert(isinstance(idx, int)) = value III if idx = len(self.data): raise IndexError self.data[idx] = value def _len__(self): ""Implements 'len(self)' return len(self.data) def class ArrayList: _init__(self, size=1000): self.max_size = size # maximum memory capacity self.data = Array(self.max_size) # create initial array self.curr_size = 0 # current actual size # TODO: Feel free to add more lines here # TODO: Implement this method - Required Time Complexity: 0(1) def getitem_(self, idx): Implements 'value = self[idx]' Raises IndexError if idx is invalid." raise Not ImplementedError() # TODO: Implement this method - Required Time Complexity: 0(1) def setitem__(self, idx, value): """Implements 'self[idx] = value' Raises IndexError if idx is invalid." raise Not ImplementedError() def len__(self): """Implements 'len(self) return self.curr_size # TODO: Implement this method - Required Time Complexity: 0(1), except # when you need to create a larger array to fit more elements def append(self, value): ili Appends value to the end of this list." raise Not ImplementedError() # TODO: Implement this method - Required Time Complexity: 0(1), except # when you need to create a larger array to fit more elements def preprend(self, value): Prepends value to the start of this list." raise NotImplementedError() # TODO: Implement this method - Required Time Complexity: 0(n), except # when idx == 0 or idx == len(self). In these cases, call append/prepend def insert(self, idx, value) : Inserts value at position idx, shifting the original elements down the list, as needed. Note that inserting a value at len(self) equivalent to appending the value --- is permitted. Raises IndexError if idx is invalid." raise NotImplementedError() # TODO: Implement this method - Required Time Complexity: 0(n), except # when 'value' is the first element in the list. In that case, # the expected time complexity is 0(1) def remove(self, value): """Removes the first (closest to the front) instance of value from the list. Raises a ValueError if value is not found in the list." raise NotImplementedError() # TODO: Implement this method Required Time Complexity: 0(n), except # when idx' == 0 or idx == len(self) - 1. In those cases, # the expected time complexity is 0(1) def delete(self, idx): "Removes the element at index 'idx' from the list. Raises a IndexError if index is invalid". raise Not ImplementedError() # TODO: Implement this method - Required Time Complexity: O(n) def ntains_(self, value) : "Implements val in self'. Returns true iff value is in the list." raise Not ImplementedError() class Array: def __init__(self, size): self.data = [None] * size IIIIIII def _getitem_(self, idx): "'"'Implements 'value = self[idx] assert(isinstance(idx, int)) if idx = len(self.data): raise IndexError return self.data[idx] def _setitem_(self, idx, value): "Implements 'self[idx] assert(isinstance(idx, int)) = value III if idx = len(self.data): raise IndexError self.data[idx] = value def _len__(self): ""Implements 'len(self)' return len(self.data) def class ArrayList: _init__(self, size=1000): self.max_size = size # maximum memory capacity self.data = Array(self.max_size) # create initial array self.curr_size = 0 # current actual size # TODO: Feel free to add more lines here # TODO: Implement this method - Required Time Complexity: 0(1) def getitem_(self, idx): Implements 'value = self[idx]' Raises IndexError if idx is invalid." raise Not ImplementedError() # TODO: Implement this method - Required Time Complexity: 0(1) def setitem__(self, idx, value): """Implements 'self[idx] = value' Raises IndexError if idx is invalid." raise Not ImplementedError() def len__(self): """Implements 'len(self) return self.curr_size # TODO: Implement this method - Required Time Complexity: 0(1), except # when you need to create a larger array to fit more elements def append(self, value): ili Appends value to the end of this list." raise Not ImplementedError() # TODO: Implement this method - Required Time Complexity: 0(1), except # when you need to create a larger array to fit more elements def preprend(self, value): Prepends value to the start of this list." raise NotImplementedError() # TODO: Implement this method - Required Time Complexity: 0(n), except # when idx == 0 or idx == len(self). In these cases, call append/prepend def insert(self, idx, value) : Inserts value at position idx, shifting the original elements down the list, as needed. Note that inserting a value at len(self) equivalent to appending the value --- is permitted. Raises IndexError if idx is invalid." raise NotImplementedError() # TODO: Implement this method - Required Time Complexity: 0(n), except # when 'value' is the first element in the list. In that case, # the expected time complexity is 0(1) def remove(self, value): """Removes the first (closest to the front) instance of value from the list. Raises a ValueError if value is not found in the list." raise NotImplementedError() # TODO: Implement this method Required Time Complexity: 0(n), except # when idx' == 0 or idx == len(self) - 1. In those cases, # the expected time complexity is 0(1) def delete(self, idx): "Removes the element at index 'idx' from the list. Raises a IndexError if index is invalid". raise Not ImplementedError() # TODO: Implement this method - Required Time Complexity: O(n) def ntains_(self, value) : "Implements val in self'. Returns true iff value is in the list." raise Not ImplementedError()