LinkedList 基本示例及源码解析(一)(下)

本文涉及的产品
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
全局流量管理 GTM,标准版 1个月
云解析 DNS,旗舰版 1个月
简介: LinkedList 基本示例及源码解析

五、LinkedList 内部结构以及基本元素声明

  1. LinkedList内部结构是一个双向链表,具体示意图如下
    5.jpg

每一个链表都是一个Node节点,由三个元素组成

private static class Node<E> {
        // Node节点的元素
        E item;
        // 指向下一个元素
        Node<E> next;
        // 指向上一个元素
        Node<E> prev;
        // 节点构造函数
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
}

first 节点也是头节点, last节点也是尾节点

  1. LinkedList 中有三个元素,分别是
transient int size = 0; // 链表的容量
transient Node<E> first; // 指向第一个节点
transient Node<E> last; // 指向最后一个节点
  1. LinkedList 有两个构造函数,一个是空构造函数,不添加任何元素,一种是创建的时候就接收一个Collection集合。
/**
     * 空构造函数
     */
    public LinkedList() {}
    /**
     * 创建一个包含指定元素的构造函数
     */
    public LinkedList(Collection<? extends E> c) {
      this();
      addAll(c);
    }


六、LinkedList 具体源码分析

前言: 此源码是作者根据上面的代码示例一步一步跟进去的,如果有哪些疑问或者讲的不正确的地方,请与作者联系。

添加

添加的具体流程示意图:

6.jpg

包括方法有:

  • add(E e)
  • add(int index, E element)
  • addAll(CollectionE> c)
  • addAll(int index, CollectionE> c)
  • addFirst(E e)
  • addLast(E e)
  • offer(E e)
  • offerFirst(E e)
  • offerLast(E e)

下面对这些方法逐个分析其源码:

add(E e) :

// 添加指定元素至list末尾
    public boolean add(E e) {
          linkLast(e);
          return true;
    }
        // 真正添加节点的操作
    void linkLast(E e) {
      final Node<E> l = last;
        // 生成一个Node节点
      final Node<E> newNode = new Node<>(l, e, null);      last = newNode;
        // 如果l = null,代表的是第一个节点,所以这个节点即是头节点
        // 又是尾节点
      if (l == null)
          first = newNode;
      else
        // 如果不是的话,那么就让该节点的next 指向新的节点
          l.next = newNode;
      size++;
      modCount++;
    }
  1. 比如第一次添加的是111,此时链表中还没有节点,所以此时的尾节点last 为null, 生成新的节点,所以 此时的尾节点也就是111,所以这个 111 也是头节点,再进行扩容,修改次数对应增加
  2. 第二次添加的是 222, 此时链表中已经有了一个节点,新添加的节点会添加到尾部,刚刚添加的111 就当作头节点来使用,222被添加到111的节点后面。

add(int index,E e) :

/**
      *在指定位置插入指定的元素
      */
    public void add(int index, E element) {
        // 下标检查
        checkPositionIndex(index);
        if (index == size)
              // 如果需要插入的位置和链表的长度相同,就在链表的最后添加
            linkLast(element);
        else
              // 否则就链接在此位置的前面
            linkBefore(element, node(index));
    }
        // 越界检查
    private void checkPositionIndex(int index) {
          if (!isPositionIndex(index))
              throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
        // 判断参数是否是有效位置(对于迭代或者添加操作来说)
        private boolean isPositionIndex(int index) {
        return index >= 0 && index <= size;
    }
        // linkLast 上面已经介绍过
        // 查找索引所在的节点
        Node<E> node(int index) {
        // assert isElementIndex(index);
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }
        // 在非空节点插入元素
        void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
          // succ 即是插入位置的节点
            // 查找该位置处的前面一个节点
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }
  1. 例如在位置为1处添加值为123 的元素,首先对下标进行越界检查,判断这个位置是否等于链表的长度,如果与链表长度相同,就往最后插入,如果不同的话,就在索引的前面插入。
  2. 下标为1 处并不等于索引的长度,所以在索引前面插入,首先对查找 1 这个位置的节点是哪个,并获取这个节点的前面一个节点,在判断这个位置的前一个节点是否为null,如果是null,那么这个此处位置的元素就被当作头节点,如果不是的话,头节点的next 节点就指向123

