# 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)

• O(n)

### pop

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

• 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

"""
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

"""
add an element to the beginning of an array
"""

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

raise NotImplementedError

raise NotImplementedError

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):
print(arr)

print(arr)

print(arr)

print(arr)

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