最詳細集合源碼解析之LinkedList集合源碼解析

LinkedList集合特點就是增刪快，查詢慢，這種特性的主要原因就是其內部是通過鏈表來做為存儲數據的數據結構，先看下內部整體結構。

LinkedList整體結構

這裡主可以看到，和ArrayList的繼承結構大致差不多，這裡LinkedList實現了Queue,可以實現一些隊列的操作，先帶大家看下LinkedList的內部的Node內部類的結構，這個是完成數據存儲的核心部分，所有的操作都是圍繞Node來展開的。

<code>   
private
 static 
class
 
Node
<
E
> 
{
        E item; 

        Node next;
        Node prev;

        Node(Node prev, E element, Node next) {
            
this
.item = element;
            
this
.next = next;
            
this
.prev = prev;
        }
    }
/<code>

Node是LinkedList的靜態內部類，主要就是三個變量，一個就是真正要存入的值，一個是是後繼結點，一個是前驅結點，可以看出這是個雙向鏈表，只提供了一個構造函數，完成數據的存儲，可以看出數據結構的精美，幾行代碼就構築了整個LinkedList的基石。

字段屬性

字段屬性

<code> transient Node last;/<code>

<code>     

    
transient
 
int
 size = 
0
;

    
    
transient
 Node first;

  /<code><code>  
/<code>

構造函數解析

<code>     
public
 
LinkedList
(Collection extends E> c)
 
 
{
        
this
();
        addAll(c);
    }
/<code>

傳入一個集合，主要就是通過調用addAll方法來完成數據的插入。

<code> 
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 pred, 

                succ;

        

        
if
 (index == size) {

            succ = 
null
;

            pred = last; 

        }  
else
 {

            

            succ = node(index);

            pred = succ.prev;

        }

        

        
for
 (Object o : a) {

            
(
"unchecked"
) E e = (E) o;

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

    }

/<code>

首先大家想一下，對一個鏈表插入數據需要哪些步驟，回看下我剛剛講解的Node類，存在一個前驅結點，一個後繼結點，所以一個結點要插入到鏈表中，其實就主要兩步，讓插入位置的前驅結點指向新插入的結點，然後讓新節點的後繼結點指向插入位置的後繼結點，這樣就完成了插入，總結一句，那就是斷開再接上這麼個簡單的操作，就好比水管某一段壞了，漏水了，那就把漏水那段給截了，插入新的一段，新的一段再前後連接上就ok了。

addAll方法大致分為兩步，準備數據，然後for循環插入，先看下準備數據階段

• 先將集合轉為數組，再申明兩個Node結點，一個作為前驅結點，一個作為後繼結點，這兩個結點就是要插入位置節點的前驅結點和後繼結點，所以要先找到這兩個結點，然後就可以進行插入了，這裡有個node方法，這個方法就是根據索引位置查找到當前位置的結點。如果要插入的結點是尾節點，那麼succ節點就為空，前驅結點就是當前的尾節點，如果插入的位置不是尾節點，那麼前驅結點就是當前位置結點的前置節點，後繼結點就是當前位置節點

• 找到插入的第一個元素的前驅結點和後繼結點後，就可以進行插入了，通過Node構造方法可知，傳入前驅結點，以及值就能完成數據的構建，這裡什麼傳入的next結點是空呢，這裡你看for循環代碼就可知，因為你是多條數據插入，那麼你的下一個結點會在結點生成後有個pred.next=newNode,是在這裡進行賦值的，每次循環都要將剛生成的結點指向為前驅結點，因為第一個結點是第二個結點的前驅結點，通過這種方式完成數據

  的插入。

get方法

<code>    public E get(
int
 
index
) {
        checkElementIndex(
index
);
        
return
 node(
index
).item;
    }
/<code>

get方法

get方法就是通過node方法根據索引位置查找元素。

<code>
    Node node(
int
 
index
) {
        
//
 assert isElementIndex(
index 
);
        
//index
小於二分之一size
        
if
 (
index
 > 
1
)) {
            Node 
x
 = first;
            
for
 (
int
 i = 
0
; i index
; i++)
                
x
 = x.next;
            
return
 
x
;
        } 
