数据结构:图文详解单链表的各种操作(头插法,尾插法,任意位置插入,删除节点,查询节点,求链表的长度,清空链表)

本文主要是介绍数据结构:图文详解单链表的各种操作(头插法,尾插法,任意位置插入,删除节点,查询节点,求链表的长度,清空链表),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!


目录

 一.什么是链表

二.链表的实现

节点的插入

头插法

尾插法

指定位置插入

节点的删除

删除第一次出现的关键字节点

删除所有关键字节点

节点的查找

链表的清空

链表的长度


前言:在上一篇文章中,我们认识了线性数据结构中的顺序表,而本篇文章则是介绍线性数据结构中的另一个结构——链表

想要了解顺序表相关操作的知识可以查看这篇文章:
图文详解顺序表的各种操作

 一.什么是链表

链表是一种数据结构,它由一系列节点(node)构成,每个节点中包含了数据(data)和指向下一个节点的指针(next)。链表中的节点可以在内存中任何位置,它们通过指针链接在一起,形成一个链式结构。链表相对于数组的优点在于它可以动态地增加、删除节点,而不需要移动大量的数据。链表的缺点是访问元素时需要遍历整个链表,效率较低。

二.链表的实现

链表由不同的节点相互串起来,每个节点由俩个部分组成,一个是数据域,用来放具体是数值内容,另一个是指针域,用来存放下一个节点的地址信息,彼此之间就像是用链条串起来一样,就像下图展示的这样,所以称之为链表。

对于上图这样的结构,我们可以如下定义一个链表,将链表作为一个类,并且在这个类中有一个内部类专门存储每一个节点的数据结构,还有一个头节点单独定义来记录链表的起始位置

public class MyLinkList{//节点的数据结构static class ListNode{public int val;public ListNode next;}//链表的属性public ListNode head;//记录链表的第一个元素:头节点
}

对一个链表,它应该完成以下这些功能,我们将这些功能抽象出一个接口,然后通过这个接口去实现一个真正的链表

public interface Ilist {//头插void addFirst(int data);//尾插void addLast(int data);//指定插入void addIndex(int index,int data);//查询是否存在boolean contains(int key);//删除节点void remove(int key);//删除所有与目标相同的节点void removeAllKey(int key);//得到链表的长度int size();//清空链表void clear();//输出链表的所有信息void display();
}

节点的插入

我们将节点的插入分为三种:

  • 头部插入:将节点插入到链表的最前面
  • 尾部插入:将节点插入到链表的最后面
  • 指定位置插入:将节点插入到链表的中间

头插法

如图,我们准备对于刚才的链表进行插入

我们这里分俩个步骤进行操作:

  1. 将新节点指向头节点
  2. 更新头节点的位置

我们更改要添加节点的指针域,让它指向新的节点 

在指向完成后,我们新添加的节点就已经是链表的第一个节点了,所以我们要更新头节点的信息,记录新节点才是第一个节点

这样我们就完成了头部插入节点,具体代码实现如下,先生成一个节点,然后按照上面图示的思路进行操作

    //头插法public void addFirst(int data) {ListNode newNode = new ListNode(data);newNode.next = this.head;this.head = newNode;}

尾插法

尾插法是将节点插入到链表的末尾,但是我们是并没有记录末尾节点的位置的,所以如果要使用尾插法的话就需要先找到尾部节点。那我们只需要根据最后一个节点特征进行遍历找到最后一个节点就可以了,而最后一个节点最大的特征就是,它只有数据域内有信息,指针域里面是空。如果链表为空的话,那我们直接在头节点之后添加就可以,整体流程如下:

整体代码实现如下,先判断是否为空链表,为空就直接在头节点之后添加,不为空就遍历找到最后一个节点,然后更改指针域内容,添加新节点

    //尾插法public void addLast(int data) {//当链表为空的时候,直接将节点插入到头节点的位置ListNode newNode = new ListNode(data);if (head == null) {head = newNode;}else{ListNode cur = head;while (cur.next != null){cur = cur.next;}//找到最后一个节点cur.next = newNode;//newNode.next = null;//默认新节点的指针域为空,所以这里可以不写这一行代码}}

指定位置插入

在中间位置插入是最麻烦的,原因就在于我们不能立马获取到想要插入位置的信息,我们需要先进行判断,如果输入位置是在最前面,那就可以使用头插,如果是最后就使用尾插。在得知输入位置在链表中间后,我们就需要先找到这个位置前后的节点的信息,如下图,假如我们要插入的位置是第三个位置,那就需要知道第二个位置和第三个位置的信息,当我们找到了后可以分俩布进行操作(顺序不能更改):

  1. 先让节点指向后面的节点
  2. 再让前面的节点指向插入节点

第一步,让插入节点指向后面的节点

第二步,将前面的节点指向插入的节点

我们可以通过代码来实现这段过程,先是进行合法性的判断,然后是针对性的插入

    //指定位置添加public void addIndex(int index, int data) {if(index < 0 || index > size()) {//这里不一定非要抛出自定义异常,大家可以更具喜好自行设置throw new IndexException("index不合法: "+index);}//如果输入的位置在最前面就进行头插if (index == 0)addFirst(data);//如果输入的位置在链表最后就进行尾插if (index == size())addLast(data);//输入位置在中间,就先找到这个节点的位置ListNode cur = searchPrevIndex(index);ListNode newNode = new ListNode(data);//这俩步是顺序非常重要newNode.next = cur.next;cur.next = newNode;}//找到位置对应的节点private ListNode searchPrevIndex(int index) {ListNode cur = head;int count = 0;while (count != index-2) {cur = cur.next;count++;}return cur;}

