数据结构-链表-单链表（3）

目录

1. 顺序表的缺陷

2. 单链表

2.1 单链表的基本结构与接口函数

2.2 重要接口

创建新节点的函数：

2.2.1 尾插

2.2.2 头插

2.2.3 尾删

2.2.4 头删

2.2.5 查找

2.2.6 插入

2.2.7 删除

2.2.8 从pos后面插入

2.2.9 从pos后面删除

3. 链表的缺陷与优势：

4. 链表与顺序表比较

写在最后：

---

1. 顺序表的缺陷

为什么会有链表？

我们都有顺序表来存储数据了，

因为顺序表是有缺陷的：

1. 中间头部插入删除数据，需要挪动数据，效率低下。

2. 空间不够需要扩容，扩容会有一定的消耗，也可能会造成空间的浪费。

这时候，我们就要用到链表。

2. 单链表

链表是一种物理存储结构上非连续、非顺序的存储结构，

数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

如下图： 

2.1 单链表的基本结构与接口函数

基本结构：

#pragma once#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int SLDataType;typedef struct SListNode
{SLDataType data;struct SListNode* next;
}SLNode;//打印链表
void SLPrint(SLNode* phead);//尾插
void SLPushBack(SLNode** pphead, SLDataType x);//头插
void SLPushFront(SLNode** pphead, SLDataType x);//尾删
void SLPopBack(SLNode** ppheadx);//头删
void SLPopFront(SLNode** pphead);//查找
SLNode* SLFind(SLNode* phead, SLDataType x);//插入
void SLInsert(SLNode** phead, SLNode* pos, SLDataType x);//删除
void SLErase(SLNode** phead, SLNode* pos);//从pos后面插入
void SLInsertAfter(SLNode* pos, SLDataType x);//从pos后面删除
void SLEraseAfter(SLNode* pos);

2.2 重要接口

创建新节点的函数：

//建立一个新节点（重复操作写成函数复用）
SLNode* BuyNewNode(SLDataType x)
{//malloc一个链表节点大小的空间SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));//检查if (newnode == NULL){perror("malloc::fail");return;}//赋值newnode->data = x;newnode->next = NULL;return newnode;
}

2.2.1 尾插

//尾插
void SLPushBack(SLNode** pphead, SLDataType x)
{//检查二级指针pphead地址是否为空	//方便检查是否传空指针了assert(pphead);//创建节点SLNode* newnode = BuyNewNode(x);//如果链表为空if (*pphead == NULL){*pphead = newnode;}else//如果链表不为空{//找尾SLNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}//尾插tail->next = newnode;}
}

2.2.2 头插

//头插
void SLPushFront(SLNode** pphead, SLDataType x)
{//检查二级指针pphead地址是否为空	//方便检查是否传空指针了assert(pphead);//创建节点SLNode* newnode = BuyNewNode(x);//头插newnode->next = *pphead;*pphead = newnode;
}

2.2.3 尾删

//尾删
void SLPopBack(SLNode** pphead)
{//检查二级指针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.2.4 头删

//头删
void SLPopFront(SLNode** pphead)
{//检查二级指针pphead地址是否为空	//方便检查是否传空指针了assert(pphead);//检查链表是否为空assert(*pphead);//头删SLNode* cur = (*pphead)->next;free(*pphead);*pphead = NULL;*pphead = cur;
}

2.2.5 查找

//查找
SLNode* SLFind(SLNode* phead, SLDataType x)
{//创建指针遍历链表SLNode* cur = phead;//查找while (cur){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}

2.2.6 插入

//插入
void SLInsert(SLNode** pphead, SLNode* pos, SLDataType x)
{//检查查找的地址是否为空assert(pos);//pos的位置if (pos == *pphead){SLPushFront(pphead, x);}else//在链表中间{SLNode* prev = *pphead;//查找pos对应位置while (prev->next != pos){prev = prev->next;}//插入SLNode* newnode = BuyNewNode(x);prev->next = newnode;newnode->next = pos;}
}

2.2.7 删除

//删除
void SLErase(SLNode** pphead, SLNode* pos)
{//检查二级指针pphead地址是否为空	//方便检查是否传空指针了assert(pphead);//检查查找的地址是否为空assert(pos);//检查链表是否为空（这里其实不断言也可以）assert(*pphead);//头删的情况if (*pphead == pos){SLPopFront(pphead);}else{//查找SLNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//删除prev->next = pos->next;free(pos);pos = NULL;}
}

2.2.8 从pos后面插入

//从pos后面插入
void SLInsertAfter(SLNode* pos, SLDataType x)
{//检查查找的地址是否为空assert(pos);//创建节点SLNode* newnode = BuyNewNode(x);//再pos后面插入newnode->next = pos->next;pos->next = newnode;
}

2.2.9 从pos后面删除

//从pos后面删除
void SLEraseAfter(SLNode* pos)
{//检查查找的地址和要删除的地址是否为空assert(pos);assert(pos->next);//在pos后面删除，prev记住要删除的节点，然后freeSLNode* prev = pos->next;pos->next = prev->next;free(pos->next);prev = NULL;
}

这就是单链表的基本框架和接口了，

如果感兴趣，你也可以使用接口函数玩一玩。

3. 链表的缺陷与优势：

但是链表是有缺陷的，

我们可以看到，

1. 链表想要访问一个节点，就得遍历链表，

2. 链表的尾删也需要遍历链表，

3. 而链表的优势是头删很方便是O(1)。

4. 链表与顺序表比较

我们就能跟顺序表比较一下，

1. 顺序表头插需要挪动数据是O(N)，

2. 但是顺序表能随机访问。

写在最后：

以上就是本篇文章的内容了，感谢你的阅读。

如果喜欢本文的话，欢迎点赞和评论，写下你的见解。

如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。

之后我还会输出更多高质量内容，欢迎收看。