LinkedList源码浅析-阿里云开发者社区

开发者社区> 武汉-万洋> 正文

LinkedList源码浅析

简介: LinkedList使用频率相较`ArrayList`不高,但也值得探讨一下。适合集合高频次修改时采用。
+关注继续查看

前言

LinkedList使用频率相较ArrayList不高,但也值得探讨一下。适合集合高频次修改时采用。

介绍

image-20211022113802124-4873883.png

ArrayList不同,LinkedList是对List和Deque接口的双向链表实现。实现所有可选的列表操作,并允许所有元素(包括null)。 所有操作的执行都与双链接列表的预期一样。索引到列表中的操作将从开始或结束遍历列表,以更接近指定索引的为准。

请注意,此实现是不同步的。如果多个线程同时访问一个链表,并且至少有一个线程在结构上修改链表,则必须在外部对其进行同步。(结构修改是添加或删除一个或多个元素的任何操作;仅设置元素的值不是结构修改。)这通常通过在自然封装列表的某个对象上进行同步来实现。如果不存在此类对象,则应使用Collections.synchronizedList方法“包装”列表。最好在创建时执行此操作,以防止意外不同步地访问列表:

List list = Collections.synchronizedList(new LinkedList(...));

成员变量

    transient int size = 0;

    /**
     * 指向第一个节点的指针
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node<E> first;

    /**
     * 指向加载节点的指针
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node<E> last;

节点

private static class Node<E> {
        // 节点数据
    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;
    }
}

数据结构

双向链表,可以从任一节点向前或者向后遍历。不支持随机访问。

push(E e)

    /**
     * 将元素推送到此列表表示的堆栈上。换句话说,在列表的前面插入元素。 此方法相当于addFirst。
     */
    public void push(E e) {
        addFirst(e);
    }
    /**
     * 在此列表的开头插入指定的元素。
     *
     * @param e the element to add
     */
    public void addFirst(E e) {
        linkFirst(e);
    }
    /**
     * Links e as first element.
     */
    private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }

这里其实就是链表的头插法,新建一个节点指向之前的头节点,之前的头节点向前指向新节点。头指针指向新的节点。

pop()

    /**
     * 从该列表表示的堆栈中弹出一个元素。换句话说,删除并返回此列表的第一个元素。 此方法等效于removeFirst()
     */
    public E pop() {
        return removeFirst();
    }
    /**
     * 从此列表中删除并返回第一个元素。
     */
    public E removeFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }
    /**
     * Unlinks non-null first node f.
     */
    private E unlinkFirst(Node<E> f) {
        // assert f == first && f != null;
        final E element = f.item;
        final Node<E> next = f.next;
        f.item = null;
        f.next = null; // help GC
        first = next;
        if (next == null)
            last = null;
        else
            next.prev = null;
        size--;
        modCount++;
        return element;
    }

push相反,pop弹出头节点,头指针指向头节点的下一个节点,下一个节点向前指向null

结尾

这里只是把LinkedList的核心数据结构指出,其他方法也都是对于双向链表的常规操作,读者可自行了解。

关于作者

我叫无涯,一位热爱coding的coder。更多文章在我的个人博客:oneyoung.top 。让我们一起进步。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
Flink1.7.2 Dataset 并行计算源码分析
- 了解Flink处理流程(用户程序 -> JobGrapth -> ExecutionGraph -> JobVertex -> ExecutionVertex -> 并行度 -> Task(DataSourceTask,BatchTask,DataSinkTask) - 了解Execution...
1556 0
LinkedHashMap源码分析(基于JDK1.6)
LinkedHashMap类似于HashMap,但是迭代遍历它时,取得“键值对”的顺序是插入次序,或者是最近最少使用(LRU)的次序。只比HashMap慢一点;而在迭代访问时反而更快,因为它使用链表维护内部次序(HashMap是基于散列表实现的,相关HashMap的内容可以看《Java集合类》和《HashMap源码分析》)。
575 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
4620 0
使用OpenApi弹性释放和设置云服务器ECS释放
云服务器ECS的一个重要特性就是按需创建资源。您可以在业务高峰期按需弹性的自定义规则进行资源创建,在完成业务计算的时候释放资源。本篇将提供几个Tips帮助您更加容易和自动化的完成云服务器的释放和弹性设置。
8268 0
零基础学Java系列二:23节视频课+源码解析简单Java类 | 开发者进阶站
刚入门的你是不是想要“窥探”更多Java的秘密,那就快来吧,用范例带你轻松学Java!
742 0
Flink1.7.2 Dataset 文件切片计算方式和切片数据读取源码分析
了解读取的文件或目录,具体进行切片拆分的实现 了解任务读取切片中的数据规则
1141 0
spring源码学习之:xml标签扩展配置例子
在很多情况下,我们需要为系统提供可配置化支持,简单的做法可以直接基于Spring的标准Bean来配置,但配置较为复杂或者需要更多丰富控制的 时候,会显得非常笨拙。一般的做法会用原生态的方式去解析定义好的xml文件,然后转化为配置对象,这种方式当然可以解决所有问题,但实现起来比较繁琐, 特别是是在配置非常复杂的时候,解析工作是一个不得不考虑的负担。
870 0
9
文章
0
问答
来源圈子
更多
阿里云GTS能力中心(浩鲸智能),从交付的视角探讨数字化转型过程中大型软件开发实践、以及阿里云产品在各行业被集成的案例分享、技术沉淀等内容。敬请关注!
+ 订阅
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载