三月，你好，各位csdn uu们好

文章目录

  • 前言
  • 一、何为单链表
  • 二、单链表基本操作（增，删，查，改，销毁，遍历）
    • 1.查找与修改、销毁与遍历
    • 2.链表插入与删除操作
  • 三、单链表 VS 顺序表 且 全部 源码(SLNode.h ) (SLNode.c) ( test.c)

前言

由于上一篇博客顺序表的相关实现其基本操作中，它的查找效率很快，通过下标可以快速存取表中任意一个位置的元素，但是其插入和删除操作因为要移动大量的元素，造成效率极低，时间复杂度达到O（n)，那么能用上面结构来存储可以使其效率提高呢？因此在这里引入单链表，单链表的基本操作插入和删除效率喝高很高时间复杂度为O(n)，在以查找到节点的前提下.

一、何为单链表

链表 是一种在物理上非连续、 非顺序的数据结构， 由若干 节点 所组成，一个节点连着一个节点。
单链表顾名思义是链表的每一个节点又包含两部分， 一部分是存放数据的变量data， 另一部分是指向下一个节点的指针next。一个节点连着一个节点，每一个节点之间可以想象成有一条绳子拴起来，其实是上一个节点的next指针指向下一个节点，然后下一个的next指针又指向下一个。

线性表的单链表存储结构

typedef int SLDataType;typedef struct SLNode{SLDataType data;struct SLNode* next;}SLNode;

从这个结构中，可以知道节点由存放数据元素的数据域(data)和存放下一个节点地址的指针域(next)组成,假设phead是指向链表中第一个节点的指针，那么该节点的数据域可以用phead->data表示，该节点的指针域用phead->next表示，链表与顺序表按照下标来随机寻找元素不同，
对于链表的其中一个节点A， 只能根据节点A的next指针来找到该节点的下一个节点B， 再根据节点 B的next指针找到下一个节点C……
而链表中的第一个节点被称为头节点， 最后1个节点被称为尾节点， 尾节点的 next指针指向空。后文不用带哨兵位的头节点，哨兵位的头节点数据域里是没有元素。这里的头节点数据域里是有元素的，与哨兵位头节点不同，这里用phead这一结构体指针指向链表第一个节点，phead->next是指向头节点的下一个节点，其实是phead->next存着它下一个节点的地址，可以想象成第一个节点拿着一根绳子把第二个节点拴起来了。
单链表找下一个容易但是它找他的前一个十分困难，需要再回溯一遍，在数据结构中还有一中双向链表可以快速找到前一个元素，但是本文重点描述单链表实现

链表在内存中如何存储的？

接下来我们看一看链表的存储方式。 如果说顺在内存中的存储方式是顺序存储（一个挨着一个的存储）， 而链表在内存中的存储 方式则是随机存储（链表在内存中每一个节点存储在不同内存块中，而通过节点next指针链接下一个节点地址，依靠next指针这样连使每一个节点存在联系，使这些零星的空间链接起来）红色为顺序表顺序存储，绿色为链表随机存储

链表物理结构和逻辑结构
物理结构是在内存中真是存在的内存块，结构体指针phead指向第一个节点，然后第一个节点的next指针指向下一个节点地址。其实就是前一个节点的next存着下一个节点地址，这样下去直到链表为空
逻辑结构是想象中有一根线连着两个节点，箭头表示next指针

与顺序表一样，链表同样有增删查改基本操作，并且插入和删除同样有头、尾、任意位置操作。且还有销毁操作

二、单链表基本操作（增，删，查，改，销毁，遍历）

1.查找与修改、销毁与遍历

查找

在查找元素时， 链表不像数组那样可以通过下标快速进行定位， 只能从 头节点开始向后一个一个节点逐一查找，查找到就返回改节点，找不到则返回空，如pos为3,从以phead指针指向第一个节点，第一个节点数据域不为3，通过第一个节点next指针指向第二个，然后第三个，找到为止。链表中的数据只能按顺序进行访问， 最坏的时间复杂度是O(n) 。

