网站导航
> 文章列表 > C语言实现单链表（PushBack PopBack PushFront PopFront Insert Erase Find Destroy）

C语言实现单链表（PushBack PopBack PushFront PopFront Insert Erase Find Destroy）

网友: 文章列表 2024-03-21 15:50:48

C语言实现单链表（PushBack PopBack PushFront PopFront Insert Erase Find Destroy）

链表是我们常用的一种数据结构，因为顺序表对于随机插入的效率太低，所以有了链表，不过今天说的是单链表

下面我们看一下单链表的实现

首先我们要知道，单链表就是一个一个的节点链接起来，所以他的底层结构不一定是连续的空间，而是用指针连接

既然链表是一个一个的节点，那么我们当然需要该节点的类型，在C语言中我们想要一个自己的类型需要用struct来定义

首先我们来看一下该数据结构中的头文件自己typedef的类型

C语言实现单链表（PushBack PopBack PushFront PopFront Insert Erase Find Destroy）

 

下面我们来定义一个节点

C语言实现单链表（PushBack PopBack PushFront PopFront Insert Erase Find Destroy）

这个就是我们定义的节点 ，既然有了节点，那么我们看一下我们需要实现的函数有哪些

C语言实现单链表（PushBack PopBack PushFront PopFront Insert Erase Find Destroy）

 其中我们实现几个常用的关于单链表的函数，分别是头插，尾插，头删，尾删，和任意位置插入，任意位置删除，和查找，最后就是销毁列表

下面我们先看一下尾插

C语言实现单链表（PushBack PopBack PushFront PopFront Insert Erase Find Destroy）其中这我们写的这个单列表是无哨兵位的单链C语言实现单链表（PushBack PopBack PushFront PopFront Insert Erase Find Destroy） 

所以我们需要定义一个该结构体的指针变量，如果我们刚开始插入的时候是空节点，所以我们需要将该指针变量弄成头节点，所以当我们第一次插入的时候，我们new/malloc一个新的节点，并把这个节点的val和next指针节点分别复制为，想要添加的val和NULL，所以我们在看一下如何create一个新节点

C语言实现单链表（PushBack PopBack PushFront PopFront Insert Erase Find Destroy） 

这个就是我们create节点的代码，我们有了节点以后我们就可以开始寻找最后一个节点，然后让tail的next指向新节点这样我们尾插就完成了

下面我们看一下打印

C语言实现单链表（PushBack PopBack PushFront PopFront Insert Erase Find Destroy） 

打印函数很简单，只要不为空我们就一直打印

下面我们看一下 头插

C语言实现单链表（PushBack PopBack PushFront PopFront Insert Erase Find Destroy）

头插的第一步当然也是create新节点，放有了节点之后，我们还需要判断该变量是否为第一次插入，如果是的话那么该变量就为空，所以就需要将新节点赋值给该变量，如果不是的话，只需要将新节点的next指向头节点，然后再把新节点赋值给头节点，这样我们就完成了头插

 下面我们来看尾删

C语言实现单链表（PushBack PopBack PushFront PopFront Insert Erase Find Destroy）

关于尾删我们需要判断很多 首先我们当然得判断是否为空，如果为空的话当然是不可以删除的，所以这时候我们可以直接return，或者assert也可以，然后我们就要判断是否为第一个节点，如果是第一个节点，那么我们就需要修改头节点，如果是其他的节点，则我们需要有一个可以记录的变量，记录前一个节点的变量prev，所以我们在让del迭代的时候，让prev永远是del的前一个值，但是这时候还是有一个问题，我们要删除的节点下一个节点为空的时候，这时候的prev是nullptr所以，在最后将prev的next置为空的时候，我们就会报错，所以我们需要单独处理

下面我们可以看一下头删

C语言实现单链表（PushBack PopBack PushFront PopFront Insert Erase Find Destroy）

头删是比较简单的，我们只需要判断一下，是否为空就可以了，剩下的就是记录头节点然后，让头节点等于他的next然后再free掉del

我们看一下查找

 C语言实现单链表（PushBack PopBack PushFront PopFront Insert Erase Find Destroy）

查找的返回值是找到的节点的地址，如果找不到则为空

下面看一下任意插入

 C语言实现单链表（PushBack PopBack PushFront PopFront Insert Erase Find Destroy）

任意位置插入，我们需要传入pos位置，而我们插入在pos位置之前

所以我们就可以和查找一起使用

任意位置插入，我们首先要判断是否为第一次插入，也需要判断插入的位置是否为头插，剩下的则是正常插入，如果不是前面两个，我们则需要记录插入位置的前一个位置prev我们那个找到插入位置的时候，我们同样是create节点，然后让prev的next指向新节点，然后再让新节点的next指向pos节点，而且我们还需要在其中判断pos位置是否存在，以及pos是否为空

下面我们看一下任意位置删除

 C语言实现单链表（PushBack PopBack PushFront PopFront Insert Erase Find Destroy）

任意位置删除，我们同样是个查找函数一起使用，我们删除pos位置，我们需要判断删除位置是否为头节点，如果不是的话也是需要记录删除位置的前一个节点，最后在删除的时候，让前一个节点的next指向删除位置的next节点，最后free掉该节点即可

最后我们来看一下链表销毁，虽然我们想一下，这么多节点是不是需要我们一个一个free但是由于我们写了erase函数以及尾删头删等，我们都可以通过复用来完成链表的销毁我们可以看一下

C语言实现单链表（PushBack PopBack PushFront PopFront Insert Erase Find Destroy） 

 这个销毁函数复用了erase函数所以我们只需要判断头节点是否为空即可，如果为空则删除完毕，如果不为空则还没有删除完，所以我们在循环里面删除节点

网络标签：

相关问题