线性表概念
线性表可以看做抽象的数据类型。可以看做有穷个元素排列成的列表，这个列表可以包含零个或多个元素。
在一个非空的线性表中存在唯一的首元素和尾元素，除了首元素外其他任意元素都有一个前驱元素；处尾元素外其他任意元素都有后一个继元素。
线性表的基本操作：
判空is_empty(self)；长度len(self)；表前插入元素prepend(self, item)；表后插入元素append(self, item)；任意位置插入元素insert(self, elem, i)；删除第一个元素del_first(self)；删除最后一个元素del_last(self)；删除任意元素del(self, i)；查找任意元素search(self, i)；
线性表的实现方式
顺序表，链接表（链表）。顺序表是在内存中开辟一大块连续的空间作为存储区；而链表则是链接一系列的存储空间来存储元素
顺序表
顺序表的两种布局
![]()
顺序表的两种基本形式.png
顺序表的两种基本形式.png
a中顺序表对象的存储对象类型相同且存储区起始位置为l0，表元素地址计算公式为l0+c*i，其中i为存储对象的大小。对于不同占用不同内存大小的存储对象可以采用b方式。b顺序表各单元保存相应元素的引用信息，引用信息的大小是相同的。
基本操作
- 创建
创建空表时，需要分配一块元素内存，记录表的容量并将元素计数设置为0。创建好存储去后应立即设置表的信息域。 -
加入元素顺序表增加元素.png
不需要保留原有的顺序，操作时间复杂度为O(1)，保序时间复杂度为O(n)
-
删除元素顺序表增加元素.png
尾部删除和非保序定位删除时间复杂度为O(1)，保序定位删除的时间复杂度为O(n)。
顺序表实现方式
顺序表两种基本的实现方式
- 一体式存储表的信息与元素存储区连续的排列在一起，整体性强易于管理。表一旦创建存储区的大小确定，存储量满后需要重新创建一个更大的空间，需要修改原来元素的所有存储位置。
- 分离式通过两个对象实现，创建和管理相对复杂。改变容量过程：
- 申请更大的存储空间
- 把表中已有的元素复制到新的存储区。
- 用新的元素存储区替换原来的元素存储区
- 加入新的元素
存储区的扩充策略
- 固定扩充：操作次数多节约空间
- 加倍扩充：空间换时间
Python中的list和tuple
python中的list和tuple都采用顺序表结构。其中tuple是不可变结构不支持内部操作。
list采用连续表（访问：O(1)时间复杂度，顺序不变），分离式技术（更换存储区id不变）
总结
- 顺序表可以实现O(1)时间的元素访问。
- 顺序表的建立需要提前考虑元素存储区的大小，一旦确定了存取块的大小，可容纳单元不会随着元素的插入/删除而改变。若存储块很大却只存储很少的元素会造成存储空间的浪费。
- 插入或删除表元素需要移动表内的元素，效率低。
