数据结构-链表结构-双向链表

双向链表

双向链表的定义

双向链表也叫双链表,与单向链表不同的是,每一个节点有三个区域组成:两个指针域,一个数据域

  • 前一个指针域:存储前驱节点的内存地址
  • 后一个指针域:存储后继节点的内存地址
  • 数据域:存储节点数据

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-KV1HQu2K-1690882200220)(E:\Java笔记\数据结构\线形结构\链表结构\链表结构.assets\image-20230801092637927.png)]

以下就是双向链表的最基本单位

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-K825DLOg-1690882200221)(E:\Java笔记\数据结构\线形结构\链表结构\链表结构.assets\image-20230801092801444.png)]

节点的前指针域指向前驱,后指针域执行后继

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-6zQK3LeB-1690882200221)(E:\Java笔记\数据结构\线形结构\链表结构\链表结构.assets\image-20230801112807368.png)]

完整的双向链表

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-QC8iOcYu-1690882200222)(E:\Java笔记\数据结构\线形结构\链表结构\链表结构.assets\image-20230801140702244.png)]

双向链表的功能

    • 向双向链表的尾节点之后添加节点

      • 尾节点的后指针域存储新添加节点的内存地址

      • 新添加节点的前指针域存储尾节点的内存地址

        注意:此时尾节点就是新添加的这个节点

      [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-tIwTitAd-1690882200223)(E:\Java笔记\数据结构\线形结构\链表结构\链表结构.assets\20230801_142639.gif)]

    • 向双向链表的首元节点之前添加节点

      • 新添加节点的后指针域存储首元节点的内存地址

      • 首元节点的前指针域存储新添加节点的内存地址

        注意:此时首元节点就是新添加的这个节点

      [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-yqVLrOWP-1690882200223)(E:\Java笔记\数据结构\线形结构\链表结构\链表结构.assets\20230801_153607.gif)]

    • 删除中间节点时修改改节点的前驱和后继的指针方向即可

      注意:被删除的节点称之为:野节点,这并不是真正意义上的删除,它在内存中依旧存在。那么野节点的最终归宿是被JVM的GC(垃圾回收器)所回收,也就是释放该节点的内存空间,这才是真正意义上的删除

      额外知识:java中的垃圾回收器(Garbage Collector,GC)负责管理内存的分配和释放。当一个对象没有任何引用指向它时,它就变得不可达,而垃圾回收器会将其标记为垃圾对象,并在适当的时候回收该对象所占用的内存空间。这个过程称为垃圾回收。

      [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kYeMLeLn-1690882200223)(E:\Java笔记\数据结构\线形结构\链表结构\链表结构.assets\20230801_160349 (1)].gif)

    • 挪动指针找到要修改的节点,之后讲修改节点的数据域中的数据修改掉
    • 挪动指针找到要所要查找的数据。

特点

  • 双向性:
    • 每个节点除了存储自己的数据外,还包含两个指针域,分别存储前驱和后继的内存地址,因此可以在链表中向前或向后遍历。
  • 动态性:
    • 双向链表可以在运行时动态地添加、删除和修改节点,相对于数组等静态数据结构更加灵活。
  • 插入和删除操作高效:
    • 由于双向链表中的节点包含指向前驱和后继的的指针,因此插入和删除操作只需要调整节点前后的指针,而不需要像数组那样移动大量元素。
  • 空间利用率较高:
    • 相比单向链表,双向链表需要额外的指针来表示前一个节点,空间利用率略低一些,但在某些情况下方便了一些操作。
  • 双向遍历能力:
    • 双向链表可以从任意节点开始向前或向后遍历,这在某些场景中非常有用,例如需要反向迭代链表。

双向链表在内存开销上相对于单向链表稍高。

由于有两个指针,插入和删除操作涉及到更多的指针修改,相对于单向链表略微复杂。

单向链表和双向链表的区别

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-nqluhh2h-1690882200224)(E:\Java笔记\数据结构\线形结构\链表结构\链表结构.assets\image-20230801170615367.png)]

单向链表相对于双向链表更简单且节省内存,适用于对内存占用敏感且只需要单向遍历的情况。

而双向链表由于具有双向遍历的能力,适用于需要频繁插入、删除和反向遍历的场景。

在选择使用哪种链表结构时,应根据具体需求权衡其优缺点。

MyList
public interface MyList<E> {
    //添加节点数据
    void add(E element);

    //获取节点数据
    E get (int index);

    //获取链表长度
    int size();

    //根据指针移除节点
    E remove(int index);

