数组链表哈希表解析

动态数组代码实现

class MyArrayList:
    # 默认容量
    INIT_CAP = 1

    def __init__(self, init_capacity=None):
        self.data = [None] * (init_capacity if init_capacity is not None else self.__class__.INIT_CAP)
        self.size = 0

    # 在末尾增加
    def add_last(self, element):
        now_cap = len(self.data)
        if self.size == now_cap:
            self._resize(2 * now_cap)
        self.data[self.size] =  element
        self.size += 1


    # 在开头增加
    def add_first(self, element):
        self.add(0,element)

    # 在中间插入
    def add(self, index, element):
        # 先检查索引位置是否合理
        self._check_element_index(index)

        now_cap = len(self.data)
        if self.size == now_cap:
            self._resize(2 * now_cap)

        for i in range(self.size - 1, index - 1, -1):
            self.data[i + 1] = self.data[i]

        self.data[index] = element
        self.size += 1


    # 在末尾删除
    def remove_last(self):
        if self.size == 0:
            raise NoSuchElementException
        cap = len(self.data)
        if self.size == cap // 4:
            self._resize(cap // 2)
        delete_element = self.data[self.size - 1]

        self.data[self.size - 1] = None
        self.size -= 1

        return delete_element



    # 在开头删除
    def remove_first(self):
        return self.remove(0)

    # 删除
    def remove(self, index):
        self._check_element_index(index)

        cap = len(self.data)
        if self.size == cap // 4:
            self._resize(cap // 2)

        delete_element = self.data[index]

        for i in range(index + 1, self.size):
            self.data[i - 1] = self.data[i]

        self.data[self.size - 1] = None
        self.size -= 1

        return delete_element

    # 查
    def get(self, index):
        self._check_element_index(index)

        return self.data[index]

    # 改
    def set(self, index, element):
        self._check_element_index(index)

        old_val = self.data[index]
        self.data[index] = element

        return ola_val

    # 返回数组的长度
    def size(self):
        return len(self.size)

    # 扩容
    def _resize(self, cap):
        temp = [None] * cap
        for i in range(self.size):
            temp[i] = self.data[i]
        self.data = temp

    # 判断数组是否为空:
    def is_empty(self):
        return len(self.size) == 0

    # 判断是否是一个正确的索引
    def _is_element_index(self, index):
        return 0 <= index < self.size

    def _check_element_index(self, index):
        if not self._is_element_index(index):
            raise IndexError(f"Index: {index}, Size: {self.size}")

    # 判断是否是一个可插入的位置
    def _is_position_index(self):
        return 0 <= index <= self.size

    def _check_position_index(self, index):
        if not self._is_position_index(index):
            raise IndexError(f"Index: {index}, Size: {self.size}")

    # 打印
    def display(self):
        print(f"size = {self.size}, cap = {len(self.data)}")
        print(self.data)

# Usage example
if __name__ == "__main__":
    arr = MyArrayList(init_capacity=3)

    # 添加 5 个元素
    for i in range(1, 6):
        arr.add_last(i)

    arr.remove(3)
    arr.add(1, 9)
    arr.add_first(100)
    val = arr.remove_last()

    arr.display()