addFirst(E e) :

// 在头节点插入元素
    public void addFirst(E e) {
        linkFirst(e);
    }
    private void linkFirst(E e) {
        // 先找到first 节点
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            // f 为null,也就代表着没有头节点
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }

例如要添加top 元素至链表的首部,需要先找到first节点,如果first节点为null,也就说明没有头节点,如果不为null,则头节点的prev节点是新插入的节点。

addLast(E e) :

/**
        *    在末尾处添加节点
        */
    public void addLast(E e) {
        linkLast(e);
    }
        // 链接末尾处的节点
    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

方法逻辑与在头节点插入基本相同

addAll(Collections c) :

/**
        * 在链表中批量添加数据
        */
    public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }
    public boolean addAll(int index, Collection<? extends E> c) {
               // 越界检查
        checkPositionIndex(index);
          // 把集合转换为数组
        Object[] a = c.toArray();
        int numNew = a.length;
        if (numNew == 0)
            return false;
        Node<E> pred, succ;
          // 直接在末尾添加,所以index = size
        if (index == size) {
            succ = null;
            pred = last;
        } else {
            succ = node(index);
            pred = succ.prev;
        }
          // 遍历每个数组
        for (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o;
              // 先对应生成节点,再进行节点的链接
            Node<E> newNode = new Node<>(pred, e, null);
            if (pred == null)
                first = newNode;
            else
                pred.next = newNode;
            pred = newNode;
        }
        if (succ == null) {
            last = pred;
        } else {
            pred.next = succ;
            succ.prev = pred;
        }
        size += numNew;
        modCount++;
        return true;
    }
Collection<String> collec = Arrays.asList("123","213","321");
list.addAll(collec);
  1. 例如要插入一个Collection为123,213,321 的集合,没有指定插入元素的位置,默认是向链表的尾部进行链接,首先会进行数组越界检查,然后会把集合转换为数组,在判断数组的大小是否为0,为0返回,不为0,继续下面操作
  2. 因为是直接向链尾插入,所以index = size,然后遍历每个数组,首先生成对应的节点,在对节点进行链接,因为succ 是null,此时last 节点 = pred,这个时候的pred节点就是遍历数组完成后的最后一个节点
  3. 然后再扩容数组,增加修改次数

addAll(Collections c) : 这个方法的源码同上

offer也是对元素进行添加操作,源码和add方法相同

offerFirst(E e)和addFirst(E e) 源码相同

offerLast(E e)和addLast(E e) 源码相同)

push(E e) 和addFirst(E e) 源码相同

后记 : 笔者才疏学浅,如果有哪处错误产生误导,请及时与笔者联系更正,一起共建积极向上的it氛围