    //从头添加元素
    void addFirst(E element);
    
    //从尾添加元素
    void addLast(E element);
}

MyDoubleLinkedList
public class MyDoubleLinkedList<E> implements MyList<E> {

    private int size;//记录元素的个数

    private Node head ;// 记录头节点

    private Node tail;//记录尾节点
    /**
     * 向双向链表中添加元素数据
     * @param element
     */
    @Override
    public void add(E element) {
        this.linkLast(element);
    }

    /**
     * 将节点对象添加到双向链表的尾部
     * @param element
     */
    private void linkLast(E element){
        //获取尾节点
        Node t = this.tail;
        Node<E> node = new Node<>(t,element,null);

        //将新节点定义为尾节点
        this.tail = node;
        if (t == null){//当t等于空的时候说明这个链表是个空链表
            this.head=node;//将向的元素数据赋值到头节点
        }else{
            t.next=node;//否则将新元素赋值到尾节点之后
        }
        this.size++;//添加成功长度自增加一

    }


    /**
     * 根据指针获取对应的元素数据
     * @param index
     * @return
     */
    @Override
    public E get(int index) {
        //对index做合法性校验
        this.rangeCheck(index);
        Node<E> node = this.getNode(index);
        return node.item;
    }

    /**
     * 判断当前index的合法性
     */
    private void rangeCheck(int index){
        if(!(index >=0 && index < this.size)){
            int a = this.size-1;
            throw new IndexOutOfBoundsException("您输入的索引为:"+index+"它的指针长度为:"+a);
        }
    }

    /**
     * 根据位置获取指定的节点对象
     * @param index
     * @return
     */
    private Node getNode(int index){
        //判断当前输入的指针距离头或者尾哪个节点近
        //如果输入的指针大,从尾部开始找,
        //如果输入的指针小,从头部开始找

        if (index < (this.size >> 1)){
            Node node = this.head;
            //遍历指针
            for(int i =0; i < index;i++){
                //拿到指针处的下一个节点对象赋值node
                node=node.next;
            }
            return node;
        }else {
            Node node = this.tail;
            //从尾节点找指针
            for (int i = this.size-1; i>index; i--){
                node = node.prev;
            }
            return node;
        }
    }

    /**
     * 获取元素的长度(个数)
     * @return
     */
    @Override
    public int size() {
        return this.size;
    }

    /**
     * 根据指定指针删除元素
     * @param index
     * @return
     */
    @Override
    public E remove(int index) {
        //对index指针进行合法性校验
        this.rangeCheck(index);

        //根据index进行获取节点对象,判断从头删还是从尾部删除
        Node<E> node = this.getNode(index);

        //获取index指针处的节点元素数据
        E item = node.item;

        //判断当前节点是否尾头节点
        if (node.prev == null){
            this.head = node.next;
        }else {
            //完成当前节点的直接前驱节点和当前节点的直接后继节点,挂接
            node.prev.next = node.next;
        }
        //当前节点断掉与它直接前驱点的连接
        node.prev = null;
        //当前节点断掉与他直接后继节点的连接
        node.next =null;
        node.item =null;

        //长度自减一
        this.size--;

        //返回被删除的节点元素数据
        return item;
    }

    //从头开始添加元素
    @Override
    public void addFirst(E element) {
        this.linkFirst(element);
    }

    //从尾部添加元素
    @Override
    public void addLast(E element) {
        this.linkLast(element);
    }






    //在链表的头添加元素
    private void linkFirst(E element){
        //获取头节点对象
        Node head = this.head;
        Node node = new Node(null,element,head);

        //将新节点定义为头节点
        this.head = node;

        //判断当前链表中是否有节点,如果没有该节则是头节点也是尾节点
        if(this.head == null){
            this.tail = node;
        }else {
            this.head.prev = node;
        }
        this.size++;//记录链表长度

    }

