2.0.顺序表.md

线性表

一个线性表是某类元素的一个集合，还记录着元素之间的一种顺序关系。

根据线性表的实际存储方式，分为两种实现模型：

顺序表，将元素顺序地存放在一块连续的存储区里，元素间的顺序关系由它们的存储顺序自然表示。

链表，将元素存放在通过链接构造起来的一系列存储块中。

顺序表的两种存储方式：

元素内置（一体式结构）：表里存储的元素大小固定

元素外置（分离式结构）：表里只存储链接

表中存储的两个信息

1.表中的元素集合

2.信息主要包括元素存储区的容量和当前表中已有的元素个数两项

增加元素

a. 尾端加入元素，时间复杂度为O(1)

b. 中间插入，时间复杂度为O(n)

删除元素

a. 删除表尾元素，时间复杂度为O(1)

b. 中间元素删除，时间复杂度为O(n)

Python中的顺序表

list和tuple

tuple是不可变类型，即不变的顺序表，因此不支持改变其内部状态的任何操作，而其他方面，则与list的性质类似。

list就是一种采用分离式技术实现的动态顺序表。

链表与顺序表的对比

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

链表与顺序表的各种操作复杂度如下所示：

链表的主要耗时操作是遍历查找

顺序表查找很快，主要耗时的操作是拷贝覆盖