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

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


一、双向链表

🎁 单链表的节点中只有一个 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 对象

四、add(int, E)

🎄 ① 当往索引 0 处插入节点的时候

🎄 ② 当往最后插入节点的时候

🎄 ③ 当一个节点都没有(插入第一个节点)的时候

@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++;
    }

五、remove(int index)

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

@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;
    }

六、双向链表和单链表

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

七、双向链表和动态数组

🌱 动态数组:开辟、销毁内存空间的次数相对较少但可能造成内存空间浪费(可以通过缩容解决)

🌱 双向链表:开辟、销毁内存空间的次数相对较多(每次添加元素都会创建新的内存空间 ),但不会造成内存空间的浪费

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

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

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

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

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

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

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

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

❓ 相比单链表,双向链表效率很高。哪有了双向链表,单向链表是否就没有任何用处了呢 ❓

🌿 哈希表的设计中就用到了单链表 😀

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

🌿如有错误,请不吝赐教🌿

相关文章
|
3月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
324 9
|
27天前
|
负载均衡 算法
架构学习:7种负载均衡算法策略
四层负载均衡包括数据链路层、网络层和应用层负载均衡。数据链路层通过修改MAC地址转发帧;网络层通过改变IP地址实现数据包转发;应用层有多种策略,如轮循、权重轮循、随机、权重随机、一致性哈希、响应速度和最少连接数均衡,确保请求合理分配到服务器,提升性能与稳定性。
189 11
架构学习:7种负载均衡算法策略
|
2月前
|
机器学习/深度学习 前端开发 算法
婚恋交友系统平台 相亲交友平台系统 婚恋交友系统APP 婚恋系统源码 婚恋交友平台开发流程 婚恋交友系统架构设计 婚恋交友系统前端/后端开发 婚恋交友系统匹配推荐算法优化
婚恋交友系统平台通过线上互动帮助单身男女找到合适伴侣,提供用户注册、个人资料填写、匹配推荐、实时聊天、社区互动等功能。开发流程包括需求分析、技术选型、系统架构设计、功能实现、测试优化和上线运维。匹配推荐算法优化是核心,通过用户行为数据分析和机器学习提高匹配准确性。
157 3
|
3月前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
数据结构与算法系列学习之串的定义和基本操作、串的储存结构、基本操作的实现、朴素模式匹配算法、KMP算法等代码举例及图解说明;【含常见的报错问题及其对应的解决方法】你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
|
3月前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
144 16
|
3月前
|
搜索推荐 算法 C语言
【排序算法】八大排序(下)(c语言实现)(附源码)
本文继续学习并实现了八大排序算法中的后四种:堆排序、快速排序、归并排序和计数排序。详细介绍了每种排序算法的原理、步骤和代码实现,并通过测试数据展示了它们的性能表现。堆排序利用堆的特性进行排序,快速排序通过递归和多种划分方法实现高效排序,归并排序通过分治法将问题分解后再合并,计数排序则通过统计每个元素的出现次数实现非比较排序。最后,文章还对比了这些排序算法在处理一百万个整形数据时的运行时间,帮助读者了解不同算法的优劣。
188 7
|
3月前
|
搜索推荐 算法 C语言
【排序算法】八大排序(上)(c语言实现)(附源码)
本文介绍了四种常见的排序算法:冒泡排序、选择排序、插入排序和希尔排序。通过具体的代码实现和测试数据,详细解释了每种算法的工作原理和性能特点。冒泡排序通过不断交换相邻元素来排序,选择排序通过选择最小元素进行交换,插入排序通过逐步插入元素到已排序部分,而希尔排序则是插入排序的改进版,通过预排序使数据更接近有序,从而提高效率。文章最后总结了这四种算法的空间和时间复杂度,以及它们的稳定性。
150 8
|
3月前
|
C语言
【数据结构】二叉树(c语言)(附源码)
本文介绍了如何使用链式结构实现二叉树的基本功能,包括前序、中序、后序和层序遍历,统计节点个数和树的高度,查找节点,判断是否为完全二叉树,以及销毁二叉树。通过手动创建一棵二叉树,详细讲解了每个功能的实现方法和代码示例,帮助读者深入理解递归和数据结构的应用。
203 8
|
3月前
|
机器学习/深度学习 人工智能 自然语言处理
【EMNLP2024】基于多轮课程学习的大语言模型蒸馏算法 TAPIR
阿里云人工智能平台 PAI 与复旦大学王鹏教授团队合作,在自然语言处理顶级会议 EMNLP 2024 上发表论文《Distilling Instruction-following Abilities of Large Language Models with Task-aware Curriculum Planning》。
|
3月前
|
存储 Java 索引
Java中的数据结构:ArrayList和LinkedList的比较
【10月更文挑战第28天】在Java编程世界中,数据结构是构建复杂程序的基石。本文将深入探讨两种常用的数据结构:ArrayList和LinkedList,通过直观的比喻和实例分析,揭示它们各自的优势与局限,帮助你在面对不同的编程挑战时做出明智的选择。