Hello大家好！很高兴我们又见面啦！给生活添点passion，开始今天的编程之路！
我的博客：<但凡.
我的专栏：《数据结构与算法之美》、《编程之路》、《题海拾贝》
欢迎点赞，关注！
目录
1、什么是链表
2、链表的实现 （C语言）
2.1节点的初始化
2.2节点的打印
2.3节点的插入
2.3.1头插
2.3.2尾插
2.3.3与顺序表对比
2.4节点的删除
2.4.1头删
2.4.2尾删
2.5查找
2.6指定位置之前插入数据
2.7指定位置之前插入数据
2.8删除数据
2.8.1删除指定位置之后的数据
2.8.2删除指定位置的数据
2.9销毁链表
3、C++实现部分单链表
1、什么是链表
虽然链表在之前结构体那一部分介绍过，但是我们在这里再介绍一下。
概念：链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构，数据元素的逻辑顺序是通过链表中的 指针链接次序实现的。
说白了就是我们给定几块空间存储数据，这几块空间就叫节点。每个节点除了存储数据以外还存储着下一个节点的地址，这样就能用过一个节点访问下一个节点。
2、链表的实现 （C语言）
我们还是向上次顺序表的实现一样，创建头文件和两个源文件，我们链表的增删查改和顺序表一样都用函数包装起来。同样我们的节点由结构体实现，包含两个元素：1、存放数据，2、下一个节点的地址。
2.1节点的初始化
我们为节点开辟空间，这个操作也叫新建节点：
SListNode* BuySListNode(SLTDateType x)
{SListNode* Node = (SListNode*)malloc(sizeof(SListNode));Node->data = x;return Node;
}其中，x是我们想存入的数据，在初始化节点的时候我们给定节点存储的数据。
2.2节点的打印
现在假设我们存入了几个节点的数据，我们想要打印一下：
void SListPrint(SListNode* plist)
{SListNode* pcur = plist;while (pcur->next){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL");
}我们先创建一个指针变量叫pcur，让他一次遍历这个链表的每一个节点，从而打印出每一个结点的数据。
2.3节点的插入
2.3.1头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{SListNode* newnode = BuySListNode(x);if (*pplist == NULL){*pplist = newnode;}else{SListNode* phead = *pplist;newnode->next = phead;phead = newnode;}
}需要注意的是，在头插时我们要先判断这个链表是否为空，如果为空那直接让新建节点作为这个链表的头节点就好了。
2.3.2尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{SListNode* newnode=BuySListNode(x);if (*pplist == NULL){*pplist = newnode;}else{SListNode* pcur = *pplist;while (pcur->next){pcur - pcur->next;}pcur->next = newnode;}
}2.3.3与顺序表对比
在顺序表中，头插的时间复杂度为O（n）,尾插的时间复杂度为O（1）,而在链表中恰恰相反。所以说对于链表和顺序表的使用不是绝对的。（以上所说的链表是指单链表）
2.4节点的删除
2.4.1头删
void SListPopFront(SListNode** pplist)
{assert(pplist && *pplist);SListNode* pcur = (*pplist)->next;free(pplist);*pplist = pcur;
}2.4.2尾删
void SListPopBack(SListNode** pplist)
{assert(pplist&&*pplist);SListNode* pcur = *pplist;SListNode* p = *pplist;if ((*pplist)->next == NULL){free(*pplist);*pplist = NULL;}while (pcur->next){p = pcur;pcur = pcur->next;}p->next = NULL;//先断开free(pcur);//先释放，再置空pcur = NULL;
}需要注意的是，只要是删除节点，我们就需要先判断一下，这个链表是否为空。这里我们选择直接断言一下。
2.5查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{SListNode* pcur = plist;while (pcur->data != x){pcur = pcur->next;}return pcur;
}我们这里想要查找的是存储数据为x的节点，返回类型为SListNode*
2.6指定位置之前插入数据
void SListInsertAfter(SListNode* pos, SLTDateType x)
{assert(pos);SListNode* newnode = BuySListNode(x);SListNode* pcur = pos->next;pos->next = newnode;newnode->next = pcur;
}我们需要判断一下这个节点是否存在。
2.7指定位置之前插入数据
void SListInsert(SListNode** head,SListNode* pos, SLTDateType x)
{assert(pos);if (pos == *head){SListPopFront(pos);}else{SListNode* newnode = BuySListNode(x);SListNode* pcur = *head;while ((pcur->next) != pos){pcur = pcur->next;}pcur->next = newnode;newnode->next = pos;}
}这里我们先判断一下，如果pos是第一个节点，那就直接调用头插的函数。
2.8删除数据
2.8.1删除指定位置之后的数据
void SListEraseAfter(SListNode* pos)
{assert(pos&&pos->next);SListNode* del = pos->next;pos->next = del->next;free(del);//别忘了释放内存del = NULL;
}2.8.2删除指定位置的数据
void SLTErase(SListNode** pphead, SListNode* pos)
{assert(pos);if (pos == *pphead){SListPopFront(pphead);}SListNode* pcur = *pphead;while (pcur->next != pos){pcur = pcur->next;}pcur->next = pos->next;free(pos);pos = NULL;
}2.9销毁链表
和顺序表一样，我们用完了应该销毁链表
void SLTDestroy(SListNode** pphead)
{assert(pphead);SListNode* pcur = *pphead;while (pcur){SListNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}3、C++实现部分单链表
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
typedef struct Node
{int a;Node* next;}Node;
Node* BuyNode(int n)
{Node* NewNode = new Node;if (NewNode == NULL){cout << "节点内存申请失败!" << endl;return NULL;}NewNode->a = n;NewNode->next = NULL;return NewNode;
}
void TouCha(Node* & ph, int x)
{Node* NewNode = BuyNode(x);NewNode->next = ph;ph = NewNode;
}
int main()
{//初始化链表Node* phead=BuyNode(5);//节点的插入TouCha(phead,5);cout << phead->a << endl;return 0;
}
我们还没说C++,所以这部分只是作为了解，后续我会出一篇从C到C++过度的博客，所以说现在这部分内容可以不看，当然我也没写全，就写了个简单的头插。
在C语言实现单链表时，我们对链表进行更改（插入、删除等）需要传入头节点的地址，也就是说形参是个双指针。而在C++中，我i们不用双指针，使用&重命名就可以完成这个操作（如上代码）。
好了，今天的内容就分享到这，我们下期再见！
