list的時間復(fù)雜度

操作 平均時間復(fù)雜度
list[index]-----------O(1)
list.append-----------O(1)
list.insert-----------O(n)
list.pop(index), default last element-----------O(1)
list.remove-----------O(n)

基于列表list實(shí)現(xiàn)Array

class Array(object):

    def __init__(self, size=32):
        self._size = size
        self._items = [None] * size

    def __getitem__(self, index):
        if index > self._size:  --考慮數(shù)組越界，邊界檢查
            return 'out of range'
        return self._items[index]

    def __setitem__(self, index, value):
        if index > self._size:
            return 'out of range'
        self._items[index] = value

    def __len__(self):
        return self._size

    def clear(self, value=None):
        for i in range(len(self._items)):
            self._items[i] = value

    def __iter__(self):
        for item in self._items:
            yield item

def test_array():
    a = Array(10)
    a[0] = 1
    assert a[0] == 1      --assert 若False返回AssertionError
    assert len(a) == 10
    print(a[11])
    print(len(a))
    assert a[32] == 1

if __name__ == '__main__':
    test_array()

輸出：
out of range
Traceback (most recent call last):
10
  File "C:/Users/lyq/PycharmProjects/test_data_struct/test1/test_array.py", line 39, in <module>
    test_array()
  File "C:/Users/lyq/PycharmProjects/test_data_struct/test1/test_array.py", line 36, in test_array
    assert a[32] == 1
AssertionError