LinkedList實作原理以及源碼解析（1.7）

在1.7之後，oracle将LinkedList做了一些優化，将1.6中的環形結構優化為了直線型了連結清單結構。

1、LinkedList定義：

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

LinkedList 是一個繼承于AbstractSequentialList的雙向連結清單。它也可以被當作堆棧、隊列或雙端隊列進行操作。

LinkedList 實作 List 接口，能對它進行隊列操作。

LinkedList 實作 Deque 接口，即能将LinkedList當作雙端隊列使用。

LinkedList 實作了Cloneable接口，即覆寫了函數clone()，能克隆。

LinkedList 實作java.io.Serializable接口，這意味着LinkedList支援序列化，能通過序列化去傳輸。

LinkedList 是非同步的。如果多個線程同時通路一個連結清單，而其中至少一個線程從結構上修改了該清單，則它必須保持外部同步。（結構修改指添加或删除一個或多個元素的任何操作；僅設定元素的值不是結構修改。）這一般通過對自然封裝該清單的對象進行同步操作來完成。如果不存在這樣的對象，則應該使用 Collections.synchronizedList 方法來“包裝”該清單。List list = Collections.synchronizedList(new LinkedList(...));擷取線程安全的list。

AbstractSequentialList 實作了get(int index)、set(int index, E element)、add(int index, E element) 和 remove(int index)這些骨幹性函數。降低了List接口的複雜度。這些接口都是随機通路List的，LinkedList是雙向連結清單；既然它繼承于AbstractSequentialList，就相當于已經實作了“get(int index)這些接口”。

我們若需要通過AbstractSequentialList自己實作一個清單，隻需要擴充此類，并提供 listIterator() 和 size() 方法的實作即可。若要實作不可修改的清單，則需要實作清單疊代器的 hasNext、next、hasPrevious、previous 和 index 方法即可。

2、資料結構：

雙向連結清單，存在一種資料結構——我們可以稱之為節點，節點執行個體儲存業務資料，前一個節點的位置資訊和後一個節點位置資訊。

節點與節點之間相連，構成了我們LinkedList的基本資料結構，也是LinkedList的核心。

LinkedList實作原理以及源碼解析（1.7）

3、LinkedList的構造方法

