线性表

        线性表是由个相同类型的数据元素组成的有限序列，它是最基本、最常用的一种线性结构。顾名思义，线性表就像是一条线，不会分叉。线性表有唯一的开始和结束，除了第一个元素外，每一个元素都有唯一的直接前驱，除了最后一个元素外，每一个元素都有唯一的直接后继。

前驱和后继

顺序表

        顺序表是顺序存储方式，即逻辑上相邻的数据在计算机内的存储位置也是相邻的。顺序存储方式，元素存储是连续的，中间不允许有空，可以快速定位第几个元素，但是插入、删除时需要移动大量元素。

顺序表

链表

        链表是线性表的链式存储方式，逻辑上相邻的数据在计算机内的存储位置不一定相邻。

链表

单链表

        单链表是链表中的一种形式，那么如何定义单链表：

单链表结构体

        单链表一般由两个变量组成，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