LinkedList源码和并发问题分析

xietao3 发布于2019-08-15 11:58 / 612人阅读

摘要：在次操作中其实即尾节点是共享资源，当多个线程同时执行此方法的时候，其实会出现线程安全问题。同样会出现并发安全问题，下面对此问题进行分析。

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 item;
        Node next;
        Node prev;

        Node(Node prev, E element, Node next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

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

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

 transient Node first;
 transient Node last;

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

1.3 关键方法源码分析

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

  void linkLast(E e) {
      //保存链表插入之前的最后一个节点
      final Node l = last;
      //将新节点的preNode指向链表最后一个节点
      final Node 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 succ) {
       // assert succ != null;
       final Node pred = succ.prev;
       //新建节点，并将preNode指向idnex-1节点
       final Node 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的时候都是在链表的尾部插入数据，当并发插入的时候如果出现以下执行顺序的时候，会出现插入的数据被覆盖的问题。

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

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/67637.html

Java 常用List集合使用场景分析

摘要：常用集合使用场景分析过年前的最后一篇，本章通过介绍，，，底层实现原理和四个集合的区别。和都是线程安全的，不同的是前者使用类，后者使用关键字。面试官会认为你是一个基础扎实，内功深厚的人才到这里常用集合使用场景分析就结束了。 Java 常用List集合使用场景分析过年前的最后一篇，本章通过介绍ArrayList，LinkedList，Vector，CopyOnWriteArrayList...

godruoyi 2019-08-16 11:03 评论0 收藏0
LinkedList 基本示例及源码解析

摘要：对于不可修改的列表来说，程序员需要实现列表迭代器的和方法介绍这个接口也是继承类层次的核心接口，以求最大限度的减少实现此接口的工作量，由顺序访问数据存储例如链接链表支持。一、JavaDoc 简介 LinkedList双向链表，实现了List的双向队列接口，实现了所有list可选择性操作，允许存储任何元素(包括null值) 所有的操作都可以表现为双向性的，遍历的时候会从首部到尾部进行...

senntyou 2019-08-16 16:22 评论0 收藏0
【备战春招/秋招系列】美团Java面经总结进阶篇（附详解答案）

摘要：我在前面的文章中也提到了应该怎么做自我介绍与项目介绍，详情可以查看这篇文章备战春招秋招系列初出茅庐的程序员该如何准备面试。因此基于事件消息对象驱动的业务架构可以是一系列流程。 showImg(https://user-gold-cdn.xitu.io/2018/11/14/16711ac29c2ae52c?w=928&h=531&f=png&s=798562); 一消息队列MQ的...

chengjianhua 2019-08-16 13:41 评论0 收藏0
这几道Java集合框架面试题在面试中几乎必问

摘要：若遇到哈希冲突，则将冲突的值加到链表中即可。之后相比于之前的版本，之后在解决哈希冲突时有了较大的变化，当链表长度大于阈值默认为时，将链表转化为红黑树，以减少搜索时间。有序，唯一红黑树自平衡的排序二叉树。本文是最最最常见Java面试题总结系列第三周的文章。主要内容： Arraylist 与 LinkedList 异同 ArrayList 与 Vector 区别 HashMap的底层...

bigdevil_s 2019-08-19 11:01 评论0 收藏0
学习Java Collection Framework的Iterator实现

摘要：源码，由于的结构并不是顺序的，在执行方法时不能通过指针或下标的方式直接找到下一个元素，为了能达到这个目的，在构造函数和方法中预先做了处理。继续研读JDK的源码，在比较HashMap和ConcurrentHashMap的不同之处发现了一个细节——关于Iterator的实现的不同，其实HashMap和ConcurrentHashMap还有更多不同的地方，这也是面试经常问到的问题，有一篇文...

VPointer 2019-08-16 12:31 评论0 收藏0