在JDK1.7之前，LinkedList是采用雙向環形鏈表來實現的，在1.7及之后，Oracle將LinkedList做了優化，將環形鏈表改成了線性鏈表。本文對于LinkedList的源碼分析基于JDK1.8。

LinkedList既然是通過一個雙向線性鏈表來實現，那么肯定就能夠很輕易的找到鏈表的第一個節點和最后一個節點，在源碼中可以看到有這兩個字段：

transient Node<E> first; // 鏈表第一個節點 transient Node<E> last; // 鏈表最后一個節點復制代碼

先來看一下什么是節點Node：

private static class Node<E> {E item;Node<E> next;Node<E> prev;Node(Node<E> prev, E element, Node<E> next) {this.item = element;this.next = next;this.prev = prev;} }復制代碼

節點Node中有三個成員：

• item ： 存儲的元素
• next ： 下一個節點
• prev ： 上一個節點

節點中保存有需要存儲的元素，同時持有上一個節點和下一個節點的引用，各個節點依次持有前后節點的引用就形成了一個鏈，這樣，當我們需要查找鏈中某一個節點保存的元素時，只需要通過第一個節點或者最后一個節點依次查找，就可以找到我們需要的節點。

需要注意的是，在JDK1.7及之后，第一個節點first的前一個節點prev為null，最后一個節點last的后一個節點next也為null。而在JDK1.6及之前，頭節點header是一個不保存元素的節點，header的下一個節點next是第一個元素節點，而header的上一個節點是最后一個元素節點，這樣使得它形成一個環形的雙向鏈表。

LinkedList節點結構圖1（JDK1.7及以后）
LinkedList節點結構圖2（JDK1.6及以前）

LinkedList的構造函數有兩個，一個無參，另一個可以傳入一個集合：

public LinkedList() { }public LinkedList(Collection<? extends E> c) {this();addAll(c); }復制代碼

看下addAll方法的實現：

