【数据结构】手撕单链表

目录

前言

1 链表

1.1 链表的概念及结构

1.2 链表的分类

1.2.1 单向或者双向

1.2.2 带头或者不带头

1.2.3 循环或者非循环

1.2.4 无头单向非循环链表

1.2.5 带头双向循环链表

2 链表的实现

2.1 结构

2.2 结点的创建

2.3 尾插

2.4 头插

2.5 尾删

2.6 头删

2.7 查找

2.8 在pos位置之前插入数据

2.9 删除pos位置

2.10 在pos位置之后插入数据

2.11 删除pos位置之后的数据

2.12 打印数据

2.13 销毁数据

---

🎈个人主页：库库的里昂 🎐C/C++领域新星创作者 🎉欢迎 👍点赞✍评论⭐收藏✨收录专栏：数据结构与算法🤝希望作者的文章能对你有所帮助，有不足的地方请在评论区留言指正，大家一起学习交流！🤗 前言

上一次我们分享了线性表中的一种结构顺序表，它存在着一些其缺点，比如：在中间位置或者头部进行元素插入或者删除的时候时间复杂度是O(N)效率比较低，并且顺序表在扩容的时候也存在时间和空间上的消耗，由于我们每次都是按照二倍来扩的，那就很有可能会出现扩大了用不完导致空间浪费的现象。这些问题该如何解决呢？那就需要用到今天分享给大家的另一种线性结构链表。

1 链表 1.1 链表的概念及结构

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。

注意：

从上图可看出，链式结构在逻辑上是连续的，但是在物理上不一定连续现实中的结点一般都是从堆上申请出来的从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续

假设在32位系统上，结点中值域为int类型，则一个节点的大小为8个字节，则也可能有下述链表：

1.2 链表的分类

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

1.2.1 单向或者双向

1.2.2 带头或者不带头

1.2.3 循环或者非循环

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：

1.2.4 无头单向非循环链表

1.2.5 带头双向循环链表

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。 2 链表的实现 2.1 结构 typedef int SLTDataType; typedef struct SListNode { SLTDataType data;//数据域 struct SListNode* next;//指针域 }SLTNode; 2.2 结点的创建

我们想使用链表来实现各种功能得先有链表，所以首先使用malloc创建节点。

SLNode* CreateNode(SLNDataType x) { SLNode* newnode = (SLNode*)malloc(sizeof(SLNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } newnode->val = x; newnode->next = NULL; return newnode; }

2.3 尾插

我们在尾插时，会有两种情况，链表为空的插入和有其他节点的尾插。第一种情况会出现一些理解性的错误，接下来就让我们学习学习这两种尾插的情况。

void SLTPushBack(SLNode** pphead, SLNDataType x) { assert(pphead); SLNode* newnode = CreateNode(x); if (*pphead == NULL) { *pphead = newnode; } else { SLNode* tail = *pphead; while (tail->next != NULL) { tail = tail->next; } tail->next = newnode; } } 2.4 头插

要想让链表连起来，就要让newnode->next存放下一个节点的地址，也就是旧链表phead的值，然后将newnode的地址存放在phead中，形成新的链表。无论一开始有没有节点，头插都是相同的。

void SLTPushFront(SLNode** pphead, SLNDataType x) { assert(pphead); SLNode* newnode = CreateNode(x); newnode->next = *pphead; *pphead = newnode; } 2.5 尾删

在尾删时也有两种情况，一种是有很多节点，另一种是只剩一个节点，当删最后一个节点时，要改变plist的值，所以我们要传递plist的指针。我们要使用两个指针，当后面的指针释放后，可以利用前面的指针将最后一个节点的next置为空。

void SLTPopBack(SLNode** pphead) { assert(pphead); assert(*pphead); if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else { SLNode* tail = *pphead; while (tail->next->next != NULL) { tail = tail->next; } free(tail->next); tail->next = NULL; } } 2.6 头删

头删时如果先释放空间，就会找不到下一个节点的地址；如果先把下一个节点的地址赋给*pphead就会导致无法释放空间，所以我们要创建一个临时变量来存放下一个节点的地址。

void SLTPopFront(SLNode** pphead) { assert(pphead); assert(*pphead); SLNode* tmp = *pphead; *pphead = (*pphead)->next; free(tmp); } 2.7 查找

循环判断时不要使用cur->next，这样写最后一个数据要单独处理不方便，找到时就返回此时的地址。

SLNode* SLTFind(SLNode* phead, SLNDataType x) { SLNode* cur = phead; while (cur) { if (cur->val == x) { return cur; } else { cur = cur->next; } } return NULL; } 2.8 在pos位置之前插入数据

在pos位置之前插入有一种特殊的情况就是头插，要改变plist的值，我们要传二级指针进去。同时我们要创建一个指针变量，找到pos之前的位置，才能使链表连接起来。

void SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x) { assert(pphead); assert(pos); assert(*pphead); if (*pphead == pos) { SLTPushFront(pphead, x); } else { SLNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } SLNode* newnode = CreateNode(x); prev->next = newnode; newnode->next = pos; } } 2.9 删除pos位置

有可能删除的是头节点，所以要传递二级指针。

void SLTErase(SLNode** pphead, SLNode* pos) { assert(pphead); assert(*pphead); assert(pos); if (*pphead == pos) { SLTPopFront(pphead); } else { SLNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); pos = NULL; } } 2.10 在pos位置之后插入数据

这里我们要注意地址赋值的顺序，顺序不对会造成内存泄漏。如果先把newnode的地址赋给pos的指针域，就会丢失下一个节点的地址。

void SLTInsertAfter(SLNode* pos, SLNDataType x) { assert(pos); SLNode* newnode = CreateNode(x); newnode->next = pos->next; pos->next = newnode; } 2.11 删除pos位置之后的数据 void SLTEraseAfter(SLNode* pos) { assert(pos); assert(pos->next); SLNode* tmp = pos->next; pos->next = pos->next->next; free(tmp); tmp = NULL; } 2.12 打印数据 void SLTPrint(SLNode* phead) { SLNode* cur = phead; while (cur != NULL) { printf("%d->", cur->val); cur = cur->next; } printf("NULL\n"); } 2.13 销毁数据 void SLTDestroy(SLNode** pphead) { assert(pphead); SLNode* cur = *pphead; while (cur) { SLNode* next = cur->next; free(cur); cur = next; } *pphead = NULL; }