1. 顺序表

顺序表就是一种可以让数据存储在一块连续的内存空间中的结构，例如，Python的list类型就是一种顺序表。

其增删改查操作比较简单，这里简单记录一下：

增

创建一个新的顺序表。需要事先声明一块内存空间，这就是顺序表的大小。有两种开辟内存空间的方法：动态根据数据大小开辟和静态预设数值开辟。前者需要知道数据的大小，后者内存可能会浪费。Python中的list类型是根据前者开辟内存空间。

增大顺序表的大小。数据比顺序表大，就会溢出。类似于创建表，也有两种增大顺序表的方法：动态根据数据大小新增和静态根据预设数值开辟（一般新增半个或一个顺序表大小）。

插入。需要从最后一位数据到插入位置整体往后面挪一位。过程中需要考虑数据溢出的问题。时间复杂度最好的情况所有插入的数据都在最后一位，为 \(O(n)\)；最坏的情况是所有插入数据都在第一位，为 \(O(n^2)\)
删

从删除位置的后一位到最后一位整体往前挪一位即可，然后把最后一位删除即可。如果删除位置为最后一位，直接删掉最后一位即可。时间复杂度最好的情况所有删除的数据都在最后一位，为 \(O(n)\)；最坏的情况是所有删除数据都在第一位，为 \(O(n^2)\)
改

对应索引元素改变即可。这里要考虑改变的元素大小不一样的情况。最好和最坏的时间复杂度都是 \(O(n)\)
查

返回对应索引的结果。最好和最坏的时间复杂度都是 \(O(n)\)

2. 线性链表

2.1. 单链表

单链表是一种线性表，不同于顺序表，其存储单元可以是不连续的。

相对于顺序表，其优点为：

内存是动态分配，不会出现闲置和溢出的现象；
增删操作不需要移动元素，节省增删操作的时间，所以适合频繁需要频繁增删操作的场合。
增删改查操作的最好和最坏的时间复杂度都是 \(O(n)\)

其缺点为：

每个单链表节点需要两份存储空间——数据域和指针域，比每个顺序表节点多出一个存储空间。
系统对连续的内存进行操作比对离散的内存进行操作所消耗的资源小。

单链表的增删改查的Python实现代码可以查看这里：传送门，具体就不详细记录了，看代码理解即可。

下面记录一些代码实现的小trick

2.1.1. 模拟节点

因为Python是没有指针这一概念的，所以只能创建一个 Node 类来模仿节点。

class Node:
    def __init__(self, data, next=None):
        """
        data: 数据域
        next: 结点指针
        """
        self.data = data
        self.next = next

2.1.2. 哨兵指针

一般地，对链表的操作的代码一般格式如下

def func(head):
    p = head
    while p and status():
        operate()
        change_status()
        p = p.next
    operate()

但上面的格式只能用于理论下的链表情况

理论上，头节点是一个空的节点，指向第一个数据节点，但现实应用中，如果链表很多，则需要很大的内存空间来存储头节点，所以一般我们都使用第一个数据节点作为头节点（类比git的头指针）。

但采用这种存储方式，对第一个节点进行增删改操作时，就会出现问题。例如，如果对第一个进行删除操作，此时，就会删除头节点，这就意味着整个链表都丢失了。

所以我们对节点增删改操作时，需要对当前节点判断是否为头节点。如果不想另外写判断语句，这里有个比较优雅的解决办法，我们可以新建一个节点作为临时头节点——哨兵（Sentinel）节点，并将其指向第一个节点。以哨兵节点作为链表操作的开端，当一切操作完成后，把哨兵节点指向的节点当做头节点返回即可。

def func(head):
    d = Node(data=None, next=head)
    p = d
    while p.next and status():
        change_status()
        p = p.next
    operate()
    head = d.next