【数据结构与算法】链表

简介: 【数据结构与算法】链表

一.链表的原理

上一篇博客,我们讲了顺序表,知道了其妙用,但是我们也发现了问题,那就是如果我需要插入或者删除元素时,需要移动非常多的数据,这是一个问题.

为了解决这个问题我们引入了链表.

链表也是一种线性的结构,只不过存储的位置并不相邻,是通过指针串起来的.

它由一系列节点组成,每个节点包含一个数据元素和一个指向下一个节点的指针.

二.单链表的结构

每个节点都包含一个数据域和指针域.

数据域可以是任何的数据类型,我这里是自定义的People类.

因为每一个节点都是相同的类型,所以指针的类型还是自己这个结构体的类型.

为什么重定义两个名字?

因为我们已经知道了,链表的组成就是一个个的节点.

在链表中有一个特殊的节点,那就是头节点,因为是链式的结构,我只有知道了头节点,就相当于整条链表.

所以我们用LinkList表示头节点,用LinkNode表示节点,其实都是一样的,但是更方便理解.

三.单链表的初始化

当我们定义好了链表的结构,我们现在来开始初始化.

其实就是初始化一个头节点.

我们先来看看头节点长什么样吧:

头节点相当于我们的链表,我们不需要为其设置数据.

显示创建了一个节点,然后做了一个防御性的编程,看分配的内存成功没有,然后对该节点的指向下一个节点的指针设置为空.

四.单链表增加元素

我们已经有了头节点,就相当于有了链表,我们来增加元素吧.

根据我们添加元素的位置不同,可以分为以下3种.

1.前插法

顾名思义,我每次添加进来的元素都是插入在头结点后的这个位置.

给大家画个图吧:

所以说不管是只有一个头节点,还是说有多个节点,前插法都是一样的.

先将头节点的指针域赋值给新插入的节点的指针域.

然后将新插入的节点赋值给头指针的指针域.

2.尾插法

刚刚的前插法是每次都在头节点后插入,那么现在的尾插法就是每次都插入到最后.

所以我们需要每次都要找到链尾,才能插入.

那么我们如何找到链尾呢?

我们可以注意到,链尾的指针域必定是空.通过这一点,我们可以找到尾节点,然后再进行插入.

为了变量节点,所以需要我们临时定义一个节点变量,将头节点赋值给临时变量,然后对其遍历,不停的last=last->next,直到last->next等于空,说明我们就找到了最后一个节点,然后进行插入.

新插入也很简单,就是新节点的指针域等于空,因为是插入在最后.

原本的最后一个节点的指针域就等于新插入的节点.

3.任意位置插入

这个是在给定的位置插入,像链表麻烦就麻烦在,你每次定位都必须从头节点开始,好了,不吐槽了,继续.

与尾插法的思想大致一样,只不过这里我们需要找到要插入位置的前一个节点.

当你不知所以然的时候,我们可以假设我们要插入1和2的位置.

当要插入的位置是1的时候,就是插入头节点后.

因为要遍历位置,所以我们还是定义了一个链表变量p,同时为了计数,定义了一个index的变量,

当我们i输入1的时候,是不会走到循环里面的,头节点也不为空,就刚好是插入在头节点后的.

当我们i输入2的时候,会进入到循环中,p指向了指针域所指向的地方,就循环了一次,因为有index>i-1这个循环条件.

p就刚好是第1个位置,就是我们要插入的前一个位置,然后插入即可.

if(!p||index>i-1)是为了防止要插入的位置为负数和0或者i超过了链表的节点数.

五.单链表的遍历

更尾插法的遍历基本一样

不停的进行遍历,如果本身为空了就退出,本身节点为空就相当于是最后一个节点的指针域,必定为空.

六.单链表获取元素

获取元素某个元素,当然也需要遍历了,不用像插入一样需要获取前一个位置,就获取那个位置就是那个位置.

因为头节点,没有数据,我们不需要获取,所以我们直接从头节点的下一个节点开始,从1开始.

这次的条件是index<i

下面的防御性编程是防止i过大或者过小.

然后将该节点的数据赋值为e,就拿到了我们想要的数据.

七.单链表查找元素

