配列・リストを自己実装

• 追加挿入はリストの方がO(N)で早い。配列は1つずつずらすのでO(N)となる
• ランダムアクセスは配列のO(1)で早い。リストは先頭から順に探索するため（O(N)）となる
• 配列は連続、リストは次のノードをポインタで指しているので、不連続。
• 配列は連続の為、容量があふれたときに別のメモリ領域に２倍の領域に格納し直す

配列(Array)

class Node:
    def __init__(self, data):
        self.data = data

class Array:
    def __init__(self):
        self.size = 0
        self.array = []

    # Random Access(O(1))
    def data(idx):
        return self.array[idx].data

    def append(self, data):
        self.insert(self.size, data)

    # insertion(O(n))
    def insert(self, idx, data):
        if self.size == 0:
            self.array.append(Node(data)) 
        else:
            self.array.append(None)
            # 後ろに一つずつずらす
            i = self.size
            for i in reversed(range(idx, self.size)):
                self.array[i + 1] = self.array[i]
            self.array[idx] = Node(data)
        self.size += 1

    def remove(self, idx):
        for i in reversed(range(idx, self.size - 1)):
            self.array[i] = self.array[i + 1]
        self.size -= 1

    def print_all(self):
        for i in range(self.size):
            print(str(self.array[i].data) + " ", end = "")
        print()

if __name__ == "__main__":
    ary = Array()
    print("size=" + str(ary.size))
    ary.append(100)
    ary.append(300)
    ary.append(200)
    ary.print_all()
    print("size=" + str(ary.size))
    ary.insert(1, 400)
    ary.print_all()
    ary.insert(0, 500)
    ary.print_all()
    ary.remove(3)
    ary.print_all()

リスト

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class List:
    def __init__(self):
        self.head : Node = None

    # Random Access(O(1))
    # def data(idx):
    #     temp = 
    #     return self.array[idx].data

    def size(self):
        temp = self.head
        size = 0
        while temp is not None:
            temp = temp.next
            size += 1
        return size
            
    def append(self, data):
        self.insert(self.size(), data)

    # insertion(O(1))
    def insert(self, idx, data):
        node = Node(data)
        if idx == 0:
            node.next = self.head
            self.head = node
        elif (0 < idx and idx <= self.size()):
            i = 0
            prev = self.head
            while prev is not None:
                if (i + 1 == idx):
                    node.next = prev.next
                    prev.next = node
                    break;
                prev = prev.next
                i += 1            

    def remove(self, idx):
        if idx == 0:
            self.head = head.next
        elif (0 < idx and idx <= self.size()):
            i = 0
            prev = self.head
            while prev is not None:
                if (i + 1 == idx):
                    prev.next = prev.next.next
                    break;
                prev = prev.next
                i += 1            

    def print_all(self):
        print("== print all ==")
        temp = self.head
        while temp is not None:
            print(str(temp.data) + " ")
            temp = temp.next

if __name__ == "__main__":
    l = List()
    print("size=" + str(l.size()))
    l.append(100)
    l.append(300)
    l.append(200)
    l.print_all()
    print("size=" + str(l.size()))
    l.insert(1, 400)
    l.print_all()
    l.insert(0, 500)
    l.print_all()
    l.remove(3)
    l.print_all()