LinkedList源码和并发问题分析

1.LinkedList源码分析

LinkedList的是基于链表实现的java集合类,通过index插入到指定位置的时候使用LinkedList效率要比ArrayList高,以下源码分析是基于JDK1.8.

1.1 类的继承结构

LinkedList类的继承结构如如下所示:

从以上继承结构图中可以看到,最顶层接口为Iterable接口,实现此接口的类支持通过迭代器遍历集合中的元素。其他相关接口如Collection、List、Queue、Deque分别为列表,队列功能的相关接口,即此LinkedList支持列表、队列的相关操作。Serializable接口为序列化标志接口,即所有需要序列化的类都需要实现此接口。

1.2 LinkedList数据结构说明

首先我们来看下LinkedList中保存数据的内部类定义源码如下:

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

通过以上定义可以看出来每个节点中除了保存元素的值之外还保存了前后节点的引用。即使用了链表的数据接口保存数据元素。数据结构如下图所示:

在LinkedList类中,只是定义了两个Node类型的属性,定义如下:

 transient Node<E> first;
 transient Node<E> last;

这两个属性分别表示头节点和尾节点,始终指向链表的第一个节点和最后一个节点。

1.3 关键方法源码分析

当不指定index往LinkedList中添加元素的时候默认是在链表的尾部添加数据,源代码如下

  void linkLast(E e) {
      //保存链表插入之前的最后一个节点
      final Node<E> l = last;
      //将新节点的preNode指向链表最后一个节点
      final Node<E> newNode = new Node<>(l, e, null);
      last指向插入后的尾节点
      last = newNode;
      if (l == null)
          //当第一次插入数据的时候,头节点和尾节点指向同一个节点
          first = newNode;
      else
          //插入之前的尾节点的nextNode指向新插入的节点
          l.next = newNode;
      size++;
      modCount++;
  }

插入节点的详细操作如上面代码注释。在次操作中其实last即尾节点是共享资源,当多个线程同时执行此方法的时候,其实会出现线程安全问题。具体的线程安全问题后面分析。

当指定index插入数据的时候,源代码如下所示:

public void add(int index, E element) {
       checkPositionIndex(index);

       if (index == size)
           linkLast(element);
       else
           linkBefore(element, node(index));
   }

在指定index插入元素的时候会先查询出index位置的元素,然后调用linkBefore将此元素插入到查询到的元素的前一个位置。其中linkBefore源码如下所示:

void linkBefore(E e, Node<E> succ) {
       // assert succ != null;
       final Node<E> pred = succ.prev;
       //新建节点,并将preNode指向idnex-1节点
       final Node<E> newNode = new Node<>(pred, e, succ);
       //插入前的index节点的prev指向新节点
       succ.prev = newNode;
       if (pred == null)
           first = newNode;
       else
          //index-1节点的nextNode指向新节点
           pred.next = newNode;
       size++;
       modCount++;
   }

在指定节点插入的方式如上注释所示。此操作中共享资源是插入之前index节点。同样会出现并发安全问题,下面对此问题进行分析。

2.LinkedList并发插入时节点覆盖的问题

在指定index插入或者addLast的时候都是在链表的尾部插入数据,当并发插入的时候如果出现以下执行顺序的时候,会出现插入的数据被覆盖的问题。

当多个线程同时获取到相同的尾节点的时候,然后多个线程同时在此尾节点后面插入数据的时候会出现数据覆盖的问题。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏linux驱动个人学习

C++转换构造函数与类型转换构造函数

转换构造函数:  转换构造函数的只有一个形参: 1 Student(float s) 2 { 3 score = s; 4 age = 0; ...

2744
来自专栏ImportSource

一分钟告诉你java final 关键字运行原理

final关键字究竟是怎么运行的? 这是一个非常有趣的问题, import java.util.ArrayList; import java.util.List...

3498
来自专栏Java帮帮-微信公众号-技术文章全总结

【选择题】Java基础测试二(15道)

【选择题】Java基础测试二(15道) 11.对于构造方法,下列叙述正确的是:(AC) A. 构造方法的方法名必须与类名相同; B. 构造方法必须用void...

36010
来自专栏Java爬坑系列

【JAVA零基础入门系列】Day7 Java输入与输出

  本篇主要介绍Java的输入与输出,当然,这里说的是控制台下的输入与输出,窗口程序的设计将会再后续篇章中有详细说明。     Java的输出很简单,调用Sys...

1989
来自专栏性能与架构

轻松掌握ES6中集合Set的用法

前言 Set 是 ES6 中新的对象类型,用来创建一个唯一值的集合 Set 中的值可以是简单的基本类型,例如字符串、数字,也可以是复杂的类型,例如数组、对象 基...

2107
来自专栏流媒体

STL(一)vector、set/multiset、listVectorSetmultisetlist

vector封装数组,list封装了链表,map和set封装了二叉树等。set关联式容器。set作为一个容器也是用来存储同一数据类型的数据类型,并且能从一个数据...

762
来自专栏Android干货

Python对象相关内置函数

判断一个变量是否是某些类型中的一种,比如下面的代码就可以判断是否是list或者tuple:

533
来自专栏云霄雨霁

查找----基于无序链表

1280
来自专栏武培轩的专栏

快手2018春招后端笔试题解

计算(x^y)%N 题目描述 计算(x^y)%N 注:(x^y)表示x的y次方 输入描述: 每个测试用例一行 每行为空格隔开的 int64_t 类型,分别对应x...

3485
来自专栏前端杂货铺

类型转换的判定方式

对于“==”,我们肯定不陌生,但是背后的判定机制我们可能不是很熟悉,我现在先举一些例子,最后再总结一下大概的方法: null == undefined // ...

3277

扫码关注云+社区