    /**
     * 创建节点类
     * @param <E>
     */
    class Node<E> {
        private E item;//记录元素
        private Node<E> next; // 下一个节点对象
        private Node<E> prev; // 上一个节点对象

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
}

测试
public class MyLinkedMain {
    public static void main(String[] args) {
        MyDoubleLinkedList linkedList = new MyDoubleLinkedList();

        linkedList.add(12);
        linkedList.add(13);
        linkedList.add(14);
        linkedList.add(15);
        linkedList.add(16);
        System.out.println(linkedList.get(3));//3是指针,从尾部开始找
        System.out.println(linkedList.get(4));//4是指针,从尾部开始找
        System.out.println(linkedList.get(1));//1是指针,从头部开始找
        System.out.println(linkedList.size());//获取linkedList长度
        System.out.println("删除前的指针1处的数据"+linkedList.get(1));
        System.out.println(linkedList.remove(1));
        System.out.println("删除后的指针1处的数据"+linkedList.get(1));

        System.out.println("删除前的指针0处的数据"+linkedList.get(4));
        System.out.println(linkedList.remove(4));
        try {
            System.out.println("删除后的指针0处的数据"+linkedList.get(4));

        }catch (Exception e) {
            e.printStackTrace();
        }finally {
            System.out.println("删除后的链表长度"+linkedList.size());//获取linkedList长度
        }
    }
}

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

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

相关文章

Beyond Compare和git merge、git rebase

文章目录 各个分支线将dev1 rebase进 dev2将dev1 merge进dev2 各个分支线 将dev1 rebase进 dev2 gitTest (dev2)]$ git rebase dev1local: 是rebase的分支dev1remote&#xff1a;是当前的分支dev2base&#xff1a;两个分支的最近一个父节点 将dev1 merge进dev2 gitTest (dev…

Qt应用开发(基础篇)——滑块类 Slider、ScrollBar、Dial

一、前言 滑块类QScrollBar、QSlider和QDial继承于QAbstractSlider&#xff0c;父类主要拥有最大值、最小值、步长、当前值、滑块坐标等信息&#xff0c;滑动的时候触发包含值数据变化、滑块按下、滑块释放等信号。键盘包括左/上和右/下箭头键通过定义的singleStep改变当前值&a…

物联网|可变参数的使用技巧|不一样的点灯实验|访问外设的寄存器|操作寄存器实现点灯|硬件编程的基本流程-学习笔记(11)

文章目录 可变参数的使用技巧第三阶段-初级实验Lesson5:不一样的点灯实验---学习I/O的输出 ☆点灯的电路图分析1 一起看看点灯的电路图Tip1:另一种点灯的电路Tip1:如何访问外设的寄存器2 STM32F407中操作GPIO的方法 通过直接操作寄存器实现点灯实验Tip1:硬件编程的基本流程 2代…

SpringBoot(九)jwt + 拦截器实现token验证

前面两篇文章的过滤器和拦截器&#xff0c;我们都提到过可以做诸如权限验证的事情。http/https是无状态的协议&#xff0c;当用户访问一个后端接口时&#xff0c;如何判断该用户有没有权限&#xff1f;当然&#xff0c;可以使用账号密码去验证。但是&#xff0c;如果使用账号和…

统信UOS安装mysql数据库(mariadb)-统信UOS安装JDK-统信UOS安装nginx(附安装包)

统信UOS离线全套安装教程&#xff08;手把手教程&#xff09; 银河麒麟的各种离线全套安装教程&#xff1a; https://blog.csdn.net/ACCPluzhiqi/article/details/131988147 1.统信UOS桌面系统安装mysql&#xff08;mariadb&#xff09; 2.统信UOS桌面系统安装JDK 3.统信UOS桌…

网络出口技术中的单一出口网络结构,你会用吗?

我们在设计一个园区网络的时候&#xff0c;园区网络的出口需要和运营商的网络进行对接&#xff0c;从而提供internet服务。 在和运营商网络对接的时候&#xff0c;一般采用如下3终方式&#xff1a; 单一出口网络结构 1、网络拓扑 终端用户接入到交换机&#xff0c;交换机直…

PostgreSQL-Centos7源码安装

卸载服务器上的pg13 本来是想删除原来的postgis重新源码安装就行,但是yum安装的PostgreSQL不能直接使用,会提示以下问题: 之前服务是用yum安装的,现在需要删除 -- 删除数据的postgis插件 drop extension postgis; drop extension postgis cascade;删除相关安装包 # 查询…

Linux安装操作(Mac版本)

Parallels Desktop的简介 Parallels Desktop是Mac平台上的虚拟机软件&#xff0c;也是Mac平台最好的虚拟机软件之一。它允许用户在Mac OS X系统上同时运行其他操作系统&#xff0c;例如Windows、Linux等。Parallels Desktop为Mac用户提供了使用其他操作系统和软件的便利性&…

shell脚本:使用mysqldump实现分库分表备份

一.什么是分库分表备份 分库分表备份是一种数据库备份策略&#xff0c;用于处理大型数据库系统中的数据分布和备份需求。当数据库的数据量非常大时&#xff0c;单个数据库可能无法满足性能和可扩展性的要求。为了解决这个问题&#xff0c;使用分库分表技术将数据库拆分成多个库…

