单链表详解
本篇博客将用C语言实现的单链表进行讲解，通过一段代码一段讲解来逐个详细讲解，深入了解单链表的实现。
什么是单链表？
单链表是由一系列节点组成的数据结构，每个节点包含两部分：数据域和指针域。数据域用于存储数据元素，指针域用于指向下一个节点。单链表的最后一个节点指向NULL，表示链表的结束。
不同于顺序表，顺序表的链接是物理上的空间连续，而单链表是用指针将第一个数据的尾和下一个数据的头相接（指向同一地址），具体如下图：
单链表的结构定义
typedef int SLTDataType;
struct SListNode
{
SLTDataType data;
struct SListNode* next;
};
typedef struct SListNode SLTNode;首先通过typedef设置SLTDataType为int型，之后通过改变int的类型可以更轻松的改变单链表中的数据的类型。
在结构中再定义结构体指针，相当于逐个深入嵌套，在第一个结构中用next连接下一个结构，下一个结构中储存数据和连接下一个结构的结构体指针next，逐一递推，图示如下：
单链表的基本操作
- 创建链表：动态分配内存创建节点，通过指针连接节点形成链表。
- 插入节点：在指定位置插入新节点，调整指针连接关系。
- 删除节点：删除指定节点，调整指针连接关系并释放内存。
- 遍历链表：通过循环遍历链表中的所有节点，访问节点的数据域。
- 查找节点：根据数据值或位置查找节点。
- 反转链表：将链表的指针方向反转，实现链表的逆序。
单链表的代码实现
· 新节点的创建
SLTNode* BuySListNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
newnode->data = x;
newnode->next = NULL;
return newnode;
}· 表尾插入数据
void SListPushBack(SLTNode** pphead, SLTDataType x)
{
SLTNode* newnode = BuySListNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
// 找尾节点的指针
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
// 尾节点，链接新节点
tail->next = newnode;
}
}开文创建新节点，检查当前是否存在数据，若不存在即表头直接指向创建的newcode作为表头结构。创建结构体指针tail，若存在数据即不断递推寻找目前单链表的最后一个数据（直到找到NULL），然后再将找到最后的next地址与newcode相连，完成单链表尾部的插入。
当tail ->next为NULL时表明在当前的结构中的next指向的是NULL而不是下一个结构的地址，所以可以理解为让next指向newcode，以此完成链接。
· 表头插入数据
void SListPushFront(SLTNode** pphead, SLTDataType x)
{
SLTNode* newnode = BuySListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}创建newcode，newcode的next指向现在的表头地址即可完成链接。
· 表头删除数据
void SListPopFront(SLTNode** pphead)
{
SLTNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}（*pphead）-> next 表示未添加前的表头的next，我们在刚开始创建结构体指针指向当前表头的next，这样就相当于先将表头设置成当前表头next所连接的下一个数据的地址，然后再将刚开始的表头给free掉，这样新的表头就是刚才的结构体指针next指向的地址了。在成功转移表头后就可以将原表头空间释放，达到从表头删除数据的操作。
· 表尾删除数据
void SListPopBack(SLTNode** pphead)
{
// 1、空
if (*pphead == NULL)
{
return;
}
// 2、一个节点
else if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
// 3、一个以上的节点
else
{
SLTNode* prev = NULL;
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
prev->next = NULL;
}
}在表尾删除数据时有三种情况，当单链表为空的时候return结束函数，当单链表只有一个数据时直接释放表头指向的空间，当有多个数据的时候才开始正式执行逻辑。我们再创建两个结构体指针prev和tail，用tail来寻找tail当前所在结构的next是不是NULL，因为prev永远指向的都比tail指向的结构前一位，所以当tail位置不再递推就表明已经到了最后一个数据位置。找到最后一个结构之后free掉tail，即释放了最后一个数据的空间，使它和链表切除联系。释放空间后prev的next指向的地址就变成了野指针（定义在下文讲解），所以将prev的next设置为NULL，完成了删除最后一个数据的最后步骤。
野指针：
- 指针变量未初始化：如果指针变量没有被初始化，它会包含一个随机的值，可能是一个未知的内存地址。
- 指针变量指向已经释放的内存：如果指针变量指向的内存已经被释放（通过free或delete操作），那么该指针就会变成野指针。
- 指针操作超出作用域：如果一个指针变量在其所指向的对象被销毁之后仍然被使用，那么该指针就会成为野指针。
· 查找数据
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
SListNode* cur = phead;
//while (cur != NULL)
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}- 参数
phead是一个指向SLTNode类型的指针，这是一个自定义的数据结构，表示单链表的头节点。 - 参数
x是一个SLTDataType类型的变量，它表示要查找的值。
函数内部使用了一个指针cur来遍历单链表。首先，将cur指向头节点phead。然后，使用一个while循环来遍历整个链表。在循环中，每次检查当前节点cur的值是否等于要查找的值x。如果相等，就返回当前节点的指针；如果不相等，就将cur指向下一个节点。如果遍历完整个链表都没有找到要查找的值，函数返回NULL。如此便完成查找数据的操作，返回数据所在地址。
· 指定位置前插入数据
// 在pos的前面插入x
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
if (pos == *pphead)
{
SListPushFront(pphead, x);
}
else
{
SLTNode* newnode = BuySListNode(x);
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = newnode;
newnode->next = pos;
}
}- 参数
pphead是一个指向SLTNode类型的指针的指针，这是一个双重指针，用于间接操作链表的头节点。 - 参数
pos是一个指向SLTNode类型的指针，它表示要插入节点的位置。 - 参数
x是一个SLTDataType类型的变量，它表示要插入的值
该函数分为两个情况，一种是在表头插入，一种是在其他地方插入。表头的话我们可以直接用上面的函数SListPushFront，其他地方的话先创建一个结构体指针指向新数据的空间，再通过创建的结构体指针prev来寻找到pos对应的前一个数据，然后用找到的prev的next指向插入新数据的地址，再将新数据的next指向pos的地址，完成连接。
· 删除指定位置的数据
// 删除pos位置的值
void SListErase(SLTNode** pphead, SLTNode* pos)
{
if (pos == *pphead)
{
SListPopFront(pphead);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
}
}当pos为当前头结点的时候用头删函数SListPopFront直接操作达到目的。其他情况下与插入数据中的方法相同，用prev寻找pos前的数据，然后用prev的next指向pos的next，也就是指向了pos的下一个数据，然后将pos空间释放掉，完成操作。
整体示例代码呈现
#include "SList.h"
void SListPrint(SLTNode* phead)
{
SLTNode* cur = phead;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
SLTNode* BuySListNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
newnode->data = x;
newnode->next = NULL;
return newnode;
}
void SListPushBack(SLTNode** pphead, SLTDataType x)
{
SLTNode* newnode = BuySListNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
// 找尾节点的指针
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
// 尾节点，链接新节点
tail->next = newnode;
}
}
void SListPushFront(SLTNode** pphead, SLTDataType x)
{
SLTNode* newnode = BuySListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
void SListPopFront(SLTNode** pphead)
{
SLTNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}
void SListPopBack(SLTNode** pphead)
{
// 1、空
// 2、一个节点
// 3、一个以上的节点
if (*pphead == NULL)
{
return;
}
else if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SLTNode* prev = NULL;
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
prev->next = NULL;
}
}
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
SListNode* cur = phead;
//while (cur != NULL)
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
// 在pos的前面插入x
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
if (pos == *pphead)
{
SListPushFront(pphead, x);
}
else
{
SLTNode* newnode = BuySListNode(x);
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = newnode;
newnode->next = pos;
}
}
// 删除pos位置的值
void SListErase(SLTNode** pphead, SLTNode* pos)
{
if (pos == *pphead)
{
SListPopFront(pphead);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
}
}