线性表
线性表是由个相同类型的数据元素组成的有限序列，它是最基本、最常用的一种线性结构。顾名思义，线性表就像是一条线，不会分叉。线性表有唯一的开始和结束，除了第一个元素外，每一个元素都有唯一的直接前驱，除了最后一个元素外，每一个元素都有唯一的直接后继。
前驱和后继
顺序表
顺序表是顺序存储方式，即逻辑上相邻的数据在计算机内的存储位置也是相邻的。顺序存储方式，元素存储是连续的，中间不允许有空，可以快速定位第几个元素，但是插入、删除时需要移动大量元素。
顺序表
链表
链表是线性表的链式存储方式，逻辑上相邻的数据在计算机内的存储位置不一定相邻。
链表
单链表
单链表是链表中的一种形式，那么如何定义单链表：
单链表结构体
单链表一般由两个变量组成，data变量代表单链表中存储的值，next变量代表单链表中指向下一个节点的指针。以下两张图分别是不带哨兵节点的单链表和带哨兵节点的单链表。
不带哨兵的单链表
带哨兵节点的单链表
单链表的操作
- 初始化
- 创建
- 查找、取值
- 插入
- 删除
初始化
初始化
初始化一般就是声明头指针。
创建
创建的方式，一般有两种头插法和尾插法
头插法
尾插法
//L为头结点，r为最后一个节点，s为新增节点
//头插法的伪代码
s->next = L->next
L->next = s
//尾插法的伪代码
r -> next = s
取值、查找
单链表的取值操作一般都是从头结点往后进行遍历，时间复杂度为O(n)。
取值和查找
//头指针L， j为所要取的数，p为当前指针, v为查找的值
//取值伪代码
i = 0;
p = L ->next;
while(p != null || i != j){
p = p ->next;
i = i + 1;
}
//查找伪代码
i = 0;
p = L ->next;
while(p != null && p ->value != v){
i++;
p = p ->next;
}
插入
插入
单链表的插入非常简便，只需将插入节点的next指针指向后一个节点，前一个节点的next指针指向插入的节点。时间复杂度O(1)。
//e为插入节点，p指针指向当前插入的节点
e ->next = p ->next;
p ->next = e;
删除
删除
单点表的删除操作也非常简便，将当前删除的节点的前一个节点的next指针指向删除节点的next指针指向的节点就好了。时间复杂度O(1)。
//p为删除节点的前一个节点，q为删除节点
p ->next = q ->next
双向链表
双向链表
双向链表与单链表相比多了一个前驱。所以在操作中，它比单链表还多了一个privor指针操作。举个插入例子：
//p为当前节点，a为插入的节点
p ->next ->privor = a
a ->next = p ->next
a ->privor = p
