LinkedList源碼和并發問題分析

xietao3 發布于2019-08-15 11:58 / 618人閱讀

摘要：在次操作中其實即尾節點是共享資源，當多個線程同時執行此方法的時候，其實會出現線程安全問題。同樣會出現并發安全問題，下面對此問題進行分析。

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的時候都是在鏈表的尾部插入數據，當并發插入的時候如果出現以下執行順序的時候，會出現插入的數據被覆蓋的問題。

當多個線程同時獲取到相同的尾節點的時候，然后多個線程同時在此尾節點后面插入數據的時候會出現數據覆蓋的問題。

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/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