【数据结构——链表的深度探索】从实现到应用,保姆级攻略

【数据结构——链表深度探索】从实现到应用,保姆级攻略

  • 🍁1. 链表的介绍
  • 🍁2. 链表的实现
    • 🍁2.1 单向链表
      • 🍁2.1.1 size()
      • 🍁2.1.2 display()
      • 🍁2.1.3 contains(int key)
      • 🍁2.1.4 addFirst(int key),addLast(int key),addIndex(int key, int index)
      • 🍁2.1.5 remove(int key),removeAllKey(int key)
      • 🍁2.1.6 clear()
    • 🍁2.2 双向链表
      • 🍁2.2.1 addFirst(int key)
      • 🍁2.2.2 addLast(int key)
      • 🍁2.2.3 addIndex(int key, int index)
      • 🍁2.2.4 remove(int key)和removeAllKey(int key)
      • 🍁2.2.5 clear()
  • 🍁3. Java中LinkedList的使用
    • 🍁3.1 LinkedList的创建和使用
    • 🍁3.2 LinkedList的遍历
  • 🍁4. ArrayList和LinkedList的区别

🚀欢迎互三👉: 2的n次方_💎💎
🚀所属专栏:数据结构与算法学习💎💎

在这里插入图片描述

在这里插入图片描述

🍁1. 链表的介绍

链表是数据结构中一种非常重要的基础结构,它不同于数组,链表中的元素在物理存储上并不连续,而是通过指针(或引用)连接在一起。在Java中,链表的应用非常广泛,尤其是在需要动态添加或删除元素的场景中。

🍁2. 链表的实现

🍁2.1 单向链表

单链表中的每个元素都称为节点(Node),每个节点包含两个部分:一部分存储数据(value),另一部分存储指向列表中下一个节点的引用(next)。最后一个节点的next引用为null,表示链表的结束。

所以采用内部类的形式进行创建:

public class MySingleList {
    static class ListNode {
        public int value;
        public ListNode next;

        public ListNode(int value) {
            this.value = value;
        }
    }

    public ListNode head;
}

还可以创建一个IList接口,对其中的增删查改等方法进行规范,之后MySingleList对接口进行实现

public interface IList {
    void display();
    int size();
    boolean contains(int key);
    void addFirst(int key);
    void addLast(int key);
    void addIndex(int key,int index);
    void remove(int key);
    void removeAllKey(int key);
    void clear();
}

接下来就是方法的实现

🍁2.1.1 size()

返回长度:

只需要将head依次往末尾移动,并记录移动次数进行返回就可以了,当head为null时就表示已经遍历完成

    public int size() {
        ListNode cur = head;
        int cnt = 0;
        while (cur != null) {
            cnt++;
            cur = cur.next;
        }
        return cnt;
    }

🍁2.1.2 display()

遍历打印:

遍历的话需要找到头节点,接着依次往后移动,为了不该变头节点的指向,创建一个cur节点辅助遍历,同样的,结束的标志也是最后的指向不为空

public void display() {
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.value + " ");
            cur = cur.next;
        }
        System.out.println();
    }

🍁2.1.3 contains(int key)

判断值是否存在链表中,这里同样需要依次遍历,然后比较value的值

