【数据结构与算法】4、双向链表(学习 jdk 的 LinkedList 部分源码)

这篇具有很好参考价值的文章主要介绍了【数据结构与算法】4、双向链表(学习 jdk 的 LinkedList 部分源码)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、双向链表

【数据结构与算法】4、双向链表(学习 jdk 的 LinkedList 部分源码),数据结构与算法,java,链表,学习

🎁 单链表的节点中只有一个 next 指针引用着下一个节点的地址
🎁 当要获取单链表中的最后一个元素的时候,需要从头节点开始遍历到最后
🎁 单链表一开始的时候有 first 头指针引用着头节点的地址

💰 双向链表可以提升链表的综合性能
💰 双向链表的节点中有 prev 指针引用着一个节点的地址,有 next 指针引用着一个节点的地址
💰 双向链表中一开始的时候有 first 头指针引用着头节点的地址,有 last 尾指针引用着尾节点的地址
💰 ① 当需要获取双向链表靠后的节点【index >= (size / 2)】的时候从尾节点开始遍历;② 当需要获取双向链表靠前的节点【index < (size / 2)】的时候从头节点开始遍历

🎄 头节点的 prev 为 null
🎄 尾节点的 next 为 null

二、node(int index) 根据索引找节点

  /**
   * 根据索引找节点
   */
  private Node<E> node(int index) {
      rangeCheck(index);

      if (index < (index >> 1)) { // 找左边的节点
          Node<E> node = first;
          for (int i = 0; i < index; i++) {
              node = node.next;
          }
          return node;
      } else {
          Node<E> node = last;
          for (int i = size - 1; i > index; i--) {
              node = node.prev;
          }
          return node;
      }
  }

三、clear()

  @Override
  public void clear() {
      size = 0;
      first = null;
      last = null;
  }

只有被【gc root 对象】引用的对象才不会被垃圾回收器回收:

🍃 被栈指针(局部变量)引用的对象是 gc root 对象

【数据结构与算法】4、双向链表(学习 jdk 的 LinkedList 部分源码),数据结构与算法,java,链表,学习

【数据结构与算法】4、双向链表(学习 jdk 的 LinkedList 部分源码),数据结构与算法,java,链表,学习

四、add(int, E)

【数据结构与算法】4、双向链表(学习 jdk 的 LinkedList 部分源码),数据结构与算法,java,链表,学习

🎄 ① 当往索引 0 处插入节点的时候
🎄 ② 当往最后插入节点的时候
🎄 ③ 当一个节点都没有(插入第一个节点)的时候

【数据结构与算法】4、双向链表(学习 jdk 的 LinkedList 部分源码),数据结构与算法,java,链表,学习

【数据结构与算法】4、双向链表(学习 jdk 的 LinkedList 部分源码),数据结构与算法,java,链表,学习

    @Override
    public void add(int index, E element) {
        rangeCheck4Add(index);

        if (size == 0 || (first == null && last == null)) { // 添加第一个节点
            // 新节点的 prev 和 next 都指向 null
            first = new Node<>(element, null, null);
            // 头指针和尾指针都指向新节点
            last = first;
        } else {
            if (index == size) { // 往最后插入新节点
                Node<E> oldLast = last;
                last = new Node<>(element, oldLast, null);
                oldLast.next = last;
            } else {
                // 找到 index 索引处的节点(该节点是新节点的下一个节点)
                Node<E> next = node(index);
                // 前一个节点(假如是往索引为 0 的位置插入节点的话, prev 是 null)
                Node<E> prev = next.prev;

                // 新节点的 prev 指向【前一个节点】
                // 新节点的 next 指向【后一个节点】
                Node<E> newNode = new Node<>(element, prev, next);

                // 后一个节点的 prev 指向新节点
                next.prev = newNode;

                /* 往索引为 0 处插入新节点 */
                if (prev == null) { // 往索引为 0 的位置插入新节点(插入新节点到头节点的位置)
                    first = newNode; // 头指针指向新节点
                } else {
                    // 前一个节点的 next 指向新节点
                    prev.next = newNode;
                }
            }
        }

        size++;
    }