查找元素当然也需要我们进行遍历,只不过这次的遍历条件是节点的数据与我们想要查找的数据相等时,就说明找到了,如果遍历完了,还没有找到就说明没有.

全部遍历完,p必为空才会结束循环,说明没有找打.

八.单链表删除元素

1.根据位置删除

我们的逻辑更插入时差不多,都需要找到要删除节点的前一个节点,

当然有一点特殊,就是我们要保证前一个节点的指针域不能为空.

因为我们要做的是将要删除的指针域直接赋值给前一个节点指针域,达到删除的效果.

所以这里就不再是用p作为循环判断条件,而是p->next,其他判断条件完全与任意位置插入一样.

下面是用了一个临时的变量来保存要删除的位置.

上一个节点的指针域直接指向要删除的指针域.

2.根据值删除

这个不用慌,只不过是查找和删除的结合罢了.

通过查找获取位置,然后再删除.

九.单链表销毁

还是需要用到遍历来进行销毁.

变量先指向头节点,然后头结点指向下一个节点,delete变量,然后又等于头节点,一直循环往复,直到为空节点.

十.总结

链表的优势一看便知,就是插入删除数据不需要移动大量的数据,可以直接进行.

其缺点也是显而易见,不方便访问,每次都需要从头遍历.

对于遍历一些小技巧可以记一下:

  • 任意位置插入和删除都需要找到前一个节点位置,需要从头节点开始,区别是循环条件插入是p删除是p->next
  • 获取和查找因为头节点没有数据,都是从头节点的下一个节点开始.

注意:

  1. 我们需要的是最后一个节点,还是遍历完,最后一个节点的循环条件是p->next,遍历完是p
  2. 获取前一个节点循环条件是index<i-1,获取当前节点循环条件是index<i


相关文章
|
6天前
|
Java
java数据结构,双向链表的实现
文章介绍了双向链表的实现,包括数据结构定义、插入和删除操作的代码实现,以及双向链表的其他操作方法,并提供了完整的Java代码实现。
java数据结构,双向链表的实现
|
27天前
|
存储 Java 索引
【数据结构】链表从实现到应用,保姆级攻略
本文详细介绍了链表这一重要数据结构。链表与数组不同,其元素在内存中非连续分布,通过指针连接。Java中链表常用于需动态添加或删除元素的场景。文章首先解释了单向链表的基本概念,包括节点定义及各种操作如插入、删除等的实现方法。随后介绍了双向链表,说明了其拥有前后两个指针的特点,并展示了相关操作的代码实现。最后,对比了ArrayList与LinkedList的不同之处,包括它们底层实现、时间复杂度以及适用场景等方面。
42 10
【数据结构】链表从实现到应用,保姆级攻略
|
2月前
|
存储 C语言
【数据结构】c语言链表的创建插入、删除、查询、元素翻倍
【数据结构】c语言链表的创建插入、删除、查询、元素翻倍
【数据结构】c语言链表的创建插入、删除、查询、元素翻倍
|
2月前
|
算法
【算法】合并两个有序链表(easy)——递归算法
【算法】合并两个有序链表(easy)——递归算法
【算法】合并两个有序链表(easy)——递归算法
|
2月前
|
存储 算法
【初阶数据结构篇】顺序表和链表算法题
此题可以先找到中间节点,然后把后半部分逆置,最近前后两部分一一比对,如果节点的值全部相同,则即为回文。
|
2月前
|
存储 测试技术
【初阶数据结构篇】双向链表的实现(赋源码)
因为头结点的存在,plist指针始终指向头结点,不会改变。
|
2月前
|
存储 测试技术
【初阶数据结构篇】单链表的实现(附源码)
在尾插/尾删中,都需要依据链表是否为空/链表是否多于一个节点来分情况讨论,目的是避免对空指针进行解引用造成的错误。
|
2月前
|
算法
【数据结构与算法】共享双向链表
【数据结构与算法】共享双向链表
13 0
|
2月前
|
算法
【数据结构与算法】双向链表
【数据结构与算法】双向链表
13 0
|
2月前
|
算法
【数据结构与算法】循环链表
【数据结构与算法】循环链表
15 0
下一篇
无影云桌面