最详细集合源码解析之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节点指向后继节点，那么对于后继结点来说，它的前置节点也要改变，就要指向要移除节点的前置节点，那么就完成了移除，要移除的结点以及它的前置和后继索引要置空，方便垃圾回收器进行回收，这样就完成了彻底的移除。

总结

总结

通过对链表源码的解析可以看到，为什么链表的增删快，就是因为它不需要向数组那样去移动元素，只要对当前位置进行操作，省去了移动元素而造成的时间浪费，当然，要找到移除元素的位置是需要时间的，因为要遍历寻找，这就是为什么查询元素相对较慢。