//查找SLNode* SLNodeFind(SLNode* phead, SLDataType x){SLNode* cur = phead;while (cur != NULL){if (cur->data != x){cur = cur->next;}else{return cur;}}return NULL;}

不考虑查找节点的过程， 链表的更新过程会像数组那样简单， 直接 把旧数据替换成新数据即可。修改就是将找到的这一节点的数据域修改即可

代码如下

if (ret){//修改ret节点的值ret->data *= 2;}

链表销毁

销毁时注意释放上一个节点时要找到下一个节点地址，同时将该节点置空
代码实现如下

//销毁void SLNodeDestory(SLNode** pphead){assert(*pphead);SLNode* cur = *pphead;SLNode* next = NULL;while (cur->next != NULL){next = cur->next;free(cur);cur = next;}free(cur);cur = NULL;/*free(next);next = NULL;*/*pphead = NULL;}

链表遍历
直接上代码

//遍历void SLNodeprint(SLNode* phead){SLNode* cur = phead;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");}

2.链表插入与删除操作

插入三种情况

1、尾部插入 2、头部插入 3、中间插入

在插入之前先创建一个要插入的节点，开创新节点之后返回该节点地址，新节点数据域为x，指针域为空
代码如下

//创建一个新节点SLNode* BuyNewnode(SLDataType x){SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));if (newnode == NULL){perror("malloc fail");return NULL;}newnode->data = x;//1newnode->next = NULL;return newnode;}

尾插

尾部插入， 是最简单的情况， 把最后一个节点的next指针指向新插入的 节点即可。

代码如下

//尾插void SLNodePushBack(SLNode** pphead, SLDataType x){assert(pphead);SLNode* newnode = BuyNewnode(x);if (*pphead == NULL){*pphead = newnode;//1}else{SLNode* tail = *pphead;while (tail->next != NULL)//如果将判断改为cur != NULL,那么到最后一个节点时将NULL给cur，后面插入的时候就不能找到下一个节点，直接为空了{tail = tail->next;}tail->next = newnode;}}

头插
头部插入， 可以分成两步。

1、 把新节点的next指针指向原先的头节点。
2 、把新节点变为链表的头节点。

代码如下

//头插void SLNodePushFront(SLNode** pphead, SLDataType x){assert(pphead);SLNode* newnode = BuyNewnode(x);newnode->next = *pphead;*pphead = newnode;}

任意位置（pos)插入
任意位置插入， 同样分为两步。

1、 新节点的next指针， 指向插入位置的节点。
2、 插入位置前置节点的next指针， 指向新节点。

代码 如下

//pos前面插入void SLNodeInsert(SLNode** pphead, SLNode*pos,SLDataType x){assert(pphead);SLNode* newnode = BuyNewnode(x);SLNode* prev = *pphead;if (pos == *pphead){SLNodePushFront(pphead, x);//复用头插}else{while (prev->next != pos){prev = prev->next;}prev->next = newnode;newnode->next = pos;}}

链表插入只要内存空间允许， 能够插入链表的元素是无穷无尽的， 不需要像数组 那样考虑扩容的问题。

链表删除操作同样分为尾删、头删、任意位置(pos)删除
尾删

尾部删除， 是最简单的情况， 把倒数第2个节点的next指针指向空。

代码如下

//尾删void SLNodePopBack(SLNode** pphead){assert(pphead);assert(*pphead);if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLNode* tail = *pphead;SLNode* prev = NULL;while (tail->next != NULL){prev = tail;tail = tail->next;}free(tail);tail = NULL;prev->next = NULL;}}

头删

头部删除， 把链表的头节点设为原先头节点的next指针即 可。

代码如下

//头删void SLNodePopFront(SLNode** pphead){assert(pphead);assert(*pphead);SLNode* first = *pphead;*pphead = first->next;free(first);first = NULL;}

任意位置删除
任意位置删除，把要删除节点的前置节点的next指针 指向要 删除元素的下一个节点即可。

代码如下

//删除pos位置节点void SLNodeErase(SLNode** pphead, SLNode* pos){assert(pphead);if (*pphead == pos){*pphead = pos->next;free(pos);pos = NULL;//这里置空无意义，形参改变不会影响实参，在外面调用它的那个函数置空}else{SLNode* prev = *pphead;while (prev->next!=pos){prev = prev->next;}prev->next = pos->next;free(pos);}}

