目录
1. 引子：什么是链表
经过学习与练习，已经掌握了顺序表的相关知识并且能够自我实现。在这一过程中，通过对其结构的实现，发现顺序表的尾部插入删除数据效率很高，可是，在头部与随机插入的场景下效率低下而且存在扩容消耗等一些问题。而有这样一种数据结构可以很好的解决顺序表存在的这些问题，将琐碎的系统空间充分利用，任意位置的插入删除效率都很高。此种数据结构称为链表，接下来进行对其的学习。
2. 简单数据结构：链表
2.1 链表简介与功能分析
简介：
链表，正如其名，存储其中的数据在物理上是离散的，各个数据间使用一条 “链子” 串联而成（记录下一元素地址的指针）。链表的具体结构存在数种，以是否带头，是否能双向访问，是否循环，这三个特点被简单分为六种，下面，我们先进行其中一种，带头单向不循环链表进行学习。
单向带头不循环链表结构图：
功能分析模块：
数据存储方式：
- 动态开辟malloc的一块块小内存块。
- 存储信息为数据值，与记录下一个结点的指针
以上两点创建的结点结构体数据管理方式：
- 增（头插，尾插，随机插入）：push_front，push_back，insert，insertafter
- 删（头删，尾删，随机删除）：pop_front，pop_back，erase，eraseafter
- 改（指定数据的修改）：modify
- 查（指定数据的查询）：find
2.2 单链表的实现
2.2.1 单链表：存储数据的结构体
链表结点的构建：
typedef int ListDataType;
typedef struct ListNode
{
ListDataType val;
//声明类型的过程中不能直接使用typedef后的名字
struct ListNode* next;
}ListNode;
2.2.2 单链表：结点创建与链表数据清理
结点创建：
ListNode* BuyNewNode(ListDataType val)
{
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
if (newnode == NULL)
{
perror("malloc failed");
exit(-1);
}
newnode->val = val;
newnode->next = NULL;
return newnode;
}
链表销毁：
过程演示：
//链表销毁
void ListDestroy(ListNode** PPhead)
{
assert(PPhead);
ListNode* Phead = *PPhead;
ListNode* cout = Phead;
if (Phead != NULL)
{
while (Phead->next != NULL)
{
Phead = Phead->next;
free(cout);
cout = Phead;
}
free(Phead);
*PPhead = NULL;
}
}
注：Phead为list的一份值拷贝，因此要想能够改变list（链表头）的值，传参是我们应该采用二重指针传址传参。
2.2.2 单链表插入数据与删除
头插，头删：
头插过程演示：
链表为空时头插：
链表不为空时头插：
头删过程演示：
//头插
void ListPush_Front(ListNode** PPhead, ListDataType val)
{
assert(PPhead);
ListNode* Phead = *PPhead;
ListNode* newnode = BuyNewNode(val);
if (Phead == NULL)
{
*PPhead = newnode;
}
else
{
ListNode* next = Phead;
newnode->next = Phead;
*PPhead = newnode;
}
}
//头删
void ListPop_Front(ListNode** PPhead)
{
assert(PPhead);
ListNode* Phead = *PPhead;
assert(Phead);
ListNode* next = Phead->next;
free(Phead);
*PPhead = next;
}
尾插，尾删：
//尾插
void ListPush_Back(ListNode** PPhead, ListDataType val)
{
assert(PPhead);
ListNode* Phead = *PPhead;
ListNode* end_node = Phead;
while (end_node != NULL && end_node->next != NULL)
{
end_node = end_node->next;
}
ListNode* newnode = BuyNewNode(val);
if (end_node == NULL)
{
*PPhead = newnode;
}
else//end_node->next == NULL
{
end_node->next = newnode;
}
}
//尾删
void ListPop_Back(ListNode** PPhead)
{
assert(PPhead);
ListNode* Phead = *PPhead;
assert(Phead);
ListNode* end_node = Phead;
//特殊情况
if (end_node->next == NULL)
{
free(end_node);
*PPhead = NULL;
}
else//end_node->next != NULL
{
//逻辑短路
while (end_node->next->next != NULL)
{
end_node = end_node->next;
}
free(end_node->next);
end_node->next = NULL;
}
}
随机插入与删除：
在指定结点（pos）之前插入：
void ListInsert(ListNode** PPhead, ListNode* pos, ListDataType val)
{
//不考虑结点不存在的情况
//与ListFind模块配合使用
assert(PPhead);
ListNode* Phead = *PPhead;
assert(Phead);
assert(pos);
//复用头插
if (pos == Phead)
{
ListPush_Front(PPhead, val);
}
else
{
ListNode* search = Phead;
//寻找pos结点
while (search->next != pos)
{
search = search->next;
}
//插入
ListNode* newnode = BuyNewNode(val);
ListNode* next = search->next;
search->next = newnode;
newnode->next = next;
}
}
在指定结点（pos）之后插入：
void ListInsertAfter(ListNode* pos, ListDataType val)
{
//结点不能为NULL
assert(pos);
ListNode* next = pos->next;
ListNode* newnode = BuyNewNode(val);
pos->next = newnode;
newnode->next = next;
}
删除指定结点（pos）之后的结点：
void ListEraseAfter(ListNode* pos)
{
assert(pos);
assert(pos->next);
ListNode* next = pos->next;
pos->next = pos->next->next;
free(next);
next = NULL;
pos->next = next;
}
删除指定结点（pos）：
void ListErase(ListNode** PPhead, ListNode* pos)
{
assert(PPhead);
ListNode* Phead = *PPhead;
assert(Phead);
assert(pos);
//头删
if (pos == Phead)
{
ListPop_Front(PPhead);
}
else
{
ListNode* search = Phead;
while (search->next != pos)
{
search = search->next;
}
ListNode* next = search->next->next;
free(search->next);
search->next = next;
}
}
2.2.3 单链表查询与修改
元素查询：
ListNode* ListFind(ListNode** PPhead, ListDataType val)
{
assert(PPhead);
ListNode* Phead = *PPhead;
assert(Phead);
ListNode* search = Phead;
while (search != NULL && search->val != val)
{
search = search->next;
}
return search;
}
数据修改：
void ListModify(ListNode* Node, ListDataType val)
{
assert(Node);
Node->val = val;
}
链表元素打印：
void ListPrint(ListNode* Phead)
{
while (Phead != NULL)
{
printf("%d->", Phead->val);
Phead = Phead->next;
}
printf("NULL\n");
}
