2019獨角獸企業重金招聘Python工程師標準>>>

LinkdedList特點

LinkedList是基于鏈表實現的，所以先講解一下什么是鏈表。鏈表原先是C/C++的概念，是一種線性的存儲結構，意思是將要存儲的數據存在一個存儲單元里面，這個存儲單元里面除了存放有待存儲的數據以外，還存儲有其下一個存儲單元的地址（下一個存儲單元的地址是必要的，有些存儲結構還存放有其前一 個存儲單元的地址），每次查找數據的時候，通過某個存儲單元中的下一個存儲單元的地址尋找其后面的那個存儲單元。

LinkedList是一種雙向鏈表，看一下LinkedList的基本存儲單元，它是LinkedList中的一個內部類：

private static class Entry<E> {E element;Entry<E> next;Entry<E> previous;...} 關注點結論

是否允許為空	允許
是否允許重復	允許
是否有序	有序
是否線程安全	非線程安全

LinkdedList底層

添加元素

public class LinkedList<E>extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, java.io.Serializable{private transient Entry<E> header = new Entry<E>(null, null, null);private transient int size = 0;/*** Constructs an empty list.*/public LinkedList() {header.next = header.previous = header;}...}

new了一個Entry出來名為header，Entry里面的previous、element、next都為null，執行構造函數的時候，將 previous和next的值都設置為header的引用地址，還是用畫圖的方式表示。32位JDK的字長為4個字節，而目前64位的JDK一般采用的 也是4字長，所以就以4個字長為單位。header引用地址的字長就是4個字節，假設是0×00000000，那么執行 完”List<String> list = new LinkedList<String>()”之后可以這么表示：

public boolean add(E e) {addBefore(e, header);return true;}private Entry<E> addBefore(E e, Entry<E> entry) {//實例化Entry，值為e，next為entry，previous為entry.previousEntry<E> newEntry = new Entry<E>(e, entry, entry.previous);//新實例化前一個元素的next指向新實例自己newEntry.previous.next = newEntry;//新實例化后一個元素的previous指向新實例自己newEntry.next.previous = newEntry;//鏈表長度加1size++;//采用fast-fail機器modCount++;return newEntry;}

①②③為實例化操作，④⑤為給新實例化前后元素的next/previous指向新實例自己

查看元素

public E get(int index) {return entry(index).element;}private Entry<E> entry(int index) {if (index < 0 || index >= size)throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);Entry<E> e = header;if (index < (size >> 1)) {for (int i = 0; i <= index; i++)e = e.next;} else {for (int i = size; i > index; i--)e = e.previous;}return e;}

這段代碼就體現出了雙向鏈表的好處了。雙向鏈表增加了一點點的空間消耗（每個Entry里面還要維護它的前置Entry的引用），同時也增加了一定的編程復雜度，卻大大提升了效率。

由于LinkedList是雙向鏈表，所以LinkedList既可以向前查找，也可以向后查找，第6行~第12行的作用就是：當index小于數組大小 的一半的時候（size >> 1表示size / 2，使用移位運算提升代碼運行效率），向后查找；否則，向前查找。

這樣，現在數據結構里面有10000個元素，剛巧查找的又是第10000個元素的時候，就不需要從頭遍歷10000次了，向后遍歷即可，一次就能找到我要的元素。

刪除元素

和ArrayList一樣，LinkedList支持按元素刪除和按下標刪除，前者會刪除從頭開始匹配的第一個元素。

public E remove(int index) {return remove(entry(index));}private E remove(Entry<E> e) {if (e == header)throw new NoSuchElementException();E result = e.element;e.previous.next = e.next;e.next.previous = e.previous;e.next = e.previous = null;e.element = null;size--;modCount++;return result;}

第3步、第4步、第5步將待刪除的Entry的previous、element、next都設置為了null，這三步的作用是讓虛擬機可以回收這個Entry。

但是，這個問題我稍微擴展深入一點：按照Java虛擬機HotSpot采用的垃圾回收檢測算法—-根節點搜索算法來說，即使previous、 element、next不設置為null也是可以回收這個Entry的，因為此時這個Entry已經沒有任何地方會指向它了，（tail表示尾部最后一個元素）tail的 previous與header的next都已經變掉了，所以這塊Entry會被當做”垃圾”對待。之所以還要將previous、element、 next設置為null，可能是為了兼容另外一種垃圾回收檢測算法—-引用計數法，這種垃圾回收檢測算法，只要對象之間存在相互引用，那么這塊內存 就不會被當作”垃圾”對待。

插入元素