Centos7 如何用命令直接更改配置文件里面内容

环境&#xff1a; Centos7.7 问题描述&#xff1a; Centos7 如何用命令直接更改配置文件里面内容 ifcfg-bond1文件里面DNS想替换改成114 解决方案&#xff1a; 1.使用sed命令 sed -i -e "s:匹配参数.*:匹配参数替换后的内容:g" 对应的文件路径本案例命令 se…

使用ansible playbook编写lnmp架构

使用ansible playbook编写lnmp架构 - name: nginx playgather_facts: falsehosts: lnmpremote_user: roottasks: - name: stop firewalldservice: namefirewalld statestopped- name: syslinuxcommand: /usr/sbin/setenforce 0ignore_errors: true- name: nginx.repocopy: src/…

Spring Cloud简单记录

1. Spring Cloud是什么 工作这么多年&#xff0c;哈哈。。。没深入理解spring&#xff0c;spring cloud也是没有用过。趁着周末&#xff0c;搞一搞概念&#xff0c;先搞清楚是什么&#xff0c;虽然是什么只有用过之后才能理解的更具体&#xff0c;但是还是需要先整体的熟悉一下…

网站服务器出错的原因分析和解决方法

​  网站在日常运行的过程中&#xff0c;难免会遇见一些问题&#xff0c;这次我们就来分析关于网站服务器出错、服务器异常的原因以及如何解决网站服务器错误的方法。 如何知道是网站服务器的问题呢? 只要网站不能正常访问运行&#xff0c;那么一定会反馈相关的错误代码和原…

3ds Max如何进行合成的反射光泽通道渲染

推荐&#xff1a; NSDT场景编辑器 助你快速搭建可二次开发的3D应用场景 1. 准备场景 步骤 1 打开 3ds Max。smart_phone.max打开已 随教程提供。 打开 3ds Max 步骤 2 按 M 打开材质编辑器。选择空材料 槽。单击漫射通道。它将打开材质/贴图浏览器窗口。选择位图&#xff0…

Ubuntu 离线部署的常见操作

Ubuntu 离线安装的常见操作 **说明&#xff1a;**很多情况下,生产环境都是离线环境&#xff0c;然而开发环境都是互联网的环境&#xff0c;因此部署的过程中需要构建离线安装包; 1. 下载但是不安装 # 例如使用 apt 下载 wireshark 安装包 sudo apt download wireshark # 下载…

【JavaEE】简单了解JVM

目录 一、JVM中的内存区域划分 二、JVM的类加载机制 1、类加载的触发时机 2、双亲委派模型 1.1、向上委派 1.2、向下委派 三、JVM中的垃圾回收机制&#xff08;GC&#xff09; 1、确认垃圾 1.1、引用计数&#xff08;Java实际上没有使用这个方案&#xff0c;但是Pytho…

K8S暴露pod内多个端口

K8S暴露pod内多个端口 一、背景 公司统一用的某个底包跑jar服务&#xff0c;只暴露了8080端口 二、需求 由于有些服务在启动jar服务后&#xff0c;会启动多个端口&#xff0c;除了8080端口&#xff0c;还有别的端口需要暴露&#xff0c;我这里就还需要暴露9999端口。 注&a…

玩转顺序表——【数据结构】

在C语言学习中&#xff0c;我们经常会遇见增删查改等一系列操作&#xff0c;而这些操作全都与线性表关联&#xff0c;没有线性表将会对这些操作完成的十分艰难&#xff01;那今天就让我们来了解一下顺序表如何增删查改&#xff01;&#xff01;&#xff01; 目录 1.线性表 2…

解码“平台工程”,VMware 有备而来

随着全球数字化进程加快&#xff0c;企业使用前沿技术加快商业创新&#xff0c;以提高竞争力。其中如何加快开发效率&#xff0c;为客户创造更多价值成为新的关注焦点。 继DevOps后&#xff0c;“平台工程”&#xff08;Platform Engineering&#xff09; 一词引发热议。平台工…

无涯教程-jQuery - Dialog组件函数

小部件对话框函数可与JqueryUI中的小部件一起使用。对话框是在HTML页面上显示信息的一种不错的方法。对话框是一个带有标题和内容区域的浮动窗口。此窗口可以移动&#xff0c;调整大小&#xff0c;并且默认情况下可以使用" X"图标关闭。 Dialog - 语法 $( "#d…