本篇博客将用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); } }
以上就是本篇博客的全部内容了，感谢您的阅读！
