表的概念：

一组有限的元素排成一个序列，就称为以一张表，表中包含0个多个元素，我们把含有0个元素的表称为空表，每个表都有确定的位置，称为下标，下标的位置一般从0开始

线性的概念

表中的元素之间存在一种基本关系：表中的某个元素和下一个元素有着顺序关系，即线性关系，我们这个有着线性结构的表称为线性表

线性表

• 线性表：具有相同特性元素的一个有限序列
• 一个非空的线性表中，有且存在唯一的表头（首元素）和表尾（尾元素）。
• 表中的每个元素，有且只有一个前驱元素，有一个后继元素（除尾元素外）
• 功能：创建、删除、是否为空、遍历、修改等

顺序表

我们把表中元素按顺序的存放在存储单元中，我们称为顺序表

顺序表的布局方案

顺序表有两种基本形式的布局方案：

1. 元素内置，每个元素所占存储单元大小固定相同
2. 元素外置，每个元素所占的存储单元大小不相同

顺序表的基本结构

一个顺序表包含两个基本信息：

• 表头元素：存放顺序表中容量和元素个数的数据
• 存储区：存储数据的区域

顺序表的实现结构

一体式结构：

顺序表信息和存储区连接在一起；

存储区的替换：整体搬迁，即整个顺序表对象改变
存储区的扩充：不可扩充

分离式结构

顺序表信息与数据存储区分开，顺序表信息多一个数据存储区的物理地址连接，来指向数据。

存储区替换：更换顺序表信息中的数据区链接地址，该顺序表对象不变。
存储区扩充：

• 每次扩充增加固定数目的存储位置

  • 节省空间，但是扩充操作频繁，操作次数多。

• 每次扩充容量加倍

  • 特点：减少了扩充操作的执行次数，但可能会浪费空间资源

顺序表的操作

增加元素

1. 尾端插入元素，时间复杂度为O(1)
2. 插入元素后，不需要保持原本顺序（不常见），时间复杂度为O(1)
3. 插入元素后，要保持原本顺序，时间复杂度O(n)

删除元素

1. 删除表尾元素，时间复杂度为O(1)
2. 非保序的元素删除（不常见），时间复杂度为O(1)
3. 保序的时间的元素删除，时间复杂度O(n)

python中列表和元组都采用了顺序表的实现；但是元组是不可变类型。，因此不支持改变内部状态的任何操作其他性质与列表类似

链表

我们把每个元素按链接结构存储的线性表称为链表，如图所示：

链表是一种常见的数据结构，是一种线性表，但不是像顺序表一样连续存储数据，而是在每个节点（数据存储单元）里存放下一个节点的位置信息（即地址）

节点

采用链接的思路如下：

• 把表中的元素存储在存储块中（即节点）
• 保证组成表的结构中任意一个节点可以找到与其相关的下一个节点
• 在前一个节点里用链接的方式记录下一个节点的关联

链表与顺序表的对比

链表失去了顺序表随机读取的优点，同时链表由于增加了节点的指针域，空间开销比较大，但对存储空间的使用要相对灵活

虽然复杂度都是O(n)，但是链表和顺序表在插入和删除的进行的是完全不同的操作：

• 链表的主要操作是遍历查找，删除和插入本身的复杂度就是O(1)。
• 顺序表进行插入和删除时需要对操作点之后的所有元素进行前后位移操作，只能通过拷贝和覆盖的方法进行