else
 {
            
//index
 大於二分之一
            Node 
x
 = 
last
;
            
for
 (
int
 i = size - 
1
; i > 
index 
; i--)
                
x
 = x.prev;
            
return
 
x
;
        }

    }
/<code>

node方法查找元素用到了二分查找的思想，這樣相對節約點查找時間，查找元素也沒啥快速方法就是通過for循環遍歷找到當前位置的元素，然後返回。

add方法

<code>   
public
 
void
 
add
(
int
 
index
, E element)
 
{
        checkPositionIndex(
index
);
          
        
if 
 (
index
 == size)
            linkLast(element);
        
else

            
            linkBefore(element, node(
index
));
    }
/<code>

add方法

添加元素，首先會進行一個校驗，判斷指定的插入位置是否合規，然後判斷是不是要插入到最後一個位置，如果是就調用linkLast方法，如果不是就調用linkBefore方法。

其實這兩個方法和addAll方法的步驟核心都是差不多的，我們來看看這兩個方法。

<code>    
void
 
linkLast
(E e)
 
{ 

        
        
final
 Node l = last;
        
        
final
 Node newNode = 
new
 Node<>(l, e, 
null
);
        
        last = newNode;
        
        
if
 (l == 
null
)
            first = newNode;
        
else

            
            l.next = newNode;

        

        size++;

        

        modCount++;

    }

/<code>

插入鏈表尾部，那麼尾節點就會作為當前節點的前置節點，然後當前節點就會作為新的尾節點，之前尾節點的next結點是空，現在就要重新指向當前節點。

<code> 
void
 
linkBefore
(E e, Node succ)
 
{
        
        
        
final
 Node pred = succ.prev;
        
        
final
 Node newNode = 
new
 Node<>(pred, e, succ);
        
        succ.prev = newNode;
        
        
if
 (pred == 
null
)
            first = newNode;
        
else
 

            
            pred.next = newNode;

        size++;

        modCount++;

    }

/<code>

linkBefore方法傳入的要插入位置的結點，首先根據該結點找到它的前置節點，這個前置節點將作為要插入節點的前置節點，那麼當前節點就會作為要插入節點的後置節點。

remove方法

remove方法和插入方法其實思路都差不多，只不過一個是插入元素嗎，一個是移除元素，移除元素對於鏈表來說需要哪些步驟呢，其實就是將要移除位置的結點的前置節點的指向和後繼結點的前置節點指向改變一下，聽起來可能有點繞，那就來看下代碼是如何操作的。

<code>    public E remove(
int
 
index
) {
        checkElementIndex(
index
);
        
return
 
unlink
(node(
index
));
    }
/<code>

移除元素調用的就是unlink方法，傳入的參數就是要移除的位置的結點。

<code> 
E 
unlink
(Node x)
 
{
         

        
final
 E element = x.item;
        
final
 Node 
next
 = x.
next
;
        
final
 Node prev = x.prev;

        
if
 (prev == 
null
) {
            first = 
next
;
        } 
else
 {
            prev.
next
 = 
next
;
            x.prev = 
null
;
        }

        
if
 (
next
 == 
null
) {
            last = prev;
        }  
else
 {
            
next
.prev = prev;
            x.
next
 = 
null
;
        }

        x.item = 
null
;
        size



/<code>

這裡首先就是先找到當前節點的前置節點和後繼節點，

然後將前置節點的next節點指向後繼節點，那麼對於後繼結點來說，它的前置節點也要改變，就要指向要移除節點的前置節點，那麼就完成了移除，要移除的結點以及它的前置和後繼索引要置空，方便垃圾回收器進行回收，這樣就完成了徹底的移除。

總結

總結

通過對鏈表源碼的解析可以看到，為什麼鏈表的增刪快，就是因為它不需要向數組那樣去移動元素，只要對當前位置進行操作，省去了移動元素而造成的時間浪費，當然，要找到移除元素的位置是需要時間的，因為要遍歷尋找，這就是為什麼查詢元素相對較慢。