public void add(int index, E element) {addBefore(element, (index==size ? header : entry(index)));}private Entry<E> addBefore(E e, Entry<E> entry) {Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);newEntry.previous.next = newEntry;newEntry.next.previous = newEntry;size++;modCount++;return newEntry;}

LinkedList和ArrayList的對比

1、順序插入速度ArrayList會比較快。因為ArrayList是基于數組實現的，數組是事先new好的，只要往指定位置塞一個數據就好 了；LinkedList則不同，每次順序插入的時候LinkedList將new一個對象出來，如果對象比較大，那么new的時間勢必會長一點，再加上 一些引用賦值的操作，所以順序插入LinkedList必然慢于ArrayList

2、 LinkedList更適用于存儲較少元素。基于上一點，因為LinkedList里面不僅維護了待插入的元素，還維護了Entry的前置Entry和后繼Entry，如果一個LinkedList中的Entry非常多，那么LinkedList將比ArrayList更耗費一些內存

3、使用各自遍歷效率最高的方式，ArrayList的遍歷效率會比LinkedList的遍歷效率高一些

4、 有些說法認為LinkedList做插入和刪除更快，這種說法其實是不準確的：

（1）LinkedList做插入、刪除的時候，慢在尋址，快在只需要改變前后Entry的引用地址

（2）ArrayList做插入、刪除的時候，慢在數組元素的批量copy，快在尋址

所以，如果待插入、刪除的元素是在數據結構的前半段尤其是非常靠前的位置的時候，LinkedList的效率將大大快過ArrayList，因為 ArrayList將批量copy大量的元素；越往后，對于LinkedList來說，因為它是雙向鏈表，所以在第2個元素后面插入一個數據和在倒數第2 個元素后面插入一個元素在效率上基本沒有差別，但是ArrayList由于要批量copy的元素越來越少，操作速度必然追上乃至超過 LinkedList。

從這個分析看出，如果你十分確定你插入、刪除的元素是在前半段，那么就使用LinkedList；如果你十分確定你刪除、刪除的元素在比較靠后的位置，那 么可以考慮使用ArrayList。如果你不能確定你要做的插入、刪除是在哪兒呢？那還是建議你使用LinkedList吧，因為一來 LinkedList整體插入、刪除的執行效率比較穩定，沒有ArrayList這種越往后越快的情況；二來插入元素的時候，弄得不好ArrayList 就要進行一次擴容，擴容消耗時間又消耗空間。

對LinkedList以及ArrayList的迭代

public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable public class LinkedList<E>extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, java.io.Serializable

注意到ArrayList是實現了RandomAccess接口而LinkedList則沒有實現這個接口，關于RandomAccess這個接口的作用，看一下JDK API上的說法：

public interface RamdomAcess

為此，我寫一段代碼證明一下這一點，注意，雖然上面的例子用的Iterator，但是做foreach循環的時候，編譯器默認會使用這個集合的Iterator，具體可參見foreach循環原理。測試代碼如下：

public class TestMain{private static int SIZE = 111111;private static void loopList(List<Integer> list){long startTime = System.currentTimeMillis();for (int i = 0; i < list.size(); i++){list.get(i);}System.out.println(list.getClass().getSimpleName() + "使用普通for循環遍歷時間為" + (System.currentTimeMillis() - startTime) + "ms");startTime = System.currentTimeMillis();for (Integer i : list){...}System.out.println(list.getClass().getSimpleName() + "使用foreach循環遍歷時間為" + (System.currentTimeMillis() - startTime) + "ms");}public static void main(String[] args){List<Integer> arrayList = new ArrayList<Integer>(SIZE);List<Integer> linkedList = new LinkedList<Integer>();for (int i = 0; i < SIZE; i++){arrayList.add(i);linkedList.add(i);}loopList(arrayList);loopList(linkedList);System.out.println();}} //截取三次運行結果ArrayList使用普通for循環遍歷時間為6msArrayList使用foreach循環遍歷時間為12msLinkedList使用普通for循環遍歷時間為38482msLinkedList使用foreach循環遍歷時間為11msArrayList使用普通for循環遍歷時間為5msArrayList使用foreach循環遍歷時間為12msLinkedList使用普通for循環遍歷時間為43287msLinkedList使用foreach循環遍歷時間為9msArrayList使用普通for循環遍歷時間為4msArrayList使用foreach循環遍歷時間為12msLinkedList使用普通for循環遍歷時間為22370msLinkedList使用foreach循環遍歷時間為5ms

ArrayList優先考慮for循環，LinkedList優先要用foreach

轉載于:https://my.oschina.net/xiaohai945/blog/1052722

總結

以上是生活随笔為你收集整理的LinkdedList的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。