【数据结构与算法】4、双向链表(学习 jdk 的 LinkedList 部分源码),数据结构与算法,java,链表,学习

五、remove(int index)

【数据结构与算法】4、双向链表(学习 jdk 的 LinkedList 部分源码),数据结构与算法,java,链表,学习

自己写的代码(测试成功的):

    @Override
    public E remove(int index) {
        rangeCheck(index);

        // 拿到 index 位置的节点
        Node<E> oldNode = node(index);

        if (index == 0) { // 删除头节点
            // 拿到头节点
            first = oldNode.next;
            first.prev = null;
        } else {
            oldNode.prev.next = oldNode.next;

            if (oldNode.next == null) { // 删除尾节点
                last = oldNode.prev;
            } else {
                oldNode.next.prev = oldNode.prev;
            }
        }

        size--;

        return oldNode.element;
    }

老师的代码:

    @Override
    public E remove(int index) {
        rangeCheck(index);

        Node<E> node = node(index);
        Node<E> prev = node.prev;
        Node<E> next = node.next;

        if (prev == null) { // 删除头节点
            first = next;
        } else {
            prev.next = next;
        }


        if (next == null) { // 删除尾节点
            last = prev;
        } else {
            next.prev = prev;
        }

        size--;

        return node.element;
    }

【数据结构与算法】4、双向链表(学习 jdk 的 LinkedList 部分源码),数据结构与算法,java,链表,学习

六、双向链表和单链表

【数据结构与算法】4、双向链表(学习 jdk 的 LinkedList 部分源码),数据结构与算法,java,链表,学习

🎉 双向链表相比单向链表操作数量缩减一半

七、双向链表和动态数组

🌱 动态数组:开辟、销毁内存空间的次数相对较少但可能造成内存空间浪费(可以通过缩容解决)
🌱 双向链表:开辟、销毁内存空间的次数相对较多(每次添加元素都会创建新的内存空间 ),但不会造成内存空间的浪费

🌿 如果需要频繁在尾部进行添加删除操作,动态数组双向链表 均可选择

  • 动态数组在尾部添加和删除都是 O(1) 级别的
  • 双向链表由于有尾指针 last 的存在,在尾部添加和删除的操作也是 O(1) 级别的

🌿 如果需要频繁在头部进行添加删除操作,建议选择使用 双向链表

  • 动态数组头部的添加和删除操作需要进行大量的元素挪动
  • 双向链表有头指针 first 的存在,在头部进行添加删除操作效率很高

🌿 如果需要频繁地(在任意位置)进行添加删除操作,建议选择使用双向链表

  • 动态数组有最坏情况(假如是在头部添加或删除几乎需要挪动全部元素)
  • 双向链表最多就遍历 n/2 次(n 是元素数量)

🌿 如果有频繁的查询操作(随机访问操作),建议选择使用动态数组

  • 动态数组的随机访问是 O(1) 级别的,通过下标 index 可以直接定位到元素的内存地址
  • 双向链表每次查询都需要遍历,最坏情况要遍历 size 次(size 是元素个数)

❓ 相比单链表,双向链表效率很高。哪有了双向链表,单向链表是否就没有任何用处了呢 ❓
🌿 哈希表的设计中就用到了单链表 😀

八、jdk 官方的 LinkedList 的 clear() 方法

【数据结构与算法】4、双向链表(学习 jdk 的 LinkedList 部分源码),数据结构与算法,java,链表,学习

  • 我学习数据结构与算法的全部代码:https://gitee.com/zgq666good/datastructureandalgorithm.git
  • 学习资料来自于我偶像 ~ 李明杰(小码哥教育)

🌿如有错误,请不吝赐教🌿文章来源地址https://www.toymoban.com/news/detail-520570.html

