JDK源碼分析（4）之 LinkedList 相關(guān)

一、定義

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

從類定義和圖中也能很清晰的看到，LinkedList的結(jié)構(gòu)大致分為三個部分；同時和ArrayList相比，他并沒有實現(xiàn)RandomAccess接口，所以他并不支持隨機訪問操作；另外可以看到他的List接口是通過AbstractSequentialList實現(xiàn)的，同時還實現(xiàn)了多個迭代器，表明他的訪問操作時通過迭代器完成的。

二、鏈表結(jié)構(gòu)

常見鏈表

LinkedList是基于雙向循環(huán)鏈表實現(xiàn)的，所以如圖所示，當對鏈表進行插入、刪除等操作時，

• 首先需要區(qū)分操作節(jié)點是否為首尾節(jié)點，并區(qū)分是否為空，

• 然后再變更相應pre和next的引用即可；

void?linkFirst(E?e)void?linkLast(E?e)void?linkBefore(E?e,?Node<E>?succ)E?unlinkFirst(Node<E>?f)E?unlinkLast(Node<E>?l)E?unlink(Node<E>?x)/**
?*?Returns?the?(non-null)?Node?at?the?specified?element?index.
?*/Node<E>?node(int?index)?{??//?assert?isElementIndex(index);
??if?(index?<?(size?>>?1))?{
????Node<E>?x?=?first;????for?(int?i?=?0;?i?<?index;?i++)
??????x?=?x.next;????return?x;
??}?else?{
????Node<E>?x?=?last;????for?(int?i?=?size?-?1;?i?>?index;?i--)
??????x?=?x.prev;????return?x;
??}
}

上面所列的方法封裝了對雙向循環(huán)鏈表常用操作，其中node(int index)是隨機查詢方法，這里通過判斷index是前半段還是后半段，來確定遍歷的方向以增加效率。
同時在LinkedList中有關(guān)List和Deque的API也是基于上面的封裝的方法完成的。具體代碼比較簡單，就不挨著分析了。

三、序列化和反序列化

transient?int?size?=?0;transient?Node<E>?first;transient?Node<E>?last;

可以看到LinkedList的成員變量都是用transient修飾的，那么在序列化的時候，他是怎么將包含的dada序列化的呢？

private?void?writeObject(java.io.ObjectOutputStream?s)?throws?java.io.IOException?{??//?Write?out?any?hidden?serialization?magic
??s.defaultWriteObject();??
??//?Write?out?size
??s.writeInt(size);??
??//?Write?out?all?elements?in?the?proper?order.
??for?(Node<E>?x?=?first;?x?!=?null;?x?=?x.next)
????s.writeObject(x.item);
}private?void?readObject(java.io.ObjectInputStream?s)?throws?java.io.IOException,?ClassNotFoundException?{??//?Read?in?any?hidden?serialization?magic
??s.defaultReadObject();??
??//?Read?in?size
??int?size?=?s.readInt();??
??//?Read?in?all?elements?in?the?proper?order.
??for?(int?i?=?0;?i?<?size;?i++)
????linkLast((E)s.readObject());
}

可以看到序列化的時候是將size和node中的data提取出來，放入java.io.ObjectInputStream，這樣就避免了很多結(jié)構(gòu)性的數(shù)據(jù)傳輸。

四、遍歷

關(guān)于LinkedList的遍歷這里有一個經(jīng)常都會踩的坑需要注意一下。

1. 隨機訪問

for?(int?i=0,?len?=?list.size();?i?<?len;?i++)?{
?String?s?=?list.get(i);
}

1. 迭代器遍歷

Iterator?iter?=?list.iterator();while?(iter.hasNext())?{
?String?s?=?(String)iter.next();
}

1. 增強for循環(huán)遍歷

for?(String?s?:?list)?{
?...
}

1. 效率測試

對一個LinkedList做順序遍歷：

這里可以明顯的看增強for循環(huán)和迭代器的效率差不多，這是因為增強for循環(huán)也是通過迭代器實現(xiàn)的，具體可以查看我在ArrayList章節(jié)的分析；但是隨機訪問的方式遍歷，耗時在急劇增加，這是為什么呢？

public?E?get(int?index)?{
??checkElementIndex(index);??return?node(index).item;
}

這里可以看到get(int index)是使用node(int index)實現(xiàn)的，所以對于迭代器和增強for循環(huán)遍歷時間復雜度是O(n)，而使用隨機訪問的方式遍歷時間復雜度則是O(n*n)；所以在對LinkedList遍歷的時候一定不能采用隨機訪問的方式。建議直接使用增強for循環(huán)遍歷，如果一定要使用隨機訪問則需要判斷是否實現(xiàn)RandomAccess接口。

五、插入和刪除

網(wǎng)上一般都在說LinkedList比ArrayList的插入和刪除快，因為ArryList基于數(shù)組，需要移動后續(xù)元素，而LinkedList則只需要修改兩條引用；但是實際如何呢？

private?static?final?Random?RANDOM?=?new?Random();private?static?List<String>?getList(List<String>?list,?int?n)?{??for?(int?i?=?0;?i?<?n;?i++)?{
????list.add("a"?+?i);
??}??return?list;
}private?static?long?test(List<String>?list,?int?count)?{??long?start?=?System.currentTimeMillis();??for?(int?i?=?0;?i?<?count;?i++)?{
????list.add(RANDOM.nextInt(list.size()),?i?+?"");
????list.remove(RANDOM.nextInt(list.size()));
??}??return?System.currentTimeMillis()?-?start;
}public?static?void?main(String[]?args)?{??int[]?tt?=?{1000,?10000,?50000};??
??for?(int?t?:?tt)?{
????List<String>?linked?=?getList(new?LinkedList<>(),?t);
????List<String>?array?=?getList(new?ArrayList<>(),?t);
????System.out.println("------------"?+?t);
????System.out.println("--linked:?"?+?test(linked,?t));
????System.out.println("--array:"?+?test(array,?t));
??}
}

這里只是簡單測試一下，如果需要精確結(jié)果可以使用JMH基準測試，
這里是對長度為 n 的 List，進行隨機插入和刪除 n 次，結(jié)果如下：

如果只是在 List 的首尾插入和刪除呢，測試結(jié)果如下：

根據(jù)測試結(jié)果：

• 對于隨機插入和刪除，LinkedList效率低于ArrayList；主要是因為LinkedList遍歷定位的時候比較慢，而ArrayList是基于數(shù)組，可以通過偏移量直接定位，并且ArrayList在插入和刪除時，移動數(shù)組是通過System.arraycopy完成的，jvm 有做特殊優(yōu)化，效率比較高。

• 對于首尾的插入和刪除，LinkedList效率高于ArrayList，這里因為LinkedList只需要插入刪除一個節(jié)點就可以，但ArrayList需要移動數(shù)組，同時可能還需要擴容操作，所以比較慢。

總結(jié)

• LinkedList 基于雙向循環(huán)鏈表實現(xiàn)，隨機訪問比較慢，所以在遍歷 List 的時候一定要注意。

• LinkedList 可以添加重復元素，可以添加 null。