相关文章
|
索引
LinkedList 基本示例及源码解析(一)(下)
LinkedList 基本示例及源码解析
88 0
LinkedList 基本示例及源码解析(一)(下)
|
存储 安全 程序员
LinkedList 基本示例及源码解析(一)(上)
LinkedList 基本示例及源码解析
88 0
LinkedList 基本示例及源码解析(一)(上)
|
索引
LinkedList 基本示例及源码解析(二)
LinkedList 基本示例及源码解析
60 0
|
7天前
|
存储 人工智能 测试技术
小鱼深度评测 | 通义灵码2.0,不仅可跨语言编码,自动生成单元测试,更炸裂的是集成DeepSeek模型且免费使用,太炸裂了。
小鱼深度评测 | 通义灵码2.0,不仅可跨语言编码,自动生成单元测试,更炸裂的是集成DeepSeek模型且免费使用,太炸裂了。
140671 12
小鱼深度评测 | 通义灵码2.0,不仅可跨语言编码,自动生成单元测试,更炸裂的是集成DeepSeek模型且免费使用,太炸裂了。
|
15天前
|
人工智能 自然语言处理 Shell
深度评测 | 仅用3分钟,百炼调用满血版 Deepseek-r1 API,百万Token免费用,简直不要太爽。
仅用3分钟,百炼调用满血版Deepseek-r1 API,享受百万免费Token。阿里云提供零门槛、快速部署的解决方案,支持云控制台和Cloud Shell两种方式,操作简便。Deepseek-r1满血版在推理能力上表现出色,尤其擅长数学、代码和自然语言处理任务,使用过程中无卡顿,体验丝滑。结合Chatbox工具,用户可轻松掌控模型,提升工作效率。阿里云大模型服务平台百炼不仅速度快,还确保数据安全,值得信赖。
357487 53
深度评测 | 仅用3分钟,百炼调用满血版 Deepseek-r1 API,百万Token免费用,简直不要太爽。
|
6天前
|
人工智能 运维 前端开发
基于阿里百炼的DeepSeek-R1满血版模型调用【零门槛保姆级2084小游戏开发实战】
本文介绍基于阿里百炼的DeepSeek-R1满血版模型调用,提供零门槛保姆级2048小游戏开发实战。文章分为三部分:定位与核心优势、实战部署操作指南、辅助实战开发。通过详细步骤和案例展示,帮助开发者高效利用DeepSeek-R1的强大推理能力,优化游戏逻辑与视觉效果,解决官网响应延迟问题,提升开发效率和用户体验。适合企业开发者、教育行业及多模态探索者使用。
31190 15
|
10天前
|
人工智能 自然语言处理 API
快速使用 DeepSeek-R1 满血版
DeepSeek是一款基于Transformer架构的先进大语言模型,以其强大的自然语言处理能力和高效的推理速度著称。近年来,DeepSeek不断迭代,从DeepSeek-V2到参数达6710亿的DeepSeek-V3,再到性能比肩GPT-4的DeepSeek-R1,每次都带来重大技术突破。其开源策略降低了AI应用门槛,推动了AI普惠化。通过阿里云百炼调用满血版API,用户可以快速部署DeepSeek,享受高效、低成本的云端服务,最快10分钟完成部署,且提供免费token,极大简化了开发流程。
63044 14
快速使用 DeepSeek-R1 满血版
|
7天前
|
人工智能 编解码 算法
DeepSeek加持的通义灵码2.0 AI程序员实战案例:助力嵌入式开发中的算法生成革新
本文介绍了通义灵码2.0 AI程序员在嵌入式开发中的实战应用。通过安装VS Code插件并登录阿里云账号,用户可切换至DeepSeek V3模型,利用其强大的代码生成能力。实战案例中,AI程序员根据自然语言描述快速生成了C语言的base64编解码算法,包括源代码、头文件、测试代码和CMake编译脚本。即使在编译错误和需求迭代的情况下,AI程序员也能迅速分析问题并修复代码,最终成功实现功能。作者认为,通义灵码2.0显著提升了开发效率,打破了编程语言限制,是AI编程从辅助工具向工程级协同开发转变的重要标志,值得开发者广泛使用。
6813 65
DeepSeek加持的通义灵码2.0 AI程序员实战案例:助力嵌入式开发中的算法生成革新
|
12天前
|
机器学习/深度学习 人工智能 自然语言处理
快来零门槛、即刻拥有 DeepSeek-R1 满血版
随着人工智能技术的发展,DeepSeek作为一款新兴推理模型,凭借强大的技术实力和广泛的应用场景崭露头角。本文基于阿里云提供的零门槛解决方案,评测DeepSeek的部署与使用。该方案支持多模态任务,涵盖文本生成、代码补全等,融合NLP、IR和ML技术,提供快速实现AI应用的便利。用户无需编码,最快5分钟、最低0元即可部署DeepSeek模型。阿里云还提供100万免费Token,适合预算有限的个人或小型团队试用。通过Chatbox客户端配置API,用户可轻松体验智能交互功能,如数学提问和代码书写等。
16714 4
|
17天前
|
人工智能 API 网络安全
用DeepSeek,就在阿里云!四种方式助您快速使用 DeepSeek-R1 满血版!更有内部实战指导!
DeepSeek自发布以来,凭借卓越的技术性能和开源策略迅速吸引了全球关注。DeepSeek-R1作为系列中的佼佼者,在多个基准测试中超越现有顶尖模型,展现了强大的推理能力。然而,由于其爆火及受到黑客攻击,官网使用受限,影响用户体验。为解决这一问题,阿里云提供了多种解决方案。
34709 42