public boolean contains(int key) {
        ListNode cur = head;
        while (cur != null) {
            if (cur.value == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

🍁2.1.4 addFirst(int key),addLast(int key),addIndex(int key, int index)

头插:

头插比较简单,直接创建一个节点,并初始化值,指向原来的head节点,接着改为新的head节点

public void addFirst(int key) {
        ListNode node = new ListNode(key);
        node.next = head;
        head = node;
    }

尾插:

尾插就需要判断head节点是否为null,接着找到尾节点进行插入

public void addLast(int key) {
        ListNode node = new ListNode(key);
        //头结点为null,直接插入
        if (head == null) {
            head = node;
            return;
        }
        //找到尾节点进行插入
        ListNode cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = node;
    }

在指定索引插入:

在指定索引插入就更加麻烦一些,需要对传入的索引进行判断,如果是0.就调用头插的方法,如果等于链表的长度,就调用尾插的方法,如果是中间的索引,就遍历链表,找到该索引进行插入

public void addIndex(int key, int index) {
        ListNode node = new ListNode(key);
        //调用头插
        if (index == 0) {
            addFirst(key);
            return;
        }
        //调用尾插
        if (index == this.size()) {
            addLast(key);
            return;
        }
        //传入索引不合法的情况
        if (index < 0 || index > this.size()) {
            throw new IndexOutOfBoundsException();
        }
        //找到目标索引进行插入
        ListNode cur = head;
        while (index - 1 != 0) {
            cur = cur.next;
            index--;
        }
        node.next = cur.next;
        cur.next = node;
    }

🍁2.1.5 remove(int key),removeAllKey(int key)

删除指定元素:

如果head为空,直接返回,如果head的value就是目标元素,就把head的下一个节点作为头结点,其他情况就根据value的值寻找目标索引,如果没找到就返回,也就是cur节点为null,找到的话把cur的引用指向cur的之后第二个节点

//根据元素找到目标索引
private ListNode findIndexofKet(int key) {
        ListNode cur = head;
        while (cur.next != null) {
            if (cur.next.value == key) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }
   
    public void remove(int key) {
    //头结点为空
        if (head == null) {
            return;
        }
        //头结点为目标元素
        if (head.value == key) {
            head = head.next;
        }
        //其他节点为目标元素
        ListNode cur = findIndexofKet(key);
        if (cur == null) {
            return;
        }
        cur.next = cur.next.next;
    }

删除所有指定元素:

需要有两个指针,同时往后遍历,删除cur节点所指元素需要将pre节点的next指向cur的next,循环判断,最后还要判断head节点是否为指定元素

public void removeAllKey(int key) {
		//头结点为null,直接返回
        if (this.head == null) {
            return;
        }
        ListNode pre = head;
        ListNode cur = head.next;
        //循环删除
        while (cur != null) {
            if (cur.value == key) {
                pre.next = cur.next;
                cur = cur.next;
            } else {
                pre = cur;
                cur = cur.next;
            }
        }
        //判断头结点
        if (head.value == key) {
            head = head.next;
        }
    }

🍁2.1.6 clear()

清空链表:

清空链表只需要遍历链表所有节点,将每一个节点置为null即可,因为是从头结点开始,如果直接将head置为null,后续再找head.next就会报错,所以还需要用一个中间变量cur辅助遍历

public void clear() {
        ListNode cur = head;
        while (cur != null) {
            //创建变量,解决空指针异常
            ListNode curn = cur.next;
            cur = null;
            cur = curn.next;
        }
        head = null;
    }

🍁2.2 双向链表

双向链表有两个指针域,一个指向前一个节点,一个指向后一个节点
在这里插入图片描述

public class MyLinkedList implements IList {
    static class TListNode {
        public int value;
        TListNode pre;
        TListNode next;

        public TListNode(int value) {
            this.value = value;
        }
    }

    public TListNode head;
    public TListNode last;
}

双向链表的size() ,display(),contains(int key)和单向链表是一样的,下面来实现其他的方法

🍁2.2.1 addFirst(int key)

头插:

在这里插入图片描述

public void addFirst(int key) {
        TListNode node = new TListNode(key);
        if (head == null) {
            head = last = node;
        } else {
            node.next = head;
            head.pre = node;
            head = node;
        }
    }

🍁2.2.2 addLast(int key)

尾插:

public void addLast(int key) {
        TListNode node = new TListNode(key);
        if (head == null) {
            head = last = node;
        } else {
            last.next = node;
            node.pre = last;
            last = last.next;
        }
    }

🍁2.2.3 addIndex(int key, int index)

指定位置插入:

public void addIndex(int key, int index) {
        TListNode node = new TListNode(key);
        if(index < 0 || index > size()) return;
        if (index == 0) {
            addFirst(key);
            return;
        }
        if (index == size()) {
            addLast(key);
        }
        if (index > 0 && index < size()) {
            TListNode cur = head;
            //可以直接到indext的位置,因为双向链表可以找到前一个节点
            while (index-- != 0) {
                cur = cur.next;
            }
            node.next = cur;
            cur.pre.next = node;
            node.pre = cur.pre;
            cur.pre = node;
        }
    }

需要修改四个位置,把要插入的节点node的next 指向cur,再把cur.pre的next指向node,此时节点的next都有了指向,接着node的pre指向cur.pre节点,cur的pre再指向node,此时就完成了插入
在这里插入图片描述

🍁2.2.4 remove(int key)和removeAllKey(int key)

首先找到要删除的值的索引

private TListNode findIndexofKet(int key) {
        TListNode cur = head;
        while (cur != null) {
            if (cur.value == key) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

删除的时候还要考虑是否为头结点和尾节点

public void remove(int key) {
        TListNode cur = findIndexofKet(key);
        if(cur == null){
            return;
        }
        //头节点的情况
        if(cur == head){
            head = cur.next;
            //只有一个节点时,指向next后head为null所以当head!=空时才能把pre置为null
            if (head != null) {
                head.pre = null;
            }
        }else{
            cur.pre.next = cur.next;
            //尾节点的情况
            if(cur.next == null){
                last = last.pre;
            }else{
                cur.next.pre = cur.pre;
            }
        }
    }

相比于单向链表,双向链表的删除所有指定元素就非常简单了,只需要在原来删除一个的基础上稍加修改就可以了

public void removeAllKey(int key) {
        TListNode cur = head;
        while (cur != null) {
            if (cur.value == key) {
                if (cur == head) {
                    head = cur.next;
                    if (head != null) {
                        head.pre = null;
                    }
                } else {
                    cur.pre.next = cur.next;
                    if (cur.next == null) {
                        last = last.pre;
                    } else {
                        cur.next.pre = cur.pre;
                    }
                }
            }
            cur = cur.next;
        }
    }

🍁2.2.5 clear()

清空链表还是依次遍历每一个节点,把每一个节点都置为null,最后把head和last也置为null

public void clear() {
        TListNode cur = head;
        while(cur.next!=null){
            TListNode curn = cur;
            curn.pre = null;
            curn.next = null;
            cur = curn;
        }
        head = last = null;
    }

🍁3. Java中LinkedList的使用

🍁3.1 LinkedList的创建和使用

在上一篇数据结构ArrayList的讲解中已经简单提到过👉点我看回顾,集合的一些基本框架,LinkedList也实现了List接口,所以也可以通过接口创建对象,也可以使用List接口中的方法

public class Demo {
    public static void main(String[] args) {
        LinkedList<Integer> list1 = new LinkedList<>();
        List<Integer> list2 = new LinkedList<>();
        list1.add(1);
        list1.add(2);
        System.out.println(list1);
        list2.add(1);
        list2.add(3);
        System.out.println(list2);
    }
}

在这里插入图片描述
可以直接对LinkedList的对象进行打印,也就是说LinkedList重写了toSting方法
在这里插入图片描述
这些都是LinkedList中独有的方法,这里就不列举使用了,

🍁3.2 LinkedList的遍历

LinkedList的遍历和ArrayList的遍历方式一样,在上一篇介绍了五种遍历方式,这次再简单回顾一下

public class Demo {
    public static void main(String[] args) {
        LinkedList<Integer> list1 = new LinkedList<>();
        list1.add(1);
        list1.add(2);
        list1.add(3);
        list1.add(4);
        //迭代器 ListIterator
        ListIterator<Integer> lit = list1.listIterator();
        while(lit.hasNext()){
            System.out.print(lit.next() + " ");
        }
        System.out.println();
        //Iterator
        Iterator<Integer> it = list1.iterator();
        while(it.hasNext()){
            System.out.print(it.next() + " ");
        }
        System.out.println();
        //增强for
        for(Integer l : list1){
            System.out.print(l + " ");
        }
        System.out.println();
        //普通for
        for(int i = 0;i < list1.size();i++){
            System.out.print(list1.get(i) + " ");
        }
        System.out.println();
        //lambda表达式
        list1.forEach(e -> {
            System.out.print(e + " ");
        });
        System.out.println();
    }
}

🍁4. ArrayList和LinkedList的区别

在这里插入图片描述
ArrayList底层是一个动态数组
LinkedList底层是双向链表
ArrayList:访问元素的时间复杂度为 O(1)(直接通过索引)。
LinkedList:访问元素的时间复杂度为 O(n)(需要从头或尾开始遍历到目标位置)。
ArrayList:
在末尾添加元素的时间复杂度为 O(1)
在中间插入或删除元素时,时间复杂度为 O(n),因为需要移动其他元素以保持连续的内存块。
LinkedList:
在任意位置添加或删除元素的时间复杂度为 O(1),只需改变前后节点的指针(需要先找到目标位置,时间复杂度为 O(n))。

使用场景:
ArrayList:
适合频繁读取、随机访问元素的场景。
如需要大量顺序读写、索引访问操作。
LinkedList:
适合频繁插入、删除元素的场景,尤其是在列表中间进行操作。
如需要频繁的增删操作,但不常用到随机访问。

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/790325.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

centOS79中安装jdk18

##red## &#x1f534; 大家好&#xff0c;我是雄雄&#xff0c;欢迎关注微信公众号&#xff0c;雄雄的小课堂。 前言 在centos7.9中安装jdk1.8很简单&#xff0c;就一条命令即可。 安装命令 yum -y install java-1.8.0-openjdk然后回车就行。 然后我们来运行一下看看是否安装…

玩转HarmonyOS NEXT之组件导航与路由跳转一

组件导航 (Navigation) Navigation是路由容器组件&#xff0c;一般作为首页的根容器&#xff0c;包括单栏(Stack)、分栏(Split)和自适应(Auto)三种显示模式。Navigation组件适用于模块内和跨模块的路由切换&#xff0c;一次开发&#xff0c;多端部署场景。通过组件级路由能力实…

【多线程】线程同步--条件变量的原理及其使用

文章目录 前言线程同步的基本概念条件变量定义条件变量初始化条件变量销毁条件变量等待条件&#xff08;重要&#xff09;唤醒等待简单运用常见使用条件变量的格式 前言 线程同步意味着在多线程并发执行中&#xff0c;协调线程之间的执行顺序&#xff0c;以确保共享资源被正确…

本地部署,图片细节处理大模型Tile Controlnet

目录 什么是 Tile ControlNet&#xff1f; 工作原理 应用场景 优势与挑战 优势 挑战 本地部署 运行结果 未来展望 结论 Tip&#xff1a; 在近年来的深度学习和计算机视觉领域&#xff0c;生成对抗网络&#xff08;GAN&#xff09;和扩散模型等技术取得了显著的进展。…

Everything搜索无法搜索到桌面的文件(无法检索C盘 或 特定路径的文件)

现象描述 在Everything搜索框中输入桌面已存在的文件或随便已知位置的文件&#xff0c;无法找到。 搜索时检索结果中明显缺少部分磁盘位置的&#xff0c;例如无法检索C盘&#xff0c;任意关键字搜索时结果中没有位于C盘的&#xff0c;无论怎样都搜不到C盘文件。 解决方法 在…

新书速览|HTML5+CSS3 Web前端开发与实例教程:微课视频版

《HTML5CSS3 Web前端开发与实例教程&#xff1a;微课视频版》 本书内容 《HTML5CSS3 Web前端开发与实例教程&#xff1a;微课视频版》秉承“思政引领&#xff0c;立德树人”的教育理念&#xff0c;自然融入多维度、深层次的思政元素&#xff0c;全面对标企业和行业需求&#x…

IAR 编译优化等级详解

目录 1.编译时优化器何时介入 2.编译优化等级汇总 3.优化项解读 3.1 代码移动 3.2 函数内联 3.3 循环交换 3.4 循环展开 3.5 公用表达式消除 3.6 链接阶段的优化 4 小结 大家好&#xff0c;这里是快乐的肌肉。 最近在迁移工程到IAR编译器上&#xff0c;发现编译优化…

【第27章】MyBatis-Plus之Mybatis X 插件

文章目录 前言一、安装指南二、核心功能1.XML 映射跳转2.代码生成3. 重置模板 三、JPA 风格提示四、常见问题解答1. JPA 提示功能无法使用&#xff1f;2. 生成的表名与预期不符&#xff1f; 五、代码生成模板配置1. 默认模板2. 重置默认模板3. 自定义模板内容3.1 实体类信息3.2…

虚拟机因断电进入./#状态解决办法

现象&#xff1a; 解决&#xff1a;先查看错误日志&#xff1a;journalctl -p err -b查看自己虚拟机中标黄部分的名字 之后运行&#xff1a;xfs_repair -v -L /dev/sda #这里sda用你自己标黄的 最后重启 reboot 即可。

基于Java技术的网吧管理系统

你好呀&#xff0c;我是计算机学姐码农小野&#xff01;如果有相关需求&#xff0c;可以私信联系我。 开发语言&#xff1a;Java 数据库&#xff1a;MySQL 技术&#xff1a;Java技术&#xff0c;B/S结构 工具&#xff1a;MyEclipse&#xff0c;MySQL 系统展示 首页 个人中…

WebRTC API接口教程:实现高效会议的步骤?

WebRTC api接口教程如何使用&#xff1f;WebRTC api接口的功能&#xff1f; WebRTC无需中间服务器即可传输音视频流&#xff0c;为视频会议、在线教育等应用提供了强大的支持。AokSend将详细介绍如何利用WebRTC API接口实现高效会议的步骤。 WebRTC API接口教程&#xff1a;获…

悠律凝声环开放式耳机体验:强劲低音、高颜值设计

最近发现了一款潮酷的开放式耳机&#xff0c;不仅颜值抗打&#xff0c;更重要的是能在嘈杂的环境中提供给我一份宁静的沉浸式音乐体验&#xff0c;号称是开放音频中的重低音之王&#xff0c;它就是悠律凝声环开放式耳机。 这款耳机无论其外观设计、音质效果、性价比以及续航能力…

MinIO - 服务端签名直传(前端 + 后端 + 效果演示)

目录 开始 服务端签名直传概述 代码实现 后端实现 前端实现 效果演示 开始 服务端签名直传概述 传统的&#xff0c;我们有两种方式将图片上传到 OSS&#xff1a; a&#xff09;前端请求 -> 后端服务器 -> OSS 好处&#xff1a;在服务端上传&#xff0c;更加安全…

【智能算法改进】一种混合多策略改进的麻雀搜索算法

目录 1.算法原理2.改进点3.结果展示4.参考文献5.代码获取 1.算法原理 【智能算法】麻雀搜索算法&#xff08;SSA&#xff09;原理及实现 2.改进点 精英反向学习策略 将精英反向学习策略应用到初始化阶段, 通过反向解的生成与精英个体的选择, 不仅使算法搜索范围得到扩大, 提…

DELTA: DEGRADATION-FREE FULLY TEST-TIME ADAPTATION--论文笔记

论文笔记 资料 1.代码地址 2.论文地址 https://arxiv.org/abs/2301.13018 3.数据集地址 https://github.com/bwbwzhao/DELTA 论文摘要的翻译 完全测试时间自适应旨在使预训练模型在实时推理过程中适应测试数据流&#xff0c;当测试数据分布与训练数据分布不同时&#x…

苹果笔记本电脑能玩哪些游戏 苹果电脑可以玩的单机游戏推荐

苹果笔记本有着优美的外观和强大的性能。用户不仅可以使用苹果笔记本办公、剪辑&#xff0c;越来越多的用户开始关注苹果笔记本在游戏领域的表现&#xff0c;尤其是在大型游戏方面。本文将为你详细介绍苹果笔记本都能玩什么游戏&#xff0c;以及为你推荐苹果电脑可以玩的单机游…

tesla p100显卡显示资源不足,api调用失败

&#x1f3c6;本文收录于《CSDN问答解惑-专业版》专栏&#xff0c;主要记录项目实战过程中的Bug之前因后果及提供真实有效的解决方案&#xff0c;希望能够助你一臂之力&#xff0c;帮你早日登顶实现财富自由&#x1f680;&#xff1b;同时&#xff0c;欢迎大家关注&&收…

进程间的通信--管道

文章目录 一、进程通信的介绍1.1进程间为什么需要通信1.2进程如何通信 二、管道2.1匿名管道2.1.1文件描述符理解管道2.1.2接口使用2.1.3管道的4种情况2.1.4管道的五种特征 2.2管道的使用场景2.2.1命令行中的管道2.2.2进程池 2.命名管道2.1.1原理2.2.2接口2.2.3代码实例 一、进程…

C++初阶:类与对象(一)

✨✨所属专栏&#xff1a;C✨✨ ✨✨作者主页&#xff1a;嶔某✨✨ 类的定义 定义格式 • class为定义类的关键字&#xff0c;后面跟类的名字&#xff0c;{}中为类的主体&#xff0c;注意类定义结束时后⾯分号不能省略。类体中内容称为类的成员&#xff1b;类中的变量称为类的…

设计模式之职责链模式

1. 职责链模式&#xff08;Chain of Responsibility Pattern&#xff09; 在职责链模式中&#xff0c;多个处理器依次处理同一个请求。一个请求先经过 A 处理器处理&#xff0c;然后再把请求传递给 B 处理器&#xff0c;B处理器处理完后再传递给 C 处理器&#xff0c;以此类推&…