transient int size = 0;

    /**
     * Pointer to first node.
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node<E> first;


    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node<E> last;

LinkedList包含3個全局參數，

size存放目前連結清單有多少個節點。

first為指向連結清單的第一個節點的引用。

last為指向連結清單的最後一個節點的引用。

LinkedList構造方法有兩個，一個是無參構造，一個是傳入Collection對象的構造。

無參構造為空實作。有參構造傳入Collection對象，将對象轉為數組，并按周遊順序将數組首尾相連，全局變量first和last分别指向這個連結清單的第一個和最後一個。

// 什麼都沒做，是一個空實作
	public LinkedList() {
	}

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

	public boolean addAll(Collection<? extends E> c) {
		return addAll(size, c);
	}


	public boolean addAll(int index, Collection<? extends E> c) {
		// 檢查傳入的索引值是否在合理範圍内
		checkPositionIndex(index);
		// 将給定的Collection對象轉為Object數組
		Object[] a = c.toArray();
		int numNew = a.length;
		// 數組為空的話，直接傳回false
		if (numNew == 0)
			return false;
		// 數組不為空
		Node<E> pred, succ;
		if (index == size) {
			// 構造方法調用的時候，index = size = 0，進入這個條件。
			succ = null;
			pred = last;
		} else {
			// 連結清單非空時調用，node方法傳回給定索引位置的節點對象
			succ = node(index);
			pred = succ.prev;
		}
		// 周遊數組，将數組的對象插入到節點中
		for (Object o : a) {
			@SuppressWarnings("unchecked")
			E e = (E) o;
			Node<E> newNode = new Node<>(pred, e, null);
			if (pred == null)
				first = newNode;
			else
				pred.next = newNode;
			pred = newNode;
		}


		if (succ == null) {
			last = pred; // 将目前連結清單最後一個節點指派給last
		} else {
			// 連結清單非空時，将斷開的部分連接配接上
			pred.next = succ;
			succ.prev = pred;
		}
		// 記錄目前節點個數
		size += numNew;
		modCount++;
		return true;
	}

Node是LinkedList的内部私有類，它的組成很簡單，隻有一個構造方法。

Node節點一共有三個屬性：item代表節點值，prev代表節點的前一個節點，next代表節點的後一個節點。

構造方法的參數順序是：前繼節點的引用，資料，後繼節點的引用。

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;  
		}  
	}

4、LinkedList方法分析

addFirst/addLast：

public void addFirst(E e) {  
		linkFirst(e);  
	}  
	  
	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;  
		else  
			f.prev = newNode;  
		size++;  
		modCount++;  
	}

加入一個新的節點，看方法名就能知道，是在現在的連結清單的頭部加一個節點，既然是頭結點，那麼頭結點的前繼必然為null，是以這也是Node<E> newNode = new Node<>(null, e, f);這樣寫的原因。

之後将first指向了目前連結清單的頭結點，之後對之前的頭節點進行了判斷，若在插入元素之前頭結點為null，則目前加入的元素就是第一個幾點，也就是頭結點，是以目前的狀況就是：頭結點=剛剛加入的節點=尾節點。若在插入元素之前頭結點不為null，則證明之前的連結清單是有值的，那麼我們隻需要把新加入的節點的後繼指向原來的頭結點，而尾節點則沒有發生變化。這樣一來，原來的頭結點就變成了第二個節點了。達到了我們的目的。

addLast方法在實作上是個addFirst是一緻的，這裡就不在贅述了。有興趣的朋友可以看看源代碼。

其實，LinkedList中add系列的方法都是大同小異的，都是建立新的節點，改變之前的節點的指向關系。

getFirst/getLast方法分析

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;  
	}

add方法：

public boolean add(E e) {
		linkLast(e);
		return true;
	}

	void linkLast(E e) {
		final Node<E> l = last;//連結清單最後一個節點
		final Node<E> newNode = new Node<>(l, e, null);//建立節點對象，前一個（perv屬性）是last，後一個（next屬性）是null，中間item資料是輸入的參數e
		last = newNode;
		if (l == null)
			first = newNode; //如果最後一個節點 為null表示連結清單為空，則添加資料時将新加的資料作為第一個節點
		else
			l.next = newNode; //如果連結清單不為空則将最後一個連結清單的next屬性指向新添加的節點
		size++; //連結清單長度自增1
		modCount++;
	}


	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;
		}
	}

LInkedList添加操作時每個新添加的對象都會被放到建立的Node對象中，Node對象中包含加入的對象和前後指針屬性（pred和next，pred和next其實都是Node對象，直接存放的就是目前對象的前一個節點對象和後一個節點對象，最後一個及節點的next值為null），然後将原來最後一個last節點的next指針指向新加入的對象。

get方法：

public E get(int index) {  
		// 校驗給定的索引值是否在合理範圍内  
		checkElementIndex(index);  
		return node(index).item;  
	}  
	  
	Node<E> node(int 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;  
		}  
	}

判斷給定的索引值，若索引值大于整個連結清單長度的一半，則從後往前找，若索引值小于整個連結清單的長度的一般，則從前往後找。這樣就可以保證，不管連結清單長度有多大，搜尋的時候最多隻搜尋連結清單長度的一半就可以找到，大大提升了效率。

removeFirst/removeLast方法：

public E removeFirst() {  
		final Node<E> f = first;  
		if (f == null)  
			throw new NoSuchElementException();  
		return unlinkFirst(f);  
	}  
	  
	private E unlinkFirst(Node<E> f) {  
		// assert f == first && f != null;  
		final E element = f.item;  
		final Node<E> next = f.next;  
		f.item = null;  
		f.next = null; // help GC  
		first = next;  
		if (next == null)  
			last = null;  
		else  
			next.prev = null;  
		size--;  
		modCount++;  
		return element;  
	}

摘掉頭結點，将原來的第二個節點變為頭結點，改變frist的指向，若之前僅剩一個節點，移除之後全部置為了null。

addAll操作：

public boolean addAll(int index, Collection<? extends E> c) {
		checkPositionIndex(index);//判斷index是否越界，越界則抛出異常
		Object[] a = c.toArray();//轉成數組
		int numNew = a.length;//要插入的集合的長度
		if (numNew == 0)
			return false;
		Node<E> pred, succ;//聲明pred和succ兩個Node對象，用于辨別要插入元素的前一個節點和最後一個節點
		if (index == size) { //如果size等于原數組長度則表示在結尾添加
			succ = null;
			pred = last;
		} else {
			succ = node(index);//index位置上的Node對象
			pred = succ.prev;
		}
		for (Object o : a) { //周遊要插入的集合
			@SuppressWarnings("unchecked") E e = (E) o;
			Node<E> newNode = new Node<>(pred, e, null);
			if (pred == null)
				first = newNode; //如果要插入的位置的前一個節點為null表示是第一個節點，則直接将newNode賦給第一個節點
			else
				pred.next = newNode; //将要插入的集合元素節點對象賦給此位置原節點對象的前一個對象的後一個，即更改前一個節點對象的next指針指到新插入的節點上
			pred = newNode;//更改指向後将新節點對象賦給pred作為下次循環中新插入節點的前一個對象節點，依次循環
		}
		//此時pred代表集合元素的插入完後的最後一個節點對象
		if (succ == null) { //結尾添加的話在添加完集合元素後将最後一個集合的節點對象pred作為last
			last = pred;
		} else {
			pred.next = succ;//将集合元素的最後一個節點對象的next指針指向原index位置上的Node對象
			succ.prev = pred;//将原index位置上的pred指針對象指向集合的最後一個對象
		}
		size += numNew;
		modCount++;
		return true;
	}

LinkedList在某個位置插入元素是通過将原位置節點的前一個節點的後一個指針指向新插入的元素，然後将原位置的節點的前一個指針指向新元素來實作的，相當于插入元素後後面的元素後移了，但是不是像ArrayList那樣将所有插入位置後面的元素都後移，此處隻是改變其前後節點的指向。

5、addAll函數集合參數轉數組：

在addAll函數中，傳入一個集合參數和插入位置，然後将集合轉化為數組，然後再周遊數組，挨個添加數組的元素，為什麼要先轉化為數組再進行周遊，而不是直接周遊集合呢？

這樣是為了避免在putAll過程中Collection的内容又發生了改變。除了多線程外，還有一種可能是，你傳入的Collection的内容又間接依賴了正在被putAll的list。

1. 如果直接周遊集合的話，那麼在周遊過程中需要插入元素，在堆上配置設定記憶體空間，修改指針域，這個過程中就會一直占用着這個集合，考慮正确同步的話，其他線程隻能一直等待。

2. 如果轉化為數組，隻需要周遊數組，而周遊集合過程中不需要額外的操作，是以占用的時間相對是較短的，這樣就利于其他線程盡快的使用這個集合。

說白了，就是有利于提高多線程通路該集合的效率，盡可能短時間的阻塞。

6、總結：

1：LinkedList的實作是基于雙向循環連結清單，實作的 List和Deque 接口。實作所有可選的清單操作，并允許所有元素（包括null）。

2：LinkedList是非線程安全的，隻在單線程下适合使用。

3：這個類的iterator和傳回的疊代器listIterator方法是fail-fast ，要注意ConcurrentModificationException 。

4：LinkedList實作了Serializable接口，是以它支援序列化，能夠通過序列化傳輸，實作了Cloneable接口，能被克隆。

5:在查找和删除某元素時，都分為該元素為null和不為null兩種情況來處理，LinkedList中允許元素為null。

6：由于是基于清單的，LinkedList的沒有擴容方法！預設加入元素是尾部自動擴容！

7：LinkedList還實作了棧和隊列的操作方法，是以也可以作為棧、隊列和雙端隊列來使用，如peek 、push、pop等方法。

8：LinkedList是基于連結清單實作的，是以插入删除效率高，查找效率低！（因為查找需要周遊整個連結清單）

9：LinkedList和ArrayList一樣實作了List接口，但是它執行插入和删除操作時比ArrayList更加高效，因為它是基于連結清單的。基于連結清單也決定了它在随機通路方面要比ArrayList遜色一點。

10：LinkedList繼承了 AbstractSequentialList抽象類，而不是像 ArrayList和 Vector那樣實作 AbstractList，實際上，java類庫中隻有 LinkedList繼承了這個抽象類，正如其名，它提供了對序列的連續通路的抽象

參考資料:

JDK API LinkedList

LinkedList 源代碼

java源碼分析之LinkedList

深入Java集合學習系列：LinkedList的實作原理

http://blog.csdn.net/seu_calvin/article/details/53012654

每天努力一點，每天都在進步。

LinkedList實作原理以及源碼解析（1.7）

繼續閱讀

【從源碼看Android】01從Looper說起

JUC ThreadLocal源碼行級解析 JDK8前言标準示例類定義成員變量initialValuewithInitial與靜态内部類SuppliedThreadLocalget與setInitialValue與getMapset與removecreateInheritedMap與childValueThreadLocalMap靜态内部類

ArrayBlockingQueue源碼解析（JDK1.8）

HashSet源碼解析(JDK1.8)

JDK8：HashMap源碼解析：treeifyBin方法

JDK8：HashMap源碼解析：resize方法

JDK8：HashMap源碼解析：hash方法

CoordinatorLayout源碼解析

LevelDB源碼解析(2) SkipList(跳躍表)

吃透Java集合系列四：LinkedList

jvm-sanbox詳解--彙總篇

JAVA學習.JAVA集合類型Collection.List.ArrayList&LinkedList

原生Mybatis架構源碼解析

Mybatis源碼解析《一》

MyBatis源碼解析（二）：初始化SqlSessionFactory