目录
- 一. 节点声明
- 二. 尾插
- 三. 链表打印
- 四. 头插
- 五. 尾删
- 六. 头删
- 七. 查找值
- 八.指定插入
- 九.指定删除
- 十.销毁链表
一. 节点声明
链表是一种数据结构，用于数据的存储。
如图，每一个链表节点所在的内存空间是不延续的，因为不是连续存储，所以需要存入下一个节点的地址，这样方便找到下一个数值，而最后一个链表指向的空间为NULL，因此我们可以声明一个结构体，代表一个节点。
typedef int ListDataType;
typedef struct SListNode
{
ListDataType data;
struct SListNode* Next;
}SLNode;
SListNode 是我们的节点结构体，ListDataType是存储数据的类型。
二. 尾插
链表的节点建立好后，接下来我们来进行尾部插入数据。
那么我们只需要找到尾部节点，把尾部节点指向的NULL值置为新节点。新节点指向NULL
因此我们要新建一个节点，然后找到最后一个节点。
void SListPushBack(SLNode** phead, ListDataType x)
{
//新开辟一个节点
SLNode* newNode = (SLNode*)malloc(sizeof(SLNode));
if (newNode == NULL)
{
//空间开辟失败
printf("SListPushBack::newNode");
exit(-1);
}
//找到最后一个节点
SLNode* cru = *phead;
//如果cru指向NULL，说明cru是最后一个节点
while (cru->Next != NULL)
{
cru = cru->Next;
}
//cru 指向新节点
cru->Next = newNode;
//新节点指向NULL，存储数据x
newNode->data = x;
newNode->Next = NULL;
}
但是这种方法，我们需要注意一种情况，那就是如果链表中本身没有节点，那么cru初始就是一个空指针，而循环条件我们对空指针进行了解引用，所以我们需要判断一下。
//尾部数据插入
void SListPushBack(SLNode** phead, ListDataType x)
{
//新开辟一个节点
SLNode* newNode = (SLNode*)malloc(sizeof(SLNode));
if (newNode == NULL)
{
//空间开辟失败
printf("SListPushBack::newNode");
exit(-1);
}
//新节点指向NULL，存储数据x
newNode->data = x;
newNode->Next = NULL;
if (*phead == NULL)
{
//当前链表为空，那么我直接让新节点替代phead
*phead = newNode;
return;
}
//找到最后一个节点
SLNode* cru = *phead;
//如果cru指向NULL，说明cru是最后一个节点
while (cru->Next != NULL)
{
cru = cru->Next;
}
//cru 指向新节点
cru->Next = newNode;
}
然后我们测试一下，发现链表已经链接起来了
三. 链表打印
为了方便后面测试，我们决定先实现打印链表的函数。我们只需要依次查找节点指向的元素，直到最后一个指向NULL时，我们停下来。
//链表打印
void SListPrint(SLNode* head)
{
SLNode* cru = head;
while (cru)
{
printf("%d->",cru->data);
cru = cru->Next;
}
printf("NULL\n");
}
四. 头插
头部插入和尾部插入差不多，我们只需要把新节点指向链表中的第一个节点，然后把头节点换成新节点。
因为我们尾插的时候创建了节点，头插又创建节点，太麻烦了，所以我们把创建节点封装成一个函数。
//创建节点
SLNode* SListCreateNode(ListDataType x)
{
//新开辟一个节点
SLNode* newNode = (SLNode*)malloc(sizeof(SLNode));
if (newNode == NULL)
{
//空间开辟失败
printf("SListPushBack::newNode");
exit(-1);
}
//新节点指向NULL，存储数据x
newNode->data = x;
newNode->Next = NULL;
return newNode;
}
尾插函数调整
//尾部数据插入
void SListPushBack(SLNode** phead, ListDataType x)
{
SLNode* newNode = SListCreateNode(x);
if (*phead == NULL)
{
//当前链表为空，那么我直接让新节点替代phead
*phead = newNode;
return;
}
//找到最后一个节点
SLNode* cru = *phead;
//如果cru指向NULL，说明cru是最后一个节点
while (cru->Next != NULL)
{
cru = cru->Next;
}
//cru 指向新节点
cru->Next = newNode;
}
头插函数
//头部数据插入
void SListPushFront(SLNode** phead, ListDataType x)
{
//新建节点
SLNode* newNode = SListCreateNode(x);
//让节点指向头
newNode->Next = *phead;
//头节点更替为新节点
*phead = newNode;
}
头插测试
五. 尾删
尾删也就是删除链表中的最后一个节点。那么我们需要找到最后一个节点，把它释放，并且要把它的前一个节点置为空指针，否则它会变成一个野指针。
//尾部数据删除
void SListPopBack(SLNode** phead)
{
SLNode* cru = *phead; //最后一个节点
SLNode* prve = NULL; //前一个节点
//最后一个节点指向空
while (cru->Next)
{
prve = cru;
cru = cru->Next;
}
//cru 为最后一个节点。释放掉
free(cru);
//前一个节点指向空
prve->Next = NULL;
}
但是这个尾删是建立在有数据的情况下的，如果没有数据我们进行此操作，那会造成空指针prve访问，所以我们在前面要断言一下
void SListPopBack(SLNode** phead)
{
//链表为空无法删除
assert(*phead);
SLNode* cru = *phead; //最后一个节点
SLNode* prve = NULL; //前一个节点
//最后一个节点指向空
while (cru->Next)
{
prve = cru;
cru = cru->Next;
}
//cru 为最后一个节点。释放掉
free(cru);
//前一个节点指向空
prve->Next = NULL;
}
即使这样，以上代码依然有问题，因为当链表只有一个节点时，并不会进入while循环，也就导致 prve对空指针解引用，所以我们还需要判断一下，如果链表只有一个节点，那么就直接释放头节点。
//尾部数据删除
void SListPopBack(SLNode** phead)
{
//链表为空无法删除
assert(*phead);
//只有一个节点时
if((*phead)->Next == NULL)
{
//释放头空间
free(*phead);
//置为空指针
*phead = NULL;
return;
}
SLNode* cru = *phead; //最后一个节点
SLNode* prve = NULL; //前一个节点
//找到最后一个节点
while (cru->Next)
{
prve = cru;
cru = cru->Next;
}
//cru 为最后一个节点。释放掉
free(cru);
//前一个节点指向空
prve->Next = NULL;
}
代码测试
六. 头删
尾删都会了，头删还远吗？头删我们只需要把头节点指向的空间释放，然后让头节点的指针指向下一个节点。
当然，如果链表为空，我们是无法操作的，我们也要断言或者if判断一下。
//头部数据删除
void SListPopFront(SLNode** phead)
{
//断言
assert(*phead);
//链表不为空，存储下一个位置的地址
SLNode* NextNode = (*phead)->Next;
//释放 *phead
free(*phead);
//存储的节点给*phead
*phead = NextNode;
}
测试一下代码
七. 查找值
在链表里查找值，我们只需要找节点，如果与找的值相等，就返回当前下标或者节点，这里我们用返回节点演示。
SLNode* SListFindNode(SLNode* head, ListDataType x)
{
SLNode* cru = head;
//查找值
while (cru)
{
//如果当前节点等于要查找的值
if (cru->data == x)
{
//返回当前节点，也可以返回下标，把函数返回值改成int
return cru;
}
//下一个节点
cru = cru->Next;
}
//遍历完没有找到， 返回空指针
return NULL;
}
看看测试结果
链表里我们插入了三个值，1，2，3。然后找1的值并返回当前节点，最终提示我们找到了。
当然，也可以用返回下标的方式，然后利用下标控制查找次数。
八.指定插入
指定插入，我们这里来演示前插，也就是在一个节点的前面进行插入，我们只需要把这个节点前面的节点指向新节点，然后新节点指向这个节点。
所以我们要先创建一个节点，让被插入节点之前的节点指向该节点，让新节点指向被插入的节点。
//指定插入
void SListInsert(SLNode** phead, SLNode* pos, ListDataType x)
{
//首先插入之前，我们必须保证被插入的pos节点存在，不然无法插入
assert(pos);
SLNode* cru = *phead; //用来查找被插入的节点
//查找pos节点
while (cru->Next != pos)
{
cru = cru->Next;
}
//找到后，创建一个新节点
SLNode* newNode = SListCreateNode(x);
//新节点指向pos
newNode->Next = pos;
//pos的前一个节点指向cru
cru->Next = newNode;
}
此时这个代码仍有问题，因为如果 pos是第一个节点时，cru->next无法判断判断第一个节点，所以我们要加个判断，如果是头节点，直接调用头插函数。
//指定插入
void SListInsert(SLNode** phead, SLNode* pos, ListDataType x)
{
//首先插入之前，我们必须保证被插入的pos节点存在，不然无法插入
assert(pos);
//头节点就是pos
if (*phead == pos)
{
//调用头插
SListPushFront(phead,x);
return 0;
}
SLNode* cru = *phead; //用来查找被插入的节点
//查找pos节点
while (cru->Next != pos)
{
cru = cru->Next;
}
//找到后，创建一个新节点
SLNode* newNode = SListCreateNode(x);
//新节点指向pos
newNode->Next = pos;
//pos的前一个节点指向cru
cru->Next = newNode;
}
代码测试
九.指定删除
指定删除和指定插入差不多，我们只需要把被删除节点的前一个节点，指向后一个节点，然后删除节点。如果要删除的是头节点，直接调用头删函数，或者也可以再次写一个头删。
//指定节点删除
void SListEase(SLNode** phead, SLNode* pos)
{
//pos是空指针，干掉程序
assert(pos);
//如果头节点与pos相等，直接调用头删
if (*phead == pos)
{
SListPopFront(phead);
return;
}
//创建一个节点
SLNode* cru = *phead; //查找被删除节点的前一个节点
while (cru->Next != pos)
{
cru = cru->Next;
}
//cru指向 pos 后的位置
cru->Next = pos->Next;
//释放pos所在空间
free(pos);
pos = NULL;
}
代码测试
十.销毁链表
如果这个链表不想用了，我们想要清空链表。那我们只需要把依次释放内存。
//销毁链表
void SListDestroy(SLNode** phead)
{
SLNode* cru = NULL;
while (*phead)
{
//存储下一个节点的地址
cru = (*phead)->Next;+
//当前地址置空
*phead = NULL;
//释放当前空间
free(*phead);
//换成下一个节点继续
*phead = cru;
}
}
然后我们测试一下，发现所有的节点都置空了
以上代码以上传至git，点这里获取
提供CDN加速