[TOC]
说明：以下文字来源《大话数据结构》 作者：程杰。
定义
线性表：零个或者多个具有相同类型的数据元素的有限序列。
首先他是一个序列，也就是说，元素之间是有顺序的，若元素存在多个，则第一个元素无前驱，最后一个元素无后续，其他每个元素都有且只有一个前驱和后续。
然后，线性表强调的是有限的，小朋友班级人数是有限的，元素个数当然也是有限的。
线性表的结构
顺序存储
指的是用一段地址连续的存储单元依次存储线性表的数据元素。
其实，内存中的地址，就和图书馆或者电影院里的座位一样，都是有编号的。存储器中的每个存储单元都有自己的编号，这个编号就是地址。
插入
删除
总结
上面的说明，线性表的顺序存储结构，在存和读数据时，不管是哪个位置，时间复杂度都是0(1)，而插入或者删除的时候，时间复杂度都是0(n)，这就说明，他比较适合元素个数不太变化，而更多的是存取数据的应用。
优点和缺点
优点
- 无需为表示表中元素之间的逻辑关系而增加额外的存储空间。
- 可以快速的存取表中任一位置的元素。
缺点
- 插入和删除操作都需要移动大量元素。
- 当线性表长度变化较大时，难以确定存储空间的容量。
- 造成存储空间的"碎片"
链式存储
以前在顺序结构中，每个数据元素只需要存数据元素信息就可以了。现在在链式结构中，除了要存数据元素信息外，还要存储他的后续元素的存储地址。
结点
为了表示每个数据元素ai与其直接后续数据元素ai+1之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需存储一个指示其直接后续的信息(即直接后续的存储位置)。我们把存储数据元素信息的域称为数据域，把存储直接后续位置的域称为指针域。这两部分信息组成数据元素ai的存储映像，称为结点（Node）。
头指针
对于线性表来说，总得有个头有个尾，链表也不例外。我们把链表中的第一个结点的存储位置叫做头指针。
头结点
有时，我们为了更加方便地对链表进行操作，会在单链表的第一个结点前附设一个结点，称为头结点。头结点的数据域可以不存储任何信息。
单链表
n个结点(ai的存储映像)链结成一个链表，即为线性表(a1，a2，a3)的链式存储结构，因为此链表的每个结点中只包含一个指针域，所以叫做单链表。
单链表的整表创建
回顾一下，顺序存储结构的创建，其实就是一个数组的初始化，即声明一个类型和大小的数组并赋值的过程。而单链表和顺序存储结构就不一样了，他不想顺序存储结构这么集中，他可以很散，是一种动态结构。 对于每个链表来说，他所占用空间的大小和位置是不需要预先分配规定的，可以根系系统的情况和实际的需求及时生成。
单链表结构和顺序存储结构优缺点
对于插入或者删除数据越多的操作，单链表的效率优势就越明显。
存储分配方式
- 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素。
- 单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素。
时间性能
1. 查找
a. 顺序存储结构O(1)
b. 单链表O(n)
2. 插入和删除
a. 顺序存储结构需要平均移动表长一半的元素，时间为O(n)
b. 单链表在线出某位置的指针后，插入和删除的时间仅为O(1)
3.空间性能
a. 顺序存储结构需要预分配存储空间，分大了，浪费，分小了容易发生溢出。
b. 单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制。
循环链表
将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成了一个环，这种头尾相接的单链表称为单循环链表，简称循环链表。
双向链表
双向链表是在单链表的每个结点中，在设置一个指向其前驱结点的指针域。所以在双向链表中的结点都有两个指针域，一个指向直接后续，一个指向直接前驱。
双向链表既然比单链表多了如何可以反向遍历和查找等数据结构，那么也就需要付出一些小的代价：在插入和删除时， 需要更改两个指针变量。
静态链表
我们让数组的元素都是由两个数据组成， data和cur。也就是说，数组的每个下标都对应一个data和一个cur。数据域data，用来存储数据元素，也就是我们要处理的数据；而cur相当于单链表中的next指针，存放改元素的后续在数组中的下标，我们把cur叫做游标。
我们把这种用数组描述的链表叫做静态链表。
「真诚赞赏，手留余香」
真诚赞赏，手留余香
使用微信扫描二维码完成支付
