0、前要：顺序表的缺陷

• 在倍数增容的时候，存储空间存在一定的空间浪费
• 增容需要申请空间、拷贝数据、释放旧空间，有不小的消耗
• 头部或者中部的插入、删除效率低下，时间复杂度是O(N)
• 查找搜索缓慢，但是这个其实是可以靠树来提速的，不过这个和本此讨论的链表没有太大关系

1、链表的基本认知

（1）链表的概念

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的（逻辑结构是想象出来的/物理结构是是实实在在的，内存中如何存储表示他们之间的关系）

（2）链表的分类

• 单向、双向
• 带头、不带头
• 循环、非循环

尽管在实际中，还是单向和双向链表用的比较多

（3）链表的头节点和尾节点

一般叫做plist/phead和pback

（4）链接的本质

将后一个节点的地址存放在前一个节点里

（5）最简单和最复杂的链表结构

• 无头单向非循环链表的实现（最简单）：一般不会直接单独存放数据，实际中更多是作为其他数据结构的子结构，例如哈希桶、图的邻接表等，这种结构在面试的时候也有很多
• 有头双向循环链表的实现（最复杂）：一般直接单独存储数据，实际中使用的链表数据结构，都是带头双向循环链表，虽然结构复杂，但是在一些接口函数实现的时候就会发现反倒是变得简单了

2、无头单向非循环链表的实现（结构最简单）

（1）“无头无循环单向链表”结构体

typedef int SLTDateType;
typedef struct SListNode
{SLTDateType data;struct SListNode* next;
}SListNode;

（2）动态申请一个结点

SListNode* BuySListNode(SLTDateType x)
{//单独申请一个节点SListNode* chche = (SListNode*)malloc(sizeof(SListNode));if (!chche){perror("fail malloc");//注意perror只有在malloc、文件操作的时候才可用return NULL;}else{//初始化该节点chche->data = x;chche->next = NULL;return chche;}
}

（3）“无头无循环单向链表”打印

void SListPrint(SListNode* plist)
{SListNode* cur = plist;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL\\n");
}

（4）“无头无循环单向链表”尾插

void SListPushBack(SListNode** pplist, SLTDateType x)
{assert(pplist);//单独申请一个节点SListNode* chche = BuySListNode(x);//开始尾插节点SListNode* cur = *pplist;if (cur == NULL)//如果是空链表{*pplist = chche;}else//如果是非空链表{while (cur->next != NULL){cur = cur->next;}cur->next = chche;}/*千万不能直接cur找到整个链表的NULL，然后将新增加的节点赋值给cur（因为上一个节点的next依旧指向NULL，链表是断开的）*//*赋值的本质是拷贝*/
}

（5）“无头无循环单向链表”的头插

void SListPushFront(SListNode** pplist, SLTDateType x)
{//单独申请一个节点SListNode* chche = BuySListNode(x);chche->next = *pplist;//这个语句保证了两种情况都可以（NULL/非NULL）*pplist = chche;
}

（6）“无头无循环单向链表”的尾删

void SListPopBack(SListNode** pplist)
{assert(pplist && *pplist);//避免空指针和空链表if ((*pplist)->next == NULL)//单独处理只有一个节点的情况{free(*pplist);//哎呀，忘记释放内存了，补上*pplist = NULL;return;}//开始尾删节点SListNode* prev = *pplist;//这一步我一开始没有想到hhhhhh，prev是为了记录上一个节点SListNode* cur = *pplist;while (cur->next != NULL){prev = cur;cur = cur->next;}free(cur);//释放掉尾节点prev->next = NULL;//重新定义尾节点
}

（7）“无头无循环单向链表”头删

void SListPopFront(SListNode** pplist)
{assert(pplist && *pplist);SListNode* p = *pplist;*pplist = (*pplist)->next;//这里容易写出bug，因为“->”的优先级要比“*”高free(p);
}

（8）“无头无循环单向链表”查找

SListNode* SListFind(SListNode* plist, SLTDateType x)
{assert(plist);//保证不传空指针SListNode* cur = plist;if ((cur->next == NULL) && (cur->data == x)){return cur;}while (cur->next != NULL){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}

（9）“无头无循环单向链表”在pos位置之后插入x

// 分析思考为什么不在pos位置之前插入？tips:因为没有办法往前插入，这是单向链表的缺点
void SListInsertAfter(SListNode* pos, SLTDateType x)
{//单独申请一个节点assert(pos);SListNode* chche = BuySListNode(x);chche->next = pos->next;pos->next = chche;
}

（10）“无头无循环单向链表”删除pos位置之后的值

// 分析思考为什么不删除pos位置？tips:也是由于单向的原因，找不回去
void SListEraseAfter(SListNode* pos)
{assert(pos && pos->next);SListNode* p1 = pos->next;SListNode* p2 = p1->next;pos->next = p2;free(p1);
}

（11）链表测试用例

void test()
{SListNode* a = NULL;SListPushFront(&a, 100);//头插SListPushFront(&a, 200);//头插SListPushFront(&a, 300);//头插SListPrint(a);//打印SListNode* p = SListFind(a, 300);//查找printf("%p\\n", p);SListPopFront(&a);//头删SListPrint(a);//打印SListPopFront(&a);//头删SListPrint(a);//打印SListPopFront(&a);//头删SListPrint(a);//打印//SListPopFront(&a);//头删（头删了空链表）//SListPrint(a);//打印SListPushBack(&a, 3);//尾插SListPushBack(&a, 2);//尾插SListPushBack(&a, 1);//尾插SListPushBack(&a, 0);//尾插SListPushFront(&a, 100);//头插SListPushFront(&a, 200);//头插SListPushFront(&a, 300);//头插SListPrint(a);//打印SListPopBack(&a);//尾删SListPrint(a);//打印SListPopBack(&a);//尾删SListPopBack(&a);//尾删SListPopBack(&a);//尾删SListPrint(a);//打印SListPopBack(&a);//尾删SListPopBack(&a);//尾删SListPopBack(&a);//尾删//SListPopBack(&a);//尾删（尾删了空链表）SListPrint(a);//打印SListPushBack(&a, 3);//尾插SListPushBack(&a, 2);//尾插SListPushBack(&a, 1);//尾插SListPushBack(&a, 0);//尾插SListPushFront(&a, 100);//头插SListPushFront(&a, 200);//头插SListPushFront(&a, 300);//头插SListPushFront(&a, 400);//头插SListPrint(a);//打印p = SListFind(a, 100);//先查找得到节点地址SListInsertAfter(p, 4);//任意插入节点SListPrint(a);//打印SListPopFront(&a);//头删SListPopBack(&a);//尾删SListPopFront(&a);//头删SListPopBack(&a);//尾删SListPopFront(&a);//头删SListPopBack(&a);//尾删SListPopFront(&a);//头删SListPopBack(&a);//尾删p = SListFind(a, 4);//先查找得到节点地址SListInsertAfter(p, 100000);//任意插入节点SListPrint(a);//打印SListPopFront(&a);//头删SListPopFront(&a);//头删SListPrint(a);//打印SListPushBack(&a, 1);//尾插SListPushBack(&a, 0);//尾插SListPushFront(&a, 100);//头插SListPushFront(&a, 200);//头插SListPrint(a);//打印p = SListFind(a, 200);//先查找得到节点地址SListEraseAfter(p);SListPrint(a);//打印SListEraseAfter(p);SListPrint(a);//打印SListEraseAfter(p);SListPrint(a);//打印
}
int main()
{test();return 0;
}