java中LinkedList源碼分析

ArrayList是動態數組，其實本質就是對數組的操作。
那麼LinkedList實現原理和ArrayList是完全不一樣的。
現在就來分析一下ArrayList和LinkeList的優劣吧
LinkedList是一個雙向鏈表，每個元素都是一個Node對象,
這個node對象裡面有三個成員：
E item;指向實際的元素
Node<E> next;指向下一個節點
Node<E> prev;指向前一個結點

利用idea編輯器查看LinkedList的結構，發現只有三個成員變數。

而所有的public方法操作的都是這個三個變數。
下麵逐個分析方法。

主要就是調用了linkLast方法。

步驟如下：
第一步：l指向尾節點，
第二步：創建新的節點newNode；因為是在鏈表的最後添加元素，所以新節點的next元素為null.
第三步：尾節點指向新的節點
第四步：如果l(之前的尾節點)為空，新節點當作第一個節點
第五步：如果l(之前的尾節點)不為空，則之前的尾節點的next變數指向新節點。
鏈表大小size++;
修改的次數modCount++；

List<String> list=new LinkedList<>();
list.add("a");
list.add("b");

與ArrayList不同，LinkedList記憶體是按需分配的，不需要提前分配記憶體空間，因為操作的不是數組。

get方法

checkElementIndex(index);主要用於檢查參數是否符合規範，沒什麼好說的。

主要看node(index)方法。

index<(size>>1)表示index小於size/2;
如果index索引位於前半部分，從頭開始根據next向後遍歷；
一直找到index-1索引處
如果在後半部分從last處開始根據prev向前遍歷。一直迴圈到index處。
ArrayList中數組是連續存放的，可以根據索引直接定位元素，而LinkedList中，必須從頭或尾順著鏈接查找，所以論查詢效率LinkedList沒有ArrayList效率高；但是在鏈表前或尾添加和刪除的效率倒是比ArrayList要高。

LinkedList還提供了remove,add(int index,E element)，indexOf(Object o)等等這些方法，基本上都是差不多的原理操作的。