定义：用一组任意的存储单元存储线性表的数据元素，这组存储单元可以存在内存中未被占用的任意位置。
在链式存储结构中，每个数据元素除了要存储数据元素信息外，还要存储它的后继元素的存储地址(指针).我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称为指针或链。这两部分信息组成数据元素称为存储印象，称为结点(Node)。
n个结点链接成一个链表，即为线性表(a1,a2,a3,…,an)的链式存储结构
因为此链表的每个结点中只包含一个指针域，所以叫做单链表
我们把链表中的开始结点的存储位置叫做头指针，最后一个结点的指针为空(NULL)
1.头指针、头结点、开始结点
开始结点：指链表中的第一个结点，它没有直接前驱
头指针：指向开始结点的指针(没有头结点的情况下,若链表有头结点，则是指向头结点的指针)，一个单链表可以由其头指针唯一确定，一般用其头指针来命名单链表，无论链表是否为空，头指针均不为空，头指针是链表的必要元素
头结点：头结点是为了操作的统一和方便而设立的，放在第一个元素的结点之前，其数据域一般无意义(但也可以用来存放链表的长度)，有了头结点，对在第一元素节点前插入节点和删除第一节点起操作与其它节点的操作就统一了，头结点不一定是链表的必须元素
2.单链表的定义
//结点的定义
typedef struct Node{
ElemType data;//数据域
struct Node *next;//指针域
}Node;
typedef struct Node *LinkList;
我们可以看到节点由存放数据元素的数据域和存放后继结点地址的指针域组成
问题:
如果p->data = ai,那么p->next->data = ?
答案: p->next->data = ai+1
注意：下方的所有算法都是基于该单链表存在头结点
3.单链表的读取
获取链表第i个数据的算法思路：
- 声明一个结点p指向链表第一个结点，初始化j从1开始
- 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j++
- 若到链表末尾p为空，则说明第i个元素不存在
- 否则查找成功，返回结点p的数据
/**
使用头指针表示单链表 LinkList L表示头指针，头指针指向头结点
*/
Status GetElem(LinkList L,int i,ElemType *e){
LinkList p = L->next;
int j = 1;
while (p && j < i) {
p = p->next;
j++;
}
if (!p || j > i) {
return ERROR;
}
*e = p->data;
return OK;
}
可以看出，此算法的时间复杂度为O(n),此算法的核心思想叫做”工作指针后移”,这其实也是很多算法的常用技术
4.单链表的插入
单链表第i个数据插入结点的算法思路：
- 声明一个节点p指向链表头结点，初始化j从1开始
- 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1
- 若到链表末尾p为空，则说明第i个元素不存在
- 否则查找成功，在系统中生成一个空结点s
- 将数据元素e复制给s->data
- 将i的next赋值给s,将i的next指向s
Status insertElem(LinkList L,int i,ElemType e){
LinkList p = L;//获取到头结点
int j = 1;
while (p && j < i) {
p = p->next;
j++;
}
if (!p || j > i) {
//超出范围了
return ERROR;
}
//分配空间，并插入
LinkList s = (LinkList)malloc(sizeof(Node));
s->data = e;
s->next = p->next;
p->next = s;
return OK;
}
5.单链表的删除
单链表第i个数据删除结点的算法思路:
- 声明结点p指向链表的头结点，初始化j=1
- 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1
- 若到链表末尾p为空，则说明第i个元素不存在
- 否则查找成功，将欲删除结点p->next赋值给q
- 单链表的删除标准语句p->next = q->next
- 将q结点中的数据复制给e，作为返回
- 释放q结点
Status deleteElem(LinkList L,int i,ElemType *e){
//头指针，指向头结点
LinkList p = L;
int j = 1;
while (p && j < i) {
p = p->next;
j++;
}
if (!p || j > i) {
return ERROR;
}
LinkList q = p->next;
//返回值
*e = q->data;
p->next = q->next;
//释放
free(q);
return OK;
}
6.单链表与线性表的顺序存储结构的效率PK
在单个元素插入与删除算法中，单链表的时间复杂度为O(n),线性表的顺序存储结构的时间复杂度也为O(n)，效率差别不大。
但是，如果我们希望从第i个位置开始，插入连续10个元素，对于顺序存储结构而言，每次插入都要移动n-i个位置，所以每次都是O(n)
而单链表，我们只需要在第一次时候，找到第i个位置的指针，此时为O(n),接下来只是简单的通过赋值移动指针而已，时间复杂度为O(1)
显然，对于插入或删除数据越频繁的操作，单链表的效率优势就越是明显
7.单链表的整表创建
顺序存储结构的线性表的整表创建，我们可以用数组的初始化来直观理解。单链表不同，它的数据可以是分散的，它的增长是动态的，所以它的创建是根据系统情况和实际需求即时生成。
创建单链表的过程是一个动态生成链表的过程，从“空表”的初始状态起，依次建立各元素结点并逐个插入链表。
创建单链表的算法思路:
- 声明一结点p和计数器变量i
- 初始化一个空链表L
- 让L的头结点的指针指向NULL，即建立一个带头结点的单链表
- 循环实现后继结点的赋值和插入
.头插法建立单链表
头插法是从一个空表开始，生成新结点，读取数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到结束为止。
简单来讲，就是把新加入的元素放在表头后的第一个为止：
- 先让新结点的next指向头结点之后
- 然后让表头的next指向新节点
void createListHead(LinkList *L,int n){
//创建头结点
LinkList p = (LinkList)malloc(sizeof(Node));
p->next = NULL;
//将头结点的指针赋值给单链表
*L = p;
srand(time(0));
//循环从头部插入
for (int i = 0; i < n; i++) {
p = (LinkList)malloc(sizeof(Node));
p->data = rand()%100+1;
//核心代码:新结点插入在头结点之后
p->next = (*L)->next;
(*L)->next = p;
}
}
.尾插法创建单链表
头插法建立链表虽然算法简单，但生成的链表中结点的次序与输入的顺序相反
尾插法刚好相反，每次把新结点都插入到最后，这种算法称之为尾插法
void createListTail(LinkList *L,int n){
//创建头结点
LinkList p = (LinkList)malloc(sizeof(Node));
p->next = NULL;
//将头结点的指针赋值给单链表
*L = p;
//中间变量
LinkList r = p;
srand(time(0));
//循环从尾部插入
for (int i = 0; i < n; i++) {
//创建新结点
p = (LinkList)malloc(sizeof(Node));
p->data = rand()%100 + 1;
//将前面结点的next指向新结点
r->next = p;
//让中间变量r指向新结点，作为后面创建结点的前驱
r = p;
}
//最后一个节点的next置为NULL
r->next = NULL;
}
8.单链表的整表删除
单链表整表删除的算法思路如下:
- 声明结点p和q
- 将第一个结点赋值给p，下一结点赋值给q
- 循环执行释放p和将q赋值给p的操作
Status clearList(LinkList *L){
//获取到第一个结点
LinkList p = (*L)->next;
LinkList q;
while (p) {
q = p->next;
free(p);
p = q;
}
(*L)->next = NULL;
//释放头结点
free((*L));
//头指针置为NULL，防止悬空指针
*L = NULL;
return OK;
}
9.单链表结构与顺序存储结构的优缺点
存储分配方式：
- 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素
- 单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素
时间性能：
-
查找
. 顺序存储结构O(1)
. 单链表O(n)
-
插入和删除
. 顺序存储结构需要平均移动表长一般的元素，时间为O(n). 单链表在计算出某位置的指针后，插入和删除时间仅为O(1)
空间性能:
-- 顺序存储结构需要预分配存储空间，分大了，容易造成空间浪费，分小了，容易发生溢出
-- 单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制
结论:
若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构
若需要频繁插入和删除时，宜采用单链表结构
10.单链表小结腾讯面试题
.题目：快速找到未知长度的单链表的中间节点
普通方法思路：
首先遍历一遍单链表以确定单链表的长度L，然后再次从头结点触发循环L/2次找到单链表的中间节点,其算法复杂度为：O(L+L/2) = O(3L/2)
巧妙方法:
利用快慢指针原理：设置两个指针search、mid都指向单链表的头结点。其中search的移动速度是mid的两倍，当*search指向末尾结点的时候，mid正好就在中间了，这也是标尺的思想
/*
快速找到未知长度的单链表的中间节点
*/
Status GetMiddleNode(LinkList L,ElemType *e,int *index){
//使用快慢指针方法 search遍历到末尾，mid速率是search的一半
LinkList search,mid;
mid = search = L;
*index = 0;
while (search->next != NULL) {
(*index)++;
if (search->next->next != NULL) {
search = search->next->next;
mid = mid->next;
} else {
search = search->next;
break;
}
}
*e = mid->data;
return OK;
}
11.将单链表翻转(倒序)
思路一：一个个的将单链表的结点剥下来，然后使用头插法插在头结点之后，这样就实现了单链表的翻转
void reverseLinkList(LinkList *L){
//pre表示上一个剥解下来的结点
LinkList pre = (*L)->next;
//next表示单链表的下一个要剥离出来的结点，初始化为NULL
LinkList next = NULL;
(*L)->next = NULL;
//将所有结点一个个剥离下来，按照头插法插入
while (pre) {
next = pre->next;
pre->next = (*L)->next;
(*L)->next = pre;
pre = next;
}
}
思路二：建立一个数据为单链表结点的栈，利用栈后进先出的特性，先一个个将结点加入栈，然后再一个个推出栈，这样也实现了翻转。(算法略)
12、判断单链表中有环
有环的定义是，链表的尾结点指向了链表中的某个结点
那么，判断单链表中是否有环，主要有以下两种方法：
- 使用p、q两个指针，p总是向前走，但q每次都从头开始走，对于每个节点，看p走的步数是否和q一样。如图，当p从6走到3时，用了6步，此时若q从head触发，则只需两步就到3，因而步数不等，出现矛盾，存在环。
- 使用p、q两个指针，p每次向前走一步，q每次向前走两步，若在某个时候p == q，则存在环
方法一：
int isHasLoop1(LinkList L){
LinkList p = L,q;
int pos1 = 0,pos2;
while (p) {
q = L;
pos2 = 0;
while (q) {
if (p == q) {
//两个指向的结点相同
if (pos1 == pos2) {
//步数相同 也就是走到p的位置上，则重新开始遍历
break;
} else {
//步数不相同，确定有环
printf("环的位置在第%d个结点处",pos2);
return 1;
}
}
q = q->next;
pos2++;
}
p = p->next;
pos1++;
}
//如果走到了最后一个结点，那么说明没有环，返回false
return 0;
}
方法二：
int isHasLoop2(LinkList L){
//p是一步步走的，q是两步两步走的
LinkList p = L,q = L;
while (p && q && q->next) {
p = p->next;
if (q->next) {
q = q->next->next;
}
printf("p:%d, q:%d \n", p->data, q->data);
if (p == q) {
return 1;
}
}
return 0;
}
