一.单链表
1.链表的概念及结构
(1)概念：
链表是一种物理存储结构上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
(2)结构：
与顺序表不同的是，链表里的每个节点都是独立申请的空间。节点的组成主要有两个部分：当前节点要保存的数据和保存下一个节点的地址（指针变量）。
图中指针变量plist保存的是第一个节点的地址，即plist“指向”第一个节点，如果我们希望plist指向第二个节点时，只需要修改plist保存的内容为0x0012FFA0。
为什么还需要指针变量来保存下一个节点的位置？
链表中每个节点都是独立申请的（即需要插入数据时才去申请一块节点的空间），我们需要通过指针变量来保存下一个节点的位置才能从当前节点找到下一个节点。
(3)每个节点对应的结构体代码
(假设当前保存的节点为整数)
//定义节点的结构
typedef struct SListNode
{
int date;//节点数据
struct SListNode* next;//指向下一个节点的指针
}SLTNode;(4)链表的打印
给定的链表结构中，如何实现链表节点从头到尾的打印？
(5)思考
当我们想保存的数据类型为字符型，浮点型或者其他自定义类型时，该如何修改？
补充说明：
• 链表机构在逻辑上是连续的，在物理结构上不一定连续
• 节点一般是从堆上申请的
• 从堆上申请来的空间，是按照一定策略分配出来的，每次申请的空间可能连续，可能不连续。
我们可以用到重命名typedef，用STDateType代替链表要保存的数据类型。当我们想保存的数据类型为字符型，浮点型或者其他自定义类型时，将int修改成我们想要的数据类型。
typedef int SLTDataType;2.单链表的实现（无头+单向+非循环链表）
SList.h
typedef int SLTDataType;
//定义节点的结构
typedef struct SListNode
{
SLTDataType date;
struct SListNode* next;
}SLTNode;
void SLTPrint(SLTNode* phead);
//头部插入删除/尾部插入删除
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SListDesTroy(SLTNode** pphead);SList.c
(1)链表的打印
//链表的打印
void SLTPrint(SLTNode* phead)
{
SLTNode* pcur = phead;
while (pcur)
{
printf("%d->", pcur->date);
pcur = pcur->next;
}
printf("NULL\n");
}(2)创建新节点的函数
//创建新节点的函数
SLTNode* SLTBuyNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc fail!");
exit(1);//异常退出（非零），正常退出是（0）
}
newnode->date = x;
newnode->next = NULL;
return newnode;
}(3)尾插
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);//但*pphead可以为空，表示该节点的地址为空
SLTNode* newnode = SLTBuyNode(x);
//空链表和非控链表
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
SLTNode* ptail = *pphead;
//找尾
while (ptail->next)
{
ptail = ptail->next;
}//ptail指向的就是最后一个节点
ptail->next = newnode;
}
}(4)头插
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = SLTBuyNode(x);
newnode->next = *pphead;
*pphead = newnode;//使newnode成为新的头结点！
}(5)尾删
//尾删
void SLTPopBack(SLTNode** pphead)
{
//*pphead 也不能为空（链表不能为空），不然就没有删除的节点
assert(pphead && *pphead);
//链表只有一个节点的情况
if ((*pphead)->next == NULL)//->的优先级高于*
{
free(*pphead);
*pphead = NULL;
}
else
{
SLTNode* ptail = *pphead;
SLTNode* prev = *pphead;
while (ptail->next)
{
prev = ptail;
ptail = ptail->next;
}//ptail 为尾节点
//prev为尾节点的前一个节点
free(ptail);
ptail = NULL;
prev->next = NULL;
}
}(6)头删
//头删
void SLTPopFront(SLTNode** pphead)
{
//*pphead 也不能为空（链表不能为空），不然就没有删除的节点
assert(pphead && *pphead);
SLTNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}
(7)查找链表中有没有值为x的节点，如果有的话返回该节点
//查找链表中有没有值为x的节点，如果有的话返回该节点
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
SLTNode* ptail = phead;
while (ptail)
{
if (ptail->date == x)
{
return ptail;
}
ptail = ptail->next;
}
//没有找到
return NULL;
}(8)在指定位置之前插入数据
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead && *pphead);//链表不能为空，不然就找不到节点pos
assert(pos);
//链表只有一个节点
if (pos == *pphead)//说明是头插
{
SLTPushFront(pphead, x);
}
else
{
SLTNode* newnode = SLTBuyNode(x);
SLTNode* ptail = *pphead;
while (ptail->next != pos)
{
ptail = ptail->next;
}//ptail为pos节点的前一个节点
ptail->next = newnode;
newnode->next = pos;
}
}(9)删除pos节点
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead && pos);
//pos为头结点——>头删
if (pos == *pphead)
{
SLTPopFront(pphead);
}
else//po不是头结点
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}//prev 为pos 的前一个节点
prev->next = pos->next;
free(pos);
pos = NULL;
}
}(10)在指定位置之后插入数据
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = SLTBuyNode(x);
newnode->next = pos->next;
pos->next = newnode;
}(11)删除pos之后的节点
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos)
{
assert((pos->next) && pos);
SLTNode* next = pos->next;
pos->next = next->next;
free(next);
next = NULL;
}(12)销毁链表—>销毁一个一个的节点
//销毁链表——>销毁一个一个的节点
void SListDesTroy(SLTNode** pphead)
{
assert(pphead && *pphead);
SLTNode* pcur = *pphead;
while (pcur)
{
SLTNode* next = pcur->next;
free(pcur);
pcur = next;
}
*pphead = NULL;//别忘记销毁头结点
}3.链表的分类
链表结构非常多样，以下情况组合起来就有8种。
(1)单项或双向
(2)带头或不带头
(3)循环或不循环
虽然有那么多的链表结构，但我们最常用的只有两种：
• 无头单向非循环链表：结构简单，一般不会单独用来存放数据。实际中更多是作为其他结构的子结构，如哈希桶，图的邻接表等等。另外这种结构在笔试面试中出现很多。
• 带头双向循环链表：结构最复杂，一般用在单独存放数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码1实现以后会发现结构会带来很多优势。
二.双向链表
1.双向链表的结构
注意：这里的“带头”跟前面说的“头结点”是两个概念，实际前面的在单链表讲解中称呼不严谨。
带头链表里的头结点，实际为“哨兵位”，哨兵位节点不存储任何有效元素，只是“放哨”作用。
“哨兵位”存在的意义：
遍历循环链表避免死循环。
2.双向链表的实现
typedef int LTDateType;
typedef struct ListNode
{
LTDateType date;
struct ListNode* next;
struct ListNode* prev;
}LTNode;
//声明双向链表中提供的方法
//双向链表初始化
LTNode* LTInit2();//1以返回值的形式初始化，为了保持接口一致性
//void LTInit(LTNode** pphead);//2
//打印双向链表
void LTPrint(LTNode* phead);
//插入数据之前，链表必须初始化到只有一个节点的情况
//不能改变哨兵位的地址，因此传一级即可
//尾插
void LTPushBack(LTNode* phead, LTDateType x);
//头插
void LTPushFront(LTNode* phead, LTDateType x);
//尾删
void LTPopBack(LTNode* phead);
//头删
void LTPopFront(LTNode* phead);
//查找
LTNode* LTFind(LTNode* phead, LTDateType x);
//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDateType x);
//删除pos节点
void LTErase(LTNode* pos);//不传二级指针原因：保持接口一致性
//双向链表的销毁
void LTDestory(LTNode* phead);
//LTErase和LTDestory参数理论上要传二级指针，因为我们需要让形参的
//改变影响实参，但是为了保持接口一致性才传的一级。
//传一级指针的问题在于，当形参phead置为NULL后，实参plist不会被修改
//为NULL，因此解决方法是：调用完方法后手动将实参置为NULL。
//plist（LTDestory的方法调用后，plist保存的空间已经被释放掉了）
//若后续还需要用plist指针就会有问题。(1)打印双向链表
//打印双向链表
void LTPrint(LTNode* phead)
{
assert(phead);
LTNode* pcur = phead->next;
while (pcur != phead)
{
printf("%d->", pcur->date);
pcur = pcur->next;
}
printf("\n");
}(2)创建一个节点
//创建一个节点
LTNode* LTBuyNode(int x)
{
LTNode* node = (LTNode*)malloc(sizeof(LTNode));
if (node == NULL)
{
perror("malloc fail!");
exit(1);
}
node->date = x;
node->next = node->prev = node;
}(3)双向链表的初始化
//双向链表的初始化
//1.以返回值的形式初始化
LTNode* LTInit2()
{
LTNode* pcur = LTBuyNode(-1);
return pcur;
}
//2.以参数形式初始化
//void LTInit(LTNode** pphead)
//{
// //给双向链表创建一个哨兵位
// *pphead = LTBuyNode(-1);
//}(4)尾插
//尾插(将新节点插到头节点（哨兵位）之前)
void LTPushBack(LTNode* phead, LTDateType x)
{
assert(phead);
LTNode* newnode = LTBuyNode(x);
//将phead phead->prev newnode 正确排列
//先用新节点
newnode->prev = phead->prev;
newnode->next = phead;
//下面两行代码不能位置改变
phead->prev->next = newnode;
phead->prev = newnode;
}(5)头插
//头插（在链表里第一个有效数字的前面插）（往头结点后面插）
void LTPushFront(LTNode* phead, LTDateType x)
{
assert(phead);
LTNode* newnode = LTBuyNode(x);
newnode->prev = phead;
newnode->next = phead->next;
phead->next->prev = newnode;
phead->next = newnode;
//phead->next = newnode;
//newnode->next->prev = newnode;(这两行也可以)
}(6)尾删
//尾删
void LTPopBack(LTNode* phead)
{
//链表必须有效且不能为空（只有一个哨兵位的情况）
assert(phead && (phead->next) != phead);
phead->prev = phead->prev->prev;
phead->prev->next = phead;
//或
//LTNode* del = phead->prev;
//del->prev->next = phead;
//phead->prev = del->prev;
删除del节点
//free(del);
//del == NULL;
}(7)头删
//头删
void LTPopFront(LTNode* phead)
{
assert(phead && (phead->next) != phead);
phead->next = phead->next->next;
phead->next->prev = phead;
}(8)查找
//查找
LTNode* LTFind(LTNode* phead, LTDateType x)
{
LTNode* pcur = phead->next;
while(pcur != phead)
{
if (pcur->date == x)
{
return pcur;
}
pcur = pcur->next;
}//没有找到
return NULL;
}(9)在pos位置之后插入数据
//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDateType x)
{
assert(pos);
LTNode* newnode = LTBuyNode(x);
newnode->next = pos->next;
newnode->prev = pos;
pos->next->prev = newnode;
pos->next = newnode;
}(10)删除pos节点
//删除pos节点
void LTErase(LTNode* pos)
{
//理论上pos节点不能为phead，但是没有phead无法参加校验
assert(pos);
pos->prev->next = pos->next;
pos->next->prev = pos->prev;
free(pos);
pos = NULL;
}(11)双向链表的销毁
//双向链表的销毁
void LTDestory(LTNode* phead)
{
assert(phead);
LTNode* pcur = phead->next;
while (pcur != phead)
{
LTNode* next = pcur->next;
free(pcur);
pcur = next;
}
//此时pcur指向phead，phead没有被销毁
free(phead);
phead = NULL;
}三.顺序表与链表的优缺点分析
备注：缓存利用率参考存储体系结构及局部原理性。