public boolean addAll(Collection<? extends E> c) {return addAll(size, c); }public boolean addAll(int index, Collection<? extends E> c) {// 檢查是否越界checkPositionIndex(index);// 將集合c轉化為數組aObject[] a = c.toArray();int numNew = a.length;if (numNew == 0)return false;// pred為插入元素位置點前一個節點，succ為插入元素位置的后一個節點Node<E> pred, succ; if (index == size) { // index==size的話，在鏈表的末尾添加元素succ = null;pred = last;} else { // 否則的話，從鏈表中間加入succ = node(index);pred = succ.prev;}// 遍歷需要加入的元素數組afor (Object o : a) { // 通過元素o構造一個節點Node@SuppressWarnings("unchecked") E e = (E) o;Node<E> newNode = new Node<>(pred, e, null);if (pred == null) // 插入位置的前一個節點為null，說明需要插入的是first節點first = newNode;else // 插入位置的前一個節點不為null，即從鏈表中或鏈表末尾插入// 將要插入的節點復制給插入位置的上一個節點的nextpred.next = newNode;// 將newNode賦值給下個需要插入的節點的predpred = newNode;}if (succ == null) { // succ為null，說明是從末尾添加的元素，將添加的最后一個元素賦值給lastlast = pred;} else { // 從鏈表中某個位置添加的，重新連接上添加元素時斷開的引用鏈pred.next = succ;succ.prev = pred;}// 更新鏈表的大小size += numNew;modCount++;return true; }復制代碼

在構造方法中調用addAll方法，相當于是向一個空鏈表中添加集合c中的元素。

如果是在已有元素的鏈表中調用addAll方法來添加元素的話，就需要判斷指定的添加位置index是否越界，如果越界會拋出異常；如果沒有越界，根據添加的位置index，斷開鏈表中index位置的節點前后的引用，加入新元素，重新連上斷開位置的前后節點的引用。過程如下圖：

LinkedList加入元素1
LinkedList加入元素2

add方法:

public boolean add(E e) {linkLast(e);return true; }復制代碼

直接就調用了linkLast方法，說明默認的add方法是直接將元素添加到已有的鏈表的末尾。

void linkLast(E e) {final Node<E> l = last;final Node<E> newNode = new Node<>(l, e, null);last = newNode;if (l == null)first = newNode;elsel.next = newNode;size++;modCount++; }復制代碼

新加入元素的節點賦值給last節點，然后判斷了一下加入之前的last節點是否為空，為空的話，說明鏈表中沒有元素，新加入的就是鏈表的first節點；不為空直接將之前的最后一個節點的next引用添加的節點即可。

還有一個add方法，指定了添加位置：

public void add(int index, E element) {checkPositionIndex(index);if (index == size)linkLast(element);elselinkBefore(element, node(index)); }復制代碼

先判斷是否越界，在判斷添加的位置是否在已有鏈表的末尾，如果在末尾就直接添加到末尾，不在末尾的話，調用linkBefore添加到index位置的節點之前。

void linkBefore(E e, Node<E> succ) {// assert succ != null;final Node<E> pred = succ.prev;final Node<E> newNode = new Node<>(pred, e, succ);succ.prev = newNode;if (pred == null)first = newNode;elsepred.next = newNode;size++;modCount++; }復制代碼

pred為null的話，說明succ是添加元素前鏈表的first節點，加入元素e，更新first節點，并更改引用鏈。

addFirst和addLast方法中分別調用了linkFirst方法和linkLast方法：

private void linkFirst(E e) {final Node<E> f = first;final Node<E> newNode = new Node<>(null, e, f);first = newNode;if (f == null)last = newNode;elsef.prev = newNode;size++;modCount++; }void linkLast(E e) {final Node<E> l = last;final Node<E> newNode = new Node<>(l, e, null);last = newNode;if (l == null)first = newNode;elsel.next = newNode;size++;modCount++; }復制代碼

linkFirst/linkLast方法即是將新節點添加到鏈表的頭部或者尾部，更新鏈表的prev和next引用。

remove方法：

public boolean remove(Object o) {if (o == null) {for (Node<E> x = first; x != null; x = x.next) {if (x.item == null) {unlink(x);return true;}}} else {for (Node<E> x = first; x != null; x = x.next) {if (o.equals(x.item)) {unlink(x);return true;}}}return false; }復制代碼

不管需要移除的元素O是否為空，都是遍歷后調用unlink方法來刪除節點，繼續看unlink方法：

E unlink(Node<E> x) {// assert x != null;final E element = x.item;final Node<E> next = x.next;final Node<E> prev = x.prev;if (prev == null) {// 如果prev為null的話，那么刪除的是first節點，將next指定為刪除后的first節點first = next;} else {// prev不為null，將prev的next引用指向next，并解除x元素對prev的引用prev.next = next;x.prev = null;}if (next == null) {// 如果next為null，那么刪除的是last節點，將prev指定為刪除后的last節點last = prev;} else {// next不為null，將next的prev引用指向prev，并解除x的next引用next.prev = prev;x.next = null;}// 置空x節點中的元素x.item = null;size--;modCount++;return element; }復制代碼

removeFirst和removeLast方法同樣是直接調用了unlinkFirst和unlinkLast，實現和unlink差不多，不做過多解釋。

set方法，set方法即修改鏈表中指定位置的元素：

public E set(int index, E element) {checkElementIndex(index);Node<E> x = node(index);E oldVal = x.item;x.item = element;return oldVal; }復制代碼

找到指定位置的節點x，更改該節點的item屬性就行了。

獲取節點的node方法：

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;} }復制代碼

判斷位置index是靠近頭部還是尾部，靠近頭部，則從first節點往后遍歷，靠近尾部則從last節點往前遍歷，這種方式可以使得鏈表查找的時候遍歷次數不會超過鏈表長度的一半，從而提升查找效率。

get、getFirst、getLast方法：

public E get(int index) {checkElementIndex(index);return node(index).item; }public E getFirst() {final Node<E> f = first;if (f == null)throw new NoSuchElementException();return f.item; }public E getLast() {final Node<E> l = last;if (l == null)throw new NoSuchElementException();return l.item; }復制代碼

getFirst和getLast直接后去first和last節點中的元素值，get方法則直接調用了node方法，不再解釋。

LinkedList源碼中的其他方法不再分析了，實現都很容易理解。從LinkedList的增、刪、改、查等方法的實現邏輯可以看出來，LinkedList的增和刪效率相對于改和查要高，因為每次修改和查詢都要從鏈表的頭節點或尾節點開始遍歷，而增加和刪除，只需要在制定位置斷開節點引用，添加和刪除元素后，重新連上引用鏈即可。所以，LinkedList適合用在添加和刪除比較頻繁，而修改和查詢較少的情況下。

總結

以上是生活随笔為你收集整理的Java类集框架 —— LinkedList源码分析的全部內容，希望文章能夠幫你解決所遇到的問題。

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