节点的删除

对于节点是删除相当于插入简单了很多,我们依旧是分为俩种方式进行删除,一种是只删除第一次出现的节点,另一种是删除全部想要删除的节点。

删除第一次出现的关键字节点

我们依旧是用初始的链表进行举例,假如我们想要删除第三个节点

第一步,我们直接更改要删除节点的前面节点的指针域,让它指向要删除的节点后的节点

第二步,我们将要删除的节点的指针域置为空

这俩步的顺序同样也不能错,因为一旦我们先将要删除的节点的指针域置为空,我们就无法再找到后面的节点了,链表就相当于断开了

我们封装一个函数用来找到要删除节点的前一个节点,然后通过它再删除目标节点

    //删除第一个关键字public void remove(int key) {if (head == null)return;if (head.val == key){head = head.next;return;}//查找val等于key的节点ListNode cur = findKey(key);if (cur == null){System.out.println("查无此元素,无法删除");return;}ListNode delNode = cur.next;cur.next = delNode.next;//cur.next =cur.next.next;}//找到要删除的元素的前一个节点private ListNode findKey(int key){ListNode cur = head;while (cur.next != null){if (cur.next.val != key) {cur = cur.next;}else{return cur;}}return null;}

删除所有关键字节点

与刚才不同的是,删除一个节点是先找到前驱节点,然后通过这个前驱节点进行操作,而要删除所有的关键字节点,则是对整个链表进行遍历,一旦是关键字,那我们就进行覆盖删除,这里就不再画图了,毕竟整个流程相当于多执行几次单个删除操作

    //删除所有的关键字public void removeAllKey(int key) {if(head == null) {return;}ListNode prev = head;ListNode cur = head.next;while (cur != null) {if(cur.val == key) {prev.next = cur.next;cur = cur.next;}else {prev = cur;cur = cur.next;}}//除了头节点都删除完成了if(head.val == key) {head = head.next;}}

节点的查找

节点的查找就是遍历整个链表,如果找到就返回true,没有找到就返回false

    //查找是否存在public boolean contains(int key) {ListNode cur = head;while (cur != null){if (cur.val == key)return true;cur = cur.next;}return false;}

链表的清空

当链表的头节点为空,我们就视为链表被清空了

    //清空链表public void clear() {head = null;}

链表的长度

遍历整个链表,使用计算器进行累加记录节点个数,然后返回就可以

    //求链表的长度public int size() {int count =0;ListNode cur = head;while (cur != null){count++;cur = cur.next;}return count;}



  本次的分享就到此为止了,希望我的分享能给您带来帮助,也欢迎大家三连支持,你们的点赞就是博主更新最大的动力!如有不同意见,欢迎评论区积极讨论交流,让我们一起学习进步!有相关问题也可以私信博主,评论区和私信都会认真查看的,我们下次再见

这篇关于数据结构:图文详解单链表的各种操作(头插法,尾插法,任意位置插入,删除节点,查询节点,求链表的长度,清空链表)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/445580

相关文章

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明(认真看哦) AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证,则会调用 #attemptAuthentica

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画(下)

【课程链接】 AntV G6:深入图形与图形分组、自定义节点、节点动画(下)_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中,应该怎样去计算和绘制图形,如何给一个图形制作不间断的动画,以及在鼠标事件之后产生动画。(有点难,需要好好理解) <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06

电脑桌面文件删除了怎么找回来?别急,快速恢复攻略在此

在日常使用电脑的过程中,我们经常会遇到这样的情况:一不小心,桌面上的某个重要文件被删除了。这时,大多数人可能会感到惊慌失措,不知所措。 其实,不必过于担心,因为有很多方法可以帮助我们找回被删除的桌面文件。下面,就让我们一起来了解一下这些恢复桌面文件的方法吧。 一、使用撤销操作 如果我们刚刚删除了桌面上的文件,并且还没有进行其他操作,那么可以尝试使用撤销操作来恢复文件。在键盘上同时按下“C

OpenHarmony鸿蒙开发( Beta5.0)无感配网详解

1、简介 无感配网是指在设备联网过程中无需输入热点相关账号信息,即可快速实现设备配网,是一种兼顾高效性、可靠性和安全性的配网方式。 2、配网原理 2.1 通信原理 手机和智能设备之间的信息传递,利用特有的NAN协议实现。利用手机和智能设备之间的WiFi 感知订阅、发布能力,实现了数字管家应用和设备之间的发现。在完成设备间的认证和响应后,即可发送相关配网数据。同时还支持与常规Sof

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

csu1329(双向链表)

题意:给n个盒子,编号为1到n,四个操作:1、将x盒子移到y的左边;2、将x盒子移到y的右边;3、交换x和y盒子的位置;4、将所有的盒子反过来放。 思路分析:用双向链表解决。每个操作的时间复杂度为O(1),用数组来模拟链表,下面的代码是参考刘老师的标程写的。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#

活用c4d官方开发文档查询代码

当你问AI助手比如豆包,如何用python禁止掉xpresso标签时候,它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸(两张壁纸可不一致)

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸: 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  (注意不能是bmp格式) 替换默认锁屏壁纸: 将图片资源放入vendo

day-51 合并零之间的节点

思路 直接遍历链表即可,遇到val=0跳过,val非零则加在一起,最后返回即可 解题过程 返回链表可以有头结点,方便插入,返回head.next Code /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}*

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)