文章目录
链表的概念及结构
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成，每个结点包括两个部分：一部分是存储数据元素的数据域，另一部分是存储其他结点地址的指针域。
结构：
就拿单链表的结构举例，其逻辑结构如下：
可以看出该链表有一个头结点pList,用来储存单链表第一个节点的地址，第一个节点的指针域储存第二个节点的地址，依次到最后一个节点，最后一个节点的指针域就为NULL,这就是一个简单的单链表的逻辑结构。
这里有几点需要提示：
1.从上图可以看出，链式结构在逻辑上是连续的，但在物理上不一定连续
2.现实中的节点一般都是从堆上申请出来的
3.从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续
在实际中，链表的结构多种多样，具体有如下：
1）带头/不带头
2）单向/双向
3）循环/非循环
虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：
1.无头单向非循环链表：
无头单向非循环链表结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。
2.带头双向循环链表
带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而相对简单。
本篇博客主要就是对无头单向非循环链表的详解。
初始化链表
初始化链表就是首先定义一个结构体，该结构体包含两个成员，一个为数据域，用来存储数据；另一个为指针域，用来保存下一节点的地址，具体如下：
typedef int SLTDataType; //对类型进行重定义，方便后期改变
typedef struct SListNode //对结构体进行重定义，方便使用
{
SLTDataType data; //数据域，用于存储该节点的数据
struct SListNode* next; //指针域，用来存放下一节点的地址
}SLTNode;
打印单链表
即将单链表中的每个节点的数据域中的内容打印出来，方便查看其中的内容并调试。
void SLTPrint(SLTNode* phead)
{
SLTNode* cur = phead; //定义一个标记指针指向头节点
while (cur!= NULL) //对链表遍历
{
printf("%d->", cur->data);
cur = cur->next; //若节点的指针域不为NULL(即不为尾节点)，就将标记指针向前移动一步
}
printf("NULL");
printf("\n");
}
创建新节点
在对链表进行操作时（增删查改），有时会需要一个新节点来完成这些操作。
SLTNode* BuySListNode(SLTDataType x)
{
SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode)); //定义新节点并用malloc开辟空间
if (node == NULL)
{
printf("malloc fail!\n");
exit(-1);
}
node->data = x; //新节点数据域为传入该函数的参数x
node->next = NULL; //指针域为NULL
}
计算链表节点数
对链表进行遍历，定义一变量用来计数，返回的该变量的值就为节点数，很容易实现：
int SListSize(SLTNode* phead)
{
int size = 0;
SLTNode* cur = phead;
while (cur)
{
size++;
cur = cur->next;
}
return size;
}
单链表头插
即在表头插入一个新节点，新节点就为表头
void SListPushFront(SLTNode** pphead, SLTDataType x) //pphead为一个二级指针，该二级指针指向头节点的地址，所以*pphead就为头节点的地址
{
assert(pphead);//断言，若pphead为NULL,则程序会报错
SLTNode* newnode = BuySListNode(x);//申请一个新节点
newnode->next = *pphead;//使新节点的指针域指向第一个节点（1）
*pphead = newnode;//此时*pphead就为新插入的头节点的地址（2）
}
注：上述程序中的第（1）步与第（2）步的顺序不能颠倒，若颠倒，则原本头节点的地址就会被覆盖(丢失)，而无法使新节点与原头节点建立起联系。
单链表尾插
即在表尾插入一个节点，新节点就为表尾，若链表为空链表，则需重新创建一个节点，具体如下：
void SListPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);//断言
if (*pphead == NULL)//链表为空链表，则新创建一个节点
{
SLTNode*newnode= BuySListNode(x);
*pphead = newnode;
}
else
{
SLTNode* tail = *pphead;//定义一个标记指针指向头节点
while (tail->next != NULL)//寻找尾结点
{
tail = tail->next;
}
SLTNode* newnode = BuySListNode(x);//新建一个要插入的节点
tail->next = newnode;//使原表尾的指针域指向新节点
}
}
特定位置插入
特定位置之前插入
给定一个特定的位置(地址),在这个位置前插入给定的值x,图解如下：
如上图，若要在d2前插入一个新节点，首先需将新节点的指针域存储d2的地址，再将d1的指针域指向新节点，具体实现方法如下：
void SListInsert(SLTNode** pphead, SLTNode*pos, SLTDataType x)
{
assert(pphead);
//头插
if (*pphead == pos) //当表只有一个节点时，可直接复用头插的方法
{
SListPushFront(pphead,x);
}
else //中间插入
{
SLTNode* prev = *pphead;
while (prev->next != pos) //找到pos的前一个节点
{
prev = prev->next;
}
SLTNode*newnode = BuySListNode(x);
newnode->next = pos;
prev->next = newnode;
}
}
特定位置后插入
同在特定位置前插入的方法一样，因为给定了位置，又在该位置之后插入，所以实现起来相对简单。
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos); //断言，传入的位置指针不能为空
SLTNode* newnode = BuySListNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
单链表头删
即删除原先的头节点，新的头节点就为原本的第二个节点。
void SListPopFront(SLTNode** pphead)
{
assert(pphead);
if (*pphead == NULL) //若链表为空，则直接结束
{
return;
}
SLTNode* Next = (*pphead)->next; //定义一个指针指向第二个节点
free(*pphead); //将原本指向头节点的指针释放掉
(*pphead) = Next; //新头节点指向第二个节点
}
单链表尾删
即删除尾节点，当链表只有一个节点时，尾删后就为空链表；当链表有多个节点时，删掉尾节点后原链表的倒数第二个就变为尾删后的尾节点。
void SListPopBack(SLTNode** pphead)
{
assert(pphead);
if (*pphead == NULL) //当链表为空时，直接结束
{
return;
}
//一个节点
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
//多个节点
else
{
SLTNode* tail = *pphead;
while (tail->next->next != NULL) //通过循环找到尾节点的前一个节点
{
tail = tail->next;
}
free(tail->next); //释放掉尾节点
tail->next = NULL; //将新的尾节点的指针域置空
}
}
特定位置删除
删除特定位置的节点
即使该位置的前一个节点指向该位置的后一个节点，再将该位置的节点释放即可，例如如下图删除d2节点：
void SListErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead);
assert(pos);
if (*pphead == pos) //当链表只有一个节点时，直接复用头删的方法
{
SListPopFront(pphead);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos) //定义的prev指针用来找到该位置的前一个节点
{
prev = prev->next;
}
prev->next = pos->next; //pos的前一个节点指向pos的后一个节点
free(pos); //释放掉pos
pos = NULL;
}
}
删除特定位置的后一节点
因为是删除该节点的后一个位置，所以不用再找到被删除节点的前一个位置，实现起来相对容易：
void SListEraseAfter(SLTNode* pos)
{
assert(pos);
SLTNode* Next = pos->next; //保存给定位置的后一个节点的地址
pos->next = Next->next; //使pos处的节点的指针域指向被删除节点的后一个节点的位置
free(Next); //释放掉被删除的节点，防止内存泄露
Next = NULL; //置空
}
单链表查找
通过遍历查找到目标节点 x ,并返回该节点的位置，若未找到则返回NULL ，实现起来比较容易。
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
SLTNode* cur = phead;
while (cur)
{
if (cur->data == x)
{
return cur;
}
else
{
cur = cur->next;
}
}
return NULL;
}
修改链表
有手就行的修改操作，将指定位置的节点修改为 x 即可。（因为太简单，但为了将增、删、查、改的功能写完整，索性还是写一下）
void SListModify(SListNode* pos, SLTDataType x)
{
pos->data = x;//将结点的数据改为目标数据
}
销毁单链表
当使用完单链表后，防止内存泄露，需要销毁链表。
void SListDestory(SLTNode** pphead)
{
assert(pphead);
SLTNode* cur = *pphead; //定义一个标记指针，用于节点的移动
while (cur)
{
SLTNode* Next = cur->next; //保存被释放节点的后一个节点的地址，防止节点被释放后找不到后一节点的地址
free(cur);
cur = Next;
}
*pphead = NULL; //节点释放完后将指向头节点的指针置空
}
数据结构单链表的内容到此结束，如有讲解不当的地方欢迎各位博友指出！