Array

What are arrays?

  • A data structure that stores data in a continuous space
  • For python, the most commonly used array-like data structure is list
  • For Python, list can hold different types of data
  • To access any element in an array, we can easily use index with time complexity of O(1)

Complexity for Python List

init

  • O(1)
  • In cpython, the init create a space of 4 to start with. If the space is full, new spaces will be needed and copy the old values into the new list

append

  • If the space is not full, it’s O(1)
  • If the space is full, it’s O(n)

insert

  • O(n)

pop

  • by default, to pop the last element, it’s O(1)
  • For other element, it’s O(n)

remove

  • O(n)

Basics of List in Python

code

# initialize an array
arr = []

# assign values to an array
for i in range(10):
    arr.append(i)

# iterate through an array with a for loop via index
print("Interate with index")

for i in range(10):
    print(arr[i], end=",")
print()

# iterate through an array with a for loop with element in array
print("Interate with element")
for ele in arr:
    print(ele, end=",")
print()
# to change the 8th element (index = 7)
print("Change an element in a list")
arr[7] = 7**2

for ele in arr:
    print(ele, end=",")
Interate with index
0,1,2,3,4,5,6,7,8,9,
Interate with element
0,1,2,3,4,5,6,7,8,9,
Change an element in a list
0,1,2,3,4,5,6,49,8,9,

Implement an Array

Initialization

  • when initialization, if initial data is a type of list, copy over value
  • create a list of None with capacity = 10

Array info

  • get size
  • get capacity
  • check if array is empty

Array Operations

Add an element

  • add to the end of array -> append
  • add to any position in array

Get an element

  • use index to get the element

Update an element

  • first get the element with index, then update

Contains

  • check if the array contains a certain ele

Find

  • if the array contains a certain ele, what’s its position/index?

Delete

  • delete an element from the array, first find the element, then move up 1 position for all the element behind it

code

class Array:
    """
    Implement an array in python
    """
    def __init__(self, data=None, capacity=10):
        """
        Initialization, if data is a type of list(array),
        copy the conent over; else create a new _data
        """
        if isinstance(data, list):
            self._data = data[:]
            self._size = len(data)
            self._capacity = capacity
            return
        self._capacity = capacity
        self._data = [None] * self._capacity
        self._size = 0

    def get_size(self):
        """
        check number of elements in array
        """
        return self._size

    def get_capacity(self):
        """
        check array capacity
        """
        return len(self._data)

    def is_empty(self):
        """
        check if an array is empty
        """
        return self._size == 0

    def add_last(self, ele):
        """
        v1. add element to the end of an array
        v2. can call add_ele
        """
        # v1
        # # before adding any element, check if the array is full
        # # for the moment raise an exception if the array is full
        # if self._size == self._capacity:
        #     raise Exception("add_last failed, array is full")

        # self._data[self._size] = ele
        # self._size += 1
        # return self._data

        return self.add_ele(ele, self._size)

    def add_first(self, ele):
        """
        add an element to the beginning of an array
        """
        return self.add_ele(ele, 0)


    def add_ele(self, ele, idx):
        """
        add element to the array at idx
        """

        # before adding any element, check if the array is full
        # for the moment raise an exception if the array is full
        if self._size == self._capacity:
            raise Exception("add_last failed, array is full")

        # make sure idx is valid
        if not 0<= idx <= self._size:
            raise Exception("add failed, idx must be between 0 and {a}".format(a=self._size))

        # move 1 position for all the elements starting from idx
        # start to move the last element, then loop to idx
        # otherwise, idx+1 will be replaced with idx
        for i in range(self._size - 1, idx - 1, -1):
            self._data[i+1] = self._data[i]

        self._data[idx] = ele
        self._size += 1
        return self._data

    def get_ele(self, idx):
        """
        get the element with index idx
        """
        if not 0<=idx<=self._size:
            raise Exception("get failed, idx must be between 0 and {a}".format(a=self._size))
        return 1


    def set_ele(self, idx, val):
        """
        set self._data[idx] as ele
        """
        if not 0<=idx<=self._size:
            raise Exception("set failed, idx must be between 0 and {a}".format(a=self._size))
        self._data[idx] = val
        return self._data

    def contains(self, target):
        """
        check if the array contains the target
        """
        for num in self._data:
            if num == target:
                return True
        return False

    def find(self, target):
        """
        if the array contains target, return its position/index
        """
        if self.contains:
            for i in range(self._size):
                if self._data[i] == target:
                    return i
        print("{a} doesn't exist in the array".format(a = target))
        return -1

    def delete(self, target):
        """
        delete target from the array
        start from idx, move up one position for all elements behind idx
        """
        if self.find(target) == -1:
            print("{a} doesn't exist in the array".format(a = target))
        idx = self.find(target)

        res = self._data[idx]
        for i in range(idx, self._size):
            self._data[i] = self._data[i+1]

        self._size -= 1
        return res



    def __str__(self):
        return "Array: {a}, Size: {b}, Capacity: {c}".format(a=self._data[:self._size], b=self._size, c=self._capacity)

    def __repr__(self):
        return self.__str__()

test

class ArrayBase:

    def get_size(self):
        raise NotImplementedError

    def get_capacity(self):
        raise NotImplementedError

    def is_empty(self):
        raise NotImplementedError

    def add_first(self):
        raise NotImplementedError

    def add_last(self):
        raise NotImplementedError

    def add_ele(self):
        raise NotImplementedError

    def get_ele(self):
        raise NotImplementedError

    def set_ele(self):
        raise NotImplementedError

    def contains(self):
        raise NotImplementedError

    def find(self):
        raise NotImplementedError

    def delete(self):
        raise NotImplementedError
arr = Array(capacity=20)
print(arr)

for i in range(10):
    arr.add_first(i)
print(arr)

arr.add_ele(100,1)
print(arr)

arr.add_first(-1)
print(arr)

arr.add_first(None)
print(arr)

arr.add_last("Python")
print(arr)

print(arr.get_ele(7))

arr.set_ele(7,5**5)
print(arr)

print(arr.contains("Python"))
print(arr.contains("Java"))

print(arr.find("Python"))
print(arr.find("Java"))

print(arr.delete(3125))
print(arr)
Array: [], Size: 0, Capacity: 20
Array: [9, 8, 7, 6, 5, 4, 3, 2, 1, 0], Size: 10, Capacity: 20
Array: [9, 100, 8, 7, 6, 5, 4, 3, 2, 1, 0], Size: 11, Capacity: 20
Array: [-1, 9, 100, 8, 7, 6, 5, 4, 3, 2, 1, 0], Size: 12, Capacity: 20
Array: [None, -1, 9, 100, 8, 7, 6, 5, 4, 3, 2, 1, 0], Size: 13, Capacity: 20
Array: [None, -1, 9, 100, 8, 7, 6, 5, 4, 3, 2, 1, 0, 'Python'], Size: 14, Capacity: 20
1
Array: [None, -1, 9, 100, 8, 7, 6, 3125, 4, 3, 2, 1, 0, 'Python'], Size: 14, Capacity: 20
True
False
13
Java doesn't exist in the array
-1
3125
Array: [None, -1, 9, 100, 8, 7, 6, 4, 3, 2, 1, 0, 'Python'], Size: 13, Capacity: 20