删除注意两点

1、链表删空
2、被删除的节点需要释放且置空

链表的插入和删除时间复杂度是多少嘞？
如果不考虑插入、 删除操作之前 查找元素的过程， 只考虑纯粹的插入和删除操作， 时间复杂度都 是O(1)

三、单链表 VS 顺序表 且 全部 源码(SLNode.h ) (SLNode.c) ( test.c)

那么思考一下顺序表和 链表都属于线性的数据结构， 用哪一个更好呢？ 顺序表和链表没有绝对的好与坏，顺序和 链表各有千秋。
对比一下顺序表和链表相关操作的性能。

从表格可以看出， 顺序表的优势在于能
够快速定位元素，就这一优势就特别如在有序且数据个数范围特别大时，用二分效率高。而链表的优势在于能够灵活地进行插入和删除操作。

SLNode.h

#include#include#includetypedef int SLDataType;typedef struct SLNode{SLDataType data;struct SLNode* next;}SLNode;//遍历打印void SLNodeprint(SLNode* phead);//尾插void SLNodePushBack(SLNode** pphead, SLDataType x);//尾删void SLNodePopBack(SLNode** pphead);//头插void SLNodePushFront(SLNode** pphead, SLDataType x);//头删void SLNodePopFront(SLNode** pphead);//销毁void SLNodeDestory(SLNode** pphead);//查找SLNode* SLNodeFind(SLNode* phead, SLDataType x);//在pos位置前插入void SLNodeInsert(SLNode** pphead, SLNode* pos, SLDataType x);//在pos位置后插入void SLNodeInsertAfter(SLNode** pphead, SLNode* pos, SLDataType x);//删除pos节点void SLNodeErase(SLNode** pphead, SLNode* pos);//节点pos后一个节点void SLNodePopAfter(SLNode** pphead, SLNode* pos);

SLNode.c

#include"SLNode.h"//遍历void SLNodeprint(SLNode* phead){SLNode* cur = phead;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");}//创建一个新节点SLNode* BuyNewnode(SLDataType x){SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));if (newnode == NULL){perror("malloc fail");return NULL;}newnode->data = x;//1newnode->next = NULL;return newnode;}//尾插void SLNodePushBack(SLNode** pphead, SLDataType x){assert(pphead);SLNode* newnode = BuyNewnode(x);if (*pphead == NULL){*pphead = newnode;//1}else{SLNode* tail = *pphead;while (tail->next != NULL)//如果将判断改为cur != NULL,那么到最后一个节点时将NULL给cur，后面插入的时候就不能找到下一个节点，直接为空了{tail = tail->next;}tail->next = newnode;}}//尾删void SLNodePopBack(SLNode** pphead){assert(pphead);assert(*pphead);if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLNode* tail = *pphead;SLNode* prev = NULL;while (tail->next != NULL){prev = tail;tail = tail->next;}free(tail);tail = NULL;prev->next = NULL;}}//头插void SLNodePushFront(SLNode** pphead, SLDataType x){assert(pphead);SLNode* newnode = BuyNewnode(x);newnode->next = *pphead;*pphead = newnode;}//头删void SLNodePopFront(SLNode** pphead){assert(pphead);assert(*pphead);SLNode* first = *pphead;*pphead = first->next;free(first);first = NULL;}//销毁void SLNodeDestory(SLNode** pphead){assert(*pphead);SLNode* cur = *pphead;SLNode* next = NULL;while (cur->next != NULL){next = cur->next;free(cur);cur = next;}free(cur);cur = NULL;/*free(next);next = NULL;*/*pphead = NULL;}//查找SLNode* SLNodeFind(SLNode* phead, SLDataType x){SLNode* cur = phead;while (cur != NULL){if (cur->data != x){cur = cur->next;}else{return cur;}}return NULL;}//pos前面插入void SLNodeInsert(SLNode** pphead, SLNode*pos,SLDataType x){assert(pphead);SLNode* newnode = BuyNewnode(x);SLNode* prev = *pphead;if (pos == *pphead){SLNodePushFront(pphead, x);}else{while (prev->next != pos){prev = prev->next;}prev->next = newnode;newnode->next = pos;}}//在pos位置后面插入xvoid SLNodeInsertAfter(SLNode** pphead, SLNode* pos, SLDataType x){SLNode* newnode = BuyNewnode(x);newnode->next = pos->next;pos->next = newnode;}//删除pos位置节点void SLNodeErase(SLNode** pphead, SLNode* pos){assert(pphead);if (*pphead == pos){*pphead = pos->next;free(pos);pos = NULL;//这里置空无意义，形参改变不会影响实参，在外面调用它的那个函数置空}else{SLNode* prev = *pphead;while (prev->next!=pos){prev = prev->next;}prev->next = pos->next;free(pos);}}//在pos位置之后删除void SLNodePopAfter(SLNode** pphead, SLNode* pos){assert(pos->next);SLNode* del = pos->next;pos->next = del->next;free(del);del = NULL;}

