【数据结构】链表详解

大家好，今天为大家分享一下第二个数据结构——单链表
先打个广告：这里是博主写道顺序表，大家也可以查看：顺序表详解
首先：

我们学完顺序表的时候，我们发现有以下问题：
中间/头部的插入删除，时间复杂度为O(N)
增容需要申请新空间，拷贝数据，释放旧空间、消耗大量资源。
增容一般是2倍的增长，势必会有一定的空间浪费。例如当前容量为300，满了以后增容到600，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了295个数据空间。

链表就能够很好的解决这些问题！

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

单链表模样如下：

博主分享的链表接口如下：

typedef int SLTDataType;//存储的数据类型
typedef struct SListNode {SLTDataType data;struct SListNode* next;
}SLTNode;//打印链表
void SListPrint(SLTNode* phead);
//创建节点
SLTNode* BuySListNode(SLTDataType x);
//尾插
void SListPushBack(SLTNode** phead, SLTDataType x);
//头插
void SListPushFront(SLTNode** phead, SLTDataType x);
//尾删
void SListPopBack(SLTNode** phead);
//头删
void SListPopFront(SLTNode** phead);
//查找
SLTNode* SListFind(SLTNode* phead, SLTDataType x);
//在pos位置之前插入
void SListInsert(SLTNode** phead, SLTNode* pos, SLTDataType x);
//删除pos位置
void SListErase(SLTNode** phead, SLTNode* pos);
//在pos位置之后插入
void SListInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos之后的位置
void SListEraseAfter(SLTNode* pos);

下面对每个接口的实现进行说明：

1、创建新节点的接口函数

SLTNode* BuySListNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));//出这个函数newnode被销毁，但是它保存的地址空间是malloc出来的，不会销毁assert(newnode);newnode->data = x;newnode->next = NULL;return newnode;
}

assert断言检查一下，如果申请失败就报错提示，申请成功就返回创建的节点的地址

2、打印数据函数的实现