到了这里,关于【数据结构与算法】4、双向链表(学习 jdk 的 LinkedList 部分源码)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构和算法】使用数组的结构实现链表(单向或双向)

    上文我们通过结构体的结构实现了队列 、以及循环队列的实现,我们或许在其他老师的教学中,只学到了用结构体的形式来实现链表、队列、栈等数据结构,本文我想告诉你的是,我们 可以使用数组的结构实现链表、单调栈、单调队列 目录 前言 一、用数组结构的好处 1.数

    2024年01月20日
    浏览(74)
  • 【数据结构与算法】之双向链表及其实现!

    ​                                                                                 个人主页:秋风起,再归来~                                                                                             数据结构与

    2024年04月23日
    浏览(42)
  • 【数据结构与算法】 - 双向链表 - 详细实现思路及代码

    前几篇文章介绍了怎样去实现单链表、单循环链表, 这篇文章主要介绍 双向链表 以及实现双向链表的步骤,最后提供我自己根据理解实现双向链表的C语言代码 。跟着后面实现思路看下去,应该可以看懂代码,看懂代码后,就对双向链表有了比较抽象的理解了,最后自己再

    2024年02月01日
    浏览(39)
  • 数据结构学习分享之双向链表详解

        💓博主CSDN:杭电码农-NEO💓🎉🎉🎉       ⏩专栏分类:数据结构学习分享(持续更新中🫵)⏪🎉🎉🎉       我们上一期说到,两链表中有两个最常用的结构,一个是最简单的无头不循环单向链表,还有一个就是 结构相对比较复杂的带头双向循环链表 ,我们这一章节就来

    2024年02月04日
    浏览(68)
  • 【数据结构和算法】实现带头双向循环链表(最复杂的链表)

    前文,我们实现了认识了链表这一结构,并实现了无头单向非循环链表,接下来我们实现另一种常用的链表结构,带头双向循环链表。如有仍不了解单向链表的,请看这一篇文章(7条消息) 【数据结构和算法】认识线性表中的链表,并实现单向链表_小王学代码的博客-CSDN博客

    2024年01月17日
    浏览(78)
  • 数据结构模拟实现LinkedList双向不循环链表

    目录 一、双向不循环链表的概念 二、链表的接口 三、链表的方法实现 (1)display方法 (2)size方法 (3)contains方法 (4)addFirst方法 (5)addLast方法 (6)addIndex方法 (7)remove方法 (8)removeAllKey方法 (9)clear方法 四、最终代码 双向不循环链表中的节点有三个域,一个是存

    2024年02月03日
    浏览(41)
  • 数据结构 模拟实现LinkedList双向不循环链表

    目录 一、双向不循环链表的概念 二、链表的接口 三、链表的方法实现 (1)display方法 (2)size方法 (3)contains方法 (4)addFirst方法 (5)addLast方法 (6)addIndex方法 (7)remove方法 (8)removeAllKey方法 (9)clear方法 四、最终代码 双向不循环链表中的节点有三个域,一个是存

    2024年02月03日
    浏览(41)
  • 【数据结构】链表与LinkedList

    作者主页: paper jie 的博客 本文作者:大家好,我是paper jie,感谢你阅读本文,欢迎一建三连哦。 本文录入于《JAVA数据结构》专栏,本专栏是针对于大学生,编程小白精心打造的。笔者用重金(时间和精力)打造,将javaSE基础知识一网打尽,希望可以帮到读者们哦。 其他专栏

    2024年02月08日
    浏览(49)
  • LinkedList数据结构链表

    LinkedList 在Java中是一个实现了 List 和 Deque 接口的双向链表。它允许我们在列表的两端添加或删除元素,同时也支持在列表中间插入或移除元素。在分析 LinkedList 之前,需要理解链表这种数据结构: 链表 :链表是一种动态数据结构,由一系列节点组成,每个节点包含数据部分

    2024年02月20日
    浏览(44)
  • 【数据结构】LinkedList与链表

    上节课已经熟悉了ArrayList的使用,并且进行了简单模拟实现。通过源码知道,ArrayList底层使用数组来存储元素: 由于其底层是一段连续空间,当 在ArrayList任意位置插入或者删除元素时,就需要将后序元素整体往前或者往后搬移,时间复杂度为O(n),效率比较低 ,因此A rrayLi

    2024年02月07日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包