test.c

#include"SLNode.h"void test(){SLNode* plist = NULL;//尾插SLNodePushBack(&plist, 1);SLNodePushBack(&plist, 2);SLNodePushBack(&plist, 3);SLNodePushBack(&plist, 4);SLNodeprint(plist);//头插SLNodePushFront(&plist, 10);SLNodeprint(plist);SLNodeDestory(&plist);}void test1(){SLNode* plist = NULL;SLNodePushBack(&plist, 1);SLNodePushBack(&plist, 2);SLNodePushBack(&plist, 3);SLNodePushBack(&plist, 4);SLNodePushFront(&plist, 10);SLNodeprint(plist);//尾删SLNodePopBack(&plist);SLNodeprint(plist);SLNodePopBack(&plist);SLNodePopBack(&plist);/*SLNodePopBack(&plist);*///SLNodePopBack(&plist);SLNodeprint(plist);//头删SLNodePopFront(&plist);SLNodeprint(plist);SLNodePopFront(&plist);SLNodeprint(plist);SLNodePopFront(&plist);SLNodeprint(plist);SLNodeDestory(&plist);}void test2(){SLNode* plist = NULL;SLNodePushBack(&plist, 1);SLNodePushBack(&plist, 2);SLNodePushBack(&plist, 3);SLNodePushBack(&plist, 4);SLNodePushFront(&plist, 10);SLNodeprint(plist);//查找SLNode* ret = SLNodeFind(plist, 4);if (ret){//在ret位置前插入30SLNodeInsert(&plist, ret, 30);}SLNodeprint(plist);if (ret){//修改ret节点的值ret->data *= 2;}SLNodeprint(plist);if (ret){//在ret节点后面插入一个值为节点SLNodeInsertAfter(&plist, ret, 999);}SLNodeprint(plist);//if (ret)//{// //删除ret节点//SLNodeErase(&plist, ret);////ret = NULL;//}//SLNodeprint(plist);if (ret){//删除ret节点后面的那个节点SLNodePopAfter(&plist, ret);}SLNodeprint(plist);}int main(){//test();//test1();test2();return 0;}

注意:这篇文章是由c语言实现的，而从上文很多接口实现时可以发现，有**pphead，*phead，*plist为结构体指针初始化为空，后面在向链表中插入节点时，由于要改变链表内容，那么就需要将链表的地址传过去，在插入接口以二级指针指向链表地址，通过解引用就可以改变链表。这里插入一点传参问题，值传递：改变形参不可改变实参，地址传递：，改变形参可以改变实参。而断言assert(pphead)则是因为在插入时需要有链表才可以对链表进行操作，如果在SLNodePushBack()这个接口函数test()在传参时，传的是空地址，该接口就无法对链表进行操作。而在删除时同样如此，还需要断言链表内容是否为空，链表中是否有节点assert(*pphead)，链表为空就不能再删除了。如果不用断言判断，用if判断链表是否为空的话，如果代码太多，一时间看不出哪里出的问题，还需要通过调试才能发现，而用断言则能给你报一些基础的错误，这时会发觉断言真好用。

迎来了三月