void SListPrint(SLTNode* phead)
{SLTNode* cur = phead;while (cur!= NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}

定义一个指针cur指向头结点，使用这个指针循环遍历，这个指针指向的不为空的话就继续循环，在循环中打印cur->data，对应的操作是printf(“%d->”, cur->data);打印%d后面加->是为了方便观察;然后将cur指针移动到下一个结点的位置对应操作是cur = cur->next;，继续打印，直到cur为空打印完毕！

3、尾插函数的实现

void SListPushBack(SLTNode** phead, SLTDataType x)
{//需要传入头节点，以供寻找尾结点从而进行尾插SLTNode* newnode = BuySListNode(x);//创造新结点assert(phead);//就算链表为空，但是他的地址不能为空呀if (*phead == NULL){*phead = newnode;}else {SLTNode* tail = *phead;//循环找尾节点while (tail->next != NULL){tail = tail->next;}//找到当下最后一个节点后让它指向插入的这个节点tail->next = newnode;}
}

4、头插函数的实现

void SListPushFront(SLTNode** phead, SLTDataType x)
{assert(phead);//就算链表为空，但是他的地址不能为空呀SLTNode* newnode = BuySListNode(x);//创造新结点newnode->next = *phead;*phead = newnode;
}

将创建的新结点的地址存放在newnode指针变量中，pphead为原先头结点的地址，头插一个新结点后，应该将新结点的next存放原先头结点的地址，对应操作为newnode->next = pphead;然后保存在pphead应该为新的头结点的地址，也就是newnode所指向的地址，对应操作为pphead = newnode;

5、尾删函数的实现

void SListPopBack(SLTNode** phead)
{//if (*phead == NULL)//温柔的检查//{//	return;//}assert(phead);//就算链表为空，但是他的地址不能为空呀assert(*phead!=NULL);//暴力检查if ((*phead)->next == NULL)//如果只有一个节点{free(*phead);*phead = NULL;//                            要改变phead,就需要二级指针}else//如果有多个结点{SLTNode* tailPrev = *phead;SLTNode* tail = *phead;//循环找尾节点while (tail->next != NULL){tailPrev = tail;tail = tail->next;}free(tail);tailPrev->next = NULL;}}

先创建两个指针，一个tail,一个tailprev,便利一遍链表，tail保存最后一个节点，tailprev保存最后一个节点的前一个节点，free掉tail,将tailprev的next指向NULL，就完成了尾删
如果只有一个节点，则释放后要通过对二级指针解引用将其置为空

6、头删函数的实现

void SListPopFront(SLTNode** phead)//                    要改变phead,就需要二级指针
{assert(*phead!=NULL);//链表为空就不能删除呀assert(phead);//就算链表为空，但是他的地址不能为空呀//if (*phead == NULL)//温柔的检查//{//	return;//}SLTNode* Next = (*phead)->next;free(*phead);*phead = Next;
}

提前保存好头节点的next值，删除后将头节点变为保存的next

7、查找函数的实现

SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur = phead;while (cur){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}

遍历一遍链表，哪个节点的数据和要求的数据相同，则返回该节点

8、任意位置插入节点函数的实现

void SListInsert(SLTNode** phead, SLTNode* pos, SLTDataType x)
{assert(pos);//插入位置 传 错，为空就报错assert(*phead);assert(phead);//就算链表为空，但是他的地址不能为空呀if (pos == *phead){SListPushFront(phead, x);//头插}else{SLTNode* prev = *phead;while (prev->next !=pos){prev = prev->next;}SLTNode* newnode = BuySListNode(x);prev->next = newnode;newnode->next = pos;}
}

这个函数写出来之后就可以利用他对前面所写的头插和尾插进行改写了，大佬们可以尝试一下呀

9、删除节点函数的实现

void SListErase(SLTNode** phead, SLTNode* pos)
{assert(pos);//插入位置 传 错，为空就报错assert(*phead);assert(phead);//就算链表为空，但是他的地址不能为空呀if (pos == *phead){SListPopFront(phead);}else{SLTNode* prev = *phead;while (prev->next!= pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;//可有可无}
}

这个函数写出来之后就可以利用他对前面所写的头删和尾删进行改写了，大佬们可以尝试一下呀

下面是完整的代码：

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int SLTDataType;
typedef struct SListNode {SLTDataType data;struct SListNode* next;
}SLTNode;//打印链表
void SListPrint(SLTNode* phead);
//创建节点
SLTNode* BuySListNode(SLTDataType x);
//尾插
void SListPushBack(SLTNode** phead, SLTDataType x);
//头插
void SListPushFront(SLTNode** phead, SLTDataType x);
//尾删
void SListPopBack(SLTNode** phead);
//头删
void SListPopFront(SLTNode** phead);
//查找
SLTNode* SListFind(SLTNode* phead, SLTDataType x);
//在pos位置之前插入
void SListInsert(SLTNode** phead, SLTNode* pos, SLTDataType x);
//删除pos位置
void SListErase(SLTNode** phead, SLTNode* pos);
//在pos位置之后插入
void SListInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos之后的位置
void SListEraseAfter(SLTNode* pos);

#define _CRT_SECURE_NO_WARNINGS 1
#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被销毁，但是它保存的地址空间是malloc出来的，不会销毁assert(newnode);newnode->data = x;newnode->next = NULL;return newnode;
}void SListPushBack(SLTNode** phead, SLTDataType x)
{//需要传入头节点，以供寻找尾结点从而进行尾插SLTNode* newnode = BuySListNode(x);//创造新结点assert(phead);//就算链表为空，但是他的地址不能为空呀if (*phead == NULL){*phead = newnode;}else {SLTNode* tail = *phead;//循环找尾节点while (tail->next != NULL){tail = tail->next;}//找到当下最后一个节点后让它指向插入的这个节点tail->next = newnode;}
}void SListPushFront(SLTNode** phead, SLTDataType x)
{assert(phead);//就算链表为空，但是他的地址不能为空呀SLTNode* newnode = BuySListNode(x);//创造新结点newnode->next = *phead;*phead = newnode;}void SListPopBack(SLTNode** phead)
{//if (*phead == NULL)//温柔的检查//{//	return;//}assert(phead);//就算链表为空，但是他的地址不能为空呀assert(*phead!=NULL);//暴力检查if ((*phead)->next == NULL)//如果只有一个节点{free(*phead);*phead = NULL;//                            要改变phead,就需要二级指针}else//如果有多个结点{SLTNode* tailPrev = *phead;SLTNode* tail = *phead;//循环找尾节点while (tail->next != NULL){tailPrev = tail;tail = tail->next;}free(tail);tailPrev->next = NULL;}}void SListPopFront(SLTNode** phead)//                    要改变phead,就需要二级指针
{assert(*phead!=NULL);//链表为空就不能删除呀assert(phead);//就算链表为空，但是他的地址不能为空呀//if (*phead == NULL)//温柔的检查//{//	return;//}SLTNode* Next = (*phead)->next;free(*phead);*phead = Next;
}SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur = phead;while (cur){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}void SListInsert(SLTNode** phead, SLTNode* pos, SLTDataType x)
{assert(pos);//插入位置 传 错，为空就报错assert(*phead);assert(phead);//就算链表为空，但是他的地址不能为空呀if (pos == *phead){SListPushFront(phead, x);//头插}else{SLTNode* prev = *phead;while (prev->next !=pos){prev = prev->next;}SLTNode* newnode = BuySListNode(x);prev->next = newnode;newnode->next = pos;}
}void SListErase(SLTNode** phead, SLTNode* pos)
{assert(pos);//插入位置 传 错，为空就报错assert(*phead);assert(phead);//就算链表为空，但是他的地址不能为空呀if (pos == *phead){SListPopFront(phead);}else{SLTNode* prev = *phead;while (prev->next!= pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;//可有可无}
}void SListInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = BuySListNode(x);newnode->next = pos->next;//这两句的顺序一定要区分好pos->next = newnode;}void SListEraseAfter(SLTNode* pos)
{assert(pos);if (pos->next == NULL){return;}else{SLTNode* del = pos->next;pos->next = del->next;free(del);del = NULL;//可有可无}
}

单链表分享到这里就完了，大家可以参考，有不正确的地方还请指教，谢谢！！！