🧑💻作者： @情话0.0
📝专栏：《数据结构》
👦个人简介：一名双非编程菜鸟，在这里分享自己的编程学习笔记，欢迎大家的指正与点赞，谢谢！
前言
顺序表可以随时存取表中的任意一个元素，它的存储位置可以用一个简单直观的公式表示，但是插入和删除操作需要移动大量元素。链式存储线性表时，不需要使用地址连续的存储单元，即不要求逻辑上相邻的元素在物理位置上也相邻，它通过“链”建立起数据元素之间的逻辑关系，因此插入和删除操作不需要移动元素，而只需要修改指针，但也会失去顺序表可随机存取的优点。
一、单链表的定义
线性表的链式存储又称为单链表，它是通过一组任意的存储单元来存储线性表表中的数据元素。为了建立数据元素之间的线性关系，对每个链表节点，除存放元素本身的信息外，还需要存放一个指向其后继的指针。单链表的结构如下图所示，其中data为数据域，存放数据元素；next为指针域，存放其后继节点的地址。
利用单链表可以解决顺序表需要大量连续存储单元的缺点，但单链表附加指针域，也存在浪费存储空间的缺点。由于单链表的元素离散地分布在存储空间中，所以单链表时非随机存取的存储结构，即不能直接找到表中某个特定的结点。查找某个特定的借点时，需要从头开始遍历，依次查找。
下图为一个带头结点的单链表，头指针pList，它指向的是头结点，除最后一个节点外，它们的next都指向下一个点的地址，对于最后一个节点的next指向NULL。
从上图可以看出，链式结构在逻辑上是连续的，但在物理上不一定连续。
链表中的结点一般都是从堆上申请的。
从堆上申请的空间是按照一定的策略来分配的，两次申请的空间有可能连续，有可能不连续。
头节点和头指针的区分： 不管带不带头节点，头指针都始终指向链表的第一个节点，而头节点是带头结点的链表的第一个结点，结点内通常不存储信息。
二、单链表上基本操作的实现（不带头结点）
单链表中结点类型的描述如下：
typedef int SLTDateType;
typedef struct SListNode
{
SLTDateType data;
struct SListNode* next;
}SListNode;
1. 动态申请一个节点
对于插入操作来说，需要先动态申请一个结点，并将该结点的数值域与指针域进行赋值，指针域都设置为
NULL。
SListNode* BuySListNode(SLTDateType data)
{
SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));
if (newNode == NULL)
{
return NULL;
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}
2. 单链表尾插
在进行尾插操作时，要考虑到的一点就是在插入该结点之前此单链表是否为空，为空时则直接将该结点设置为头结点就行，若不为空就循环遍历找到最后一个结点进行尾插就行。
还有一点最为重要，就是在进行函数传参时，第一个参数为二级指针，这是为什么呢？首先定义一个头指针，它是用来指向链表第一个节点，当你以一级指针进行传参时，那么在该函数内得到头指针是一份临时拷贝，所以对该指针的临时拷贝进行操作时就不会出现想要得到的效果，所以说，凡是有关头指针的操作就是传二级指针，对于后续结点的插入其实可以传递一级指针，因为所要改变的不是头指针，而是结点这个结构体。我感觉吧，可以把该链表想象为一个双头蛇，一个头为另一个头的拷贝，当你对那个拷贝的头操作后并不会影响另外一个头，但是对于后续节点来说就可以比作为蛇的身子。
void SListPushBack(SListNode** Head, SLTDateType data)
{
assert(Head);
SListNode* newNode = BuySListNode(data); //创建一个值为data的结点
if (*Head == NULL)
{
*Head = newNode;
}
else
{
SListNode* cur = *Head;
while (cur->next)
{
cur = cur->next;
}
cur->next = newNode;
}
}
3. 单链表尾删
在尾删时同样也要传递二级指针，有可能该链表只有一个结点。
void SListPopBack(SListNode** Head)
{
if (*Head == NULL) //链表为空
{
return;
}
else if ((*Head)->next == NULL) //链表只有一个结点
{
*Head = NULL;
}
else //链表中有多个结点
{
SListNode* cur = (*Head)->next;
SListNode* prev = *Head; //prev为前序指针
while (cur->next)
{
cur = cur->next;
prev = prev->next;
}
//在循环退出后，prev指针指向倒数第二个结点
prev->next = NULL;
free(cur);
}
}
4. 单链表头插
void SListPushFront(SListNode** Head, SLTDateType data)
{
assert(Head);
SListNode* newNode = BuySListNode(data); //创建一个值为data的结点
newNode->next = *Head;
*Head = newNode;
}
5. 单链表头删
void SListPopFront(SListNode** Head)
{
if (*Head == NULL) //链表为空
{
return;
}
else
{
SListNode* cur = *Head;
*Head = (*Head)->next;
free(cur);
}
}
6. 单链表查找
此函数旨在查找元素，并不会去修改头指针的指向，所以传一级指针即可。
SListNode* SListFind(SListNode* Head, SLTDateType data)
{
assert(Head);
while (Head)
{
if (Head->data == data)
{
return Head;
}
Head = Head->next;
}
return NULL; //没有找到就返回NULL
}
7. 单链表在pos位置之后插入data
该操作是在pos位置之后进行插入（该pos位置通过查找函数获取），当然也可以在pos位置之前插入，不同的是只需改变查找函数即可，让查找函数返回pos位置的前一个结点指针。
因为不管任意位置插入还是删除都在pos位置之后，所以并不会涉及到头指针，因此不需要传递二级指针。若是pos位置之前插入删除则需要考虑有可能涉及到头指针指向位置的改变。
void SListInsertAfter(SListNode* pos, SLTDateType data)
{
SListNode* newNode = BuySListNode(data);
if (NULL == pos)
return;
newNode->next = pos->next; //这里的两行代码顺序不能乱，因为会导致pos之后的结点找不到
pos->next = newNode;
}
8. 单链表删除pos位置之后的值
void SListDelAfter(SListNode* pos)
{
SListNode* newNode = NULL;
if (NULL == pos || NULL == pos->next)
return;
newNode = pos->next; //同样，此处代码不能乱
pos->next = newNode->next;
free(newNode);
}
三、源代码及运行结果展示
1. SList.h
结构体创建及函数声明
#include <malloc.h>
#include <stdio.h>
#include <assert.h>
typedef int SLTDateType;
typedef struct SListNode
{
SLTDateType data;
struct SListNode* next;
}SListNode;
SListNode* BuySListNode(SLTDateType data);
void SListPrint(SListNode* Head);
void SListPushBack(SListNode** Head, SLTDateType data);
void SListPushFront(SListNode** Head, SLTDateType data);
void SListPopBack(SListNode** Head);
void SListPopFront(SListNode** Head);
SListNode* SListFind(SListNode* Head, SLTDateType data);
void SListInsertAfter(SListNode* pos, SLTDateType data);
void SListTest();
2. SList.c
方法实现
#include "SList.h"
SListNode* BuySListNode(SLTDateType data)
{
SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));
if (newNode == NULL)
{
return NULL;
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}
void SListPushBack(SListNode** Head, SLTDateType data)
{
assert(Head);
SListNode* newNode = BuySListNode(data);
if (*Head == NULL)
{
*Head = newNode;
}
else
{
SListNode* cur = *Head;
while (cur->next)
{
cur = cur->next;
}
cur->next = newNode;
}
}
void SListPushFront(SListNode** Head, SLTDateType data)
{
assert(Head);
SListNode* newNode = BuySListNode(data);
newNode->next = *Head;
*Head = newNode;
}
void SListPopBack(SListNode** Head)
{
if (*Head == NULL)
{
return;
}
else if ((*Head)->next == NULL)
{
*Head = NULL;
}
else
{
SListNode* cur = (*Head)->next;
SListNode* prev = *Head;
while (cur->next)
{
cur = cur->next;
prev = prev->next;
}
prev->next = NULL;
free(cur);
}
}
void SListPopFront(SListNode** Head)
{
if (*Head == NULL)
{
return;
}
else
{
SListNode* cur = *Head;
*Head = (*Head)->next;
free(cur);
}
}
SListNode* SListFind(SListNode* Head, SLTDateType data)
{
assert(Head);
while (Head)
{
if (Head->data == data)
{
return Head;
}
Head = Head->next;
}
return NULL;
}
void SListInsertAfter(SListNode* pos, SLTDateType data)
{
SListNode* newNode = BuySListNode(data);
if (NULL == pos)
return;
newNode->next = pos->next;
pos->next = newNode;
}
void SListDelAfter(SListNode* pos)
{
SListNode* newNode = NULL;
if (NULL == pos || NULL == pos->next)
return;
newNode = pos->next;
pos->next = newNode->next;
free(newNode);
}
void SListPrint(SListNode* Head)
{
SListNode* cur = Head;
while (cur)
{
printf("%d---->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
void SListTest()
{
SListNode* ListNode = NULL;
SListPushFront(&ListNode, 0);
SListPushBack(&ListNode, 1);
SListPushBack(&ListNode, 2);
SListPushBack(&ListNode, 3);
SListPushBack(&ListNode, 4);
SListPushBack(&ListNode, 5);
SListPrint(ListNode);
SListPushFront(&ListNode, -1);
SListPrint(ListNode);
SListPopBack(&ListNode);
SListPopBack(&ListNode);
SListPrint(ListNode);
SListPopFront(&ListNode);
SListPrint(ListNode);
SListNode* ret = SListFind(ListNode, 0);
if (ret == NULL)
{
printf("没找到\n");
}
else
{
printf("找到了\n");
}
SListInsertAfter(SListFind(ListNode, 2), 0);
SListPrint(ListNode);
SListDelAfter(SListFind(ListNode, 2));
SListPrint(ListNode);
}
3. test.c
主函数
#include "SList.h"
int main()
{
SListTest();
return 0;
}
结果展示：
总结
对于链表来说有着自己的特点，比如：在内存中不需要连续的地址进行存储，元素之间通过指针相连、逻辑相邻但物理上并不一定相邻，插入与删除操作不需要移动大量的元素，但是无法随机存取，只能从头遍历。而对于不带头结点的单链表来说，尤其要注意对头指针的指向修改时要使用二级指针。
文章若有不足的地方还请大佬指正！！！文章来源：https://www.toymoban.com/news/detail-826295.html
文章来源地址https://www.toymoban.com/news/detail-826295.html
到了这里，关于【数据结构】单链表——单链表的定义及基本操作的实现（头插、尾插、头删、尾删、任意位置的插入与删除）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
