数据结构与算法（python实现）_数据结构与算法:python语言实现 pdf

列表List

init[]
该操作会初始化一个Pylist对象，时间复杂度为$O(1)$
append(1)
该操作会新分配4个Pylist对象来去存储，它的容量（最多能存储多少数据）是4，但长度（实际有多少数据）小于等于4，不会一次只分配一个。当存储新数据时，如果空间足够则时间复杂度$O(1)$
当已经分配的空间不够用时，这时执行一个resize，重新分配空间（容量更大），时间复杂度退化为$O(n)$
总的平均时间复杂度为$O(1)$
insert
往中间插入，这需要重新开辟空间，时间复杂度为$O(n)$
pop
默认最后一位，时间复杂度为$O(1)$，如果pop中间的数据，时间复杂度为$O(n)$
remove
时间复杂度为$O(n)$

所以如果需要频繁的执行insert, remove 和在中间pop的操作，list可能不合适。

数组array

使用列表居多，使用array，建议使用numpy.ndarray

实现定长数组

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

    def __getitem__(self, index):
        return self._items[index]

    def __setitem__(self, index, value):
        self._items[index] = value

    def __len__(self):
        return len(self._items)

    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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

链表

单链表

class Node:
    # 定义一个节点
    def __init__(self, data=None, next_node=None):
        self.data = data
        self.next = next_node

class LinkedList:
    def __init__(self, maxsize=None):
        self.head = Node()  # 头节点是虚节点，不存储数据
        self.maxsize = maxsize
        self.length = 0
        self.tail = None

    def __len__(self):
        return self.length

    def is_empty(se
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16