如需转载，请根据 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 许可，附上本文作者及链接。
本文作者： 执笔成念
作者昵称： zbcn
本文链接： https://1363653611.github.io/zbcn.github.io/2020/02/20/al_02%E7%BA%BF%E6%80%A7%E8%A1%A8/
线性表
概念
线性表是一种线性的数据结构，特点是在有限的非空集合中，其中第一个元素没有直接前驱元素，最后一个元素没有直接后继元素，其他元素都有唯一的前驱元素和后继元素。线性表有 顺序存储结构 和 链式存储结构.
顺序存储结构
是指将线性表中的各个元素依次存放在一组地址连续的存储单元中，通常将这种方法存储的线性表称之为 顺序表
假设，线性表的每个元素须占用m个存储单元，并以所占用的第一个单元的存储地址作为数据元素的存储位置,则线性表中第i+1个元素的存储位置location(ai+1)和第i个元素的存储位置location(ai)之间满足关系location(ai+1)=location（ai）+m. 线性表中第i个元素的存储位置与第一个元素的a1的存储位置满足以下关系,location(ai) =location(a1)+(i-1)*m. 其中，第一个元素的位置location(a1)称为 起始地址 或 基地址
顺序表逻辑上相邻的元素在物理上也是相邻的.每个元素的存储位置和线性表的起始位置相差一个和数据元素在线性表中的位序成正比的常数. 只要确定了一个元素的起始位置,线性表中的任意一个元素都可以随机获取,因此, 线性表的顺序结构是一种随机存存储结构. (java 中的 数组 array)
小结:顺序表的优缺点
- 优点:无须关心表中元素之间的关系，所以不用增加额外的存储空间；可以快速地取表中任意位置的元素。
- 缺点:插入和删除操作需要移动大量元素。使用前需事先分配好内存空间，当线性表长度变化较大时，难以确定存储空间的容量。分配空间过大会造成存储空间的巨大浪费，分配的空间过小，难以适应问题的需求。
线性表的链式存储
在解决实际问题时,有时并不适合采用线性表的顺序存储结构,例如两个一元多项式的相加、相乘、相除， 就需要另外一种存储结构- 链式存储。它采用的是 任意一组连续或者非连续存储单元存储线性表的元素. 为了表示每个元素ai 与其直接后继 ai+1 个元素的逻辑关系，链式存储不仅要存储元素本身，还需要存储一个指向其后继元素的地址。这种存储结构被称之为 节点(node). 存储元素的叫做数据域，存储地址的叫做指针域。节点元素的逻辑的顺序称之为 线性链表 或者 单链表.
因为第一个结点没有直接前驱结点，因此需要一个头指针指向它.为了方便操作放在第一个元素结点之前一个结点称之为 头结点. 头指针变成指向头结点.其数据域可以存放如线性表长度等信息，而指针存放第一个元素的地址信息。 若该链表为空，则头节点指针为空。
因为，最后一个元素没有直接后继元素，所以将其指针域设置为“Null”空。
单链表与顺序表的对比
- 存储方式:顺序表用一组连续的存储单元依次存储线性表的数据元素；而单链表用一组任意的存储单元存放线性表的数据元素.
- 时间性能：采用循序存储结构时查找的时间复杂度为O(1)，插入和删除需要移动平均一半的数据元素，时间复杂度为O(n)。采用单链表存储结构的查找时间复杂度为O(n)，插入和删除不需要移动元素，时间复杂度仅为O(1）。
- 空间性能：采用顺序存储结构时需要预先分配存储空间，分配空间过大会造成浪费，过小会造成问题。采用单链表存储结构时，可根据需要进行临时分配，不需要估计问题的规模大小，只要内存够就可以分配，还可以用于一些特殊情况，如一元多项的表示。
循环单链表
循环单链表（circular linkedlist）是首尾相连的一种单链表，即将最后一个结点的空指针改为指向头结点或第一个结点的形成一个环型
双向链表
双向链表(double linked list)就是链表中的每个结点有两个指针域，一个指向直接前驱结点，另一个指向直接后继结点。双向链表的每个结点有data域、prior域、next域，共三个域。其中，data域为数据域，存放数据元素；prior域为前驱结点指针域；next域为后继结点指针域。双向链表为了方便操作也可以增加一个头结点，同时也像单链表一样也具有循环结构，称为双向循环链表。
