python配列を使用してチェーンテーブルのポリシー分析を実現

pythonチェーンテーブルデータ構造の実装:配列/ノードと参照
配列ポリシーの使用:

配列を使用して、他のオブジェクトへの参照

を格納する.

配列記憶空間過剰割当

配列が満たされた後、より大きな配列を割り当て、古い配列の内容を新しい配列にコピーする

.

class ArrayList:
    def __init__(self):
        self.size_exponent = 0
        self.max_size = 0  #         
        self.last_index = 0  #            
        self.my_array = []   #     
     
    #          
    def append(self, val):
        if self.last_index > self.max_size - 1:
            self.resize()
        self.my_array[self.last_index] = val
        self.last_index += 1
    
    #         
    def insert(self, idx, val):
        if self.last_index > self.max_size - 1:
            self.__resize()
        for i in range(self.last_index, idx - 1, -1):
            self.my_array[i + 1] = self.my_array[i]
        self.last_index += 1
        self.my_array[idx] = val
    
    #     
    def __resize(self):
        new_size = 2 ** self.size_exponent
        new_array = [0] * new_size
        for i in range(self.max_size):
            new_array[i] = self.my_array[i]   #            
        
        self.max_size = new_size
        self.my_array = new_array
        self.size_exponent += 1
        
    #        
    def __get_item__(self, idx):
        if idx < self.last_index:
            return self.my_array[idx]
        else:
            raise LookupError('index out of bounds')
    
    #       
    def __set_item__(self, idx, val):
        if idx < self.last_index:
            self.my_array[idx] = val
        else:
            raise LookupError('index out of bounds')