Java集合：LinkedList和Queue

今天我們來探索一下LinkedList和Queue，以及Stack的源碼。

1、LinkedList概述

LinkedList與ArrayList一樣實現(xiàn)List接口昭抒，只是ArrayList是List接口的大小可變數(shù)組的實現(xiàn)瞬矩，LinkedList是List接口鏈表的實現(xiàn)茶鉴。基于鏈表實現(xiàn)的方式使得LinkedList在插入和刪除時更優(yōu)于ArrayList景用，而隨機訪問則比ArrayList遜色些涵叮。LinkedList實現(xiàn)所有可選的列表操作，并允許所有的元素包括null伞插。除了實現(xiàn) List 接口外割粮，LinkedList 類還為在列表的開頭及結(jié)尾 get、remove 和 insert 元素提供了統(tǒng)一的命名方法媚污。這些操作允許將鏈接列表用作堆棧舀瓢、隊列或雙端隊列。此類實現(xiàn) Deque 接口耗美，為 add京髓、poll 提供先進先出隊列操作，以及其他堆棧和雙端隊列操作商架。所有操作都是按照雙重鏈接列表的需要執(zhí)行的堰怨。在列表中編索引的操作將從開頭或結(jié)尾遍歷列表（從靠近指定索引的一端）。同時蛇摸，與ArrayList一樣此實現(xiàn)不是同步的诚些。（以上摘自JDK 6.0 API）。

1.1、定義

首先我們先看LinkedList的定義：

public class LinkedList extends AbstractSequentialList implements List, Deque, Cloneable, java.io.Serializable 從這段代碼中我們可以清晰地看出LinkedList繼承AbstractSequentialList诬烹，實現(xiàn)List砸烦、Deque、Cloneable绞吁、Serializable幢痘。其中AbstractSequentialList提供了 List 接口的骨干實現(xiàn)，從而最大限度地減少了實現(xiàn)受“連續(xù)訪問”數(shù)據(jù)存儲（如鏈接列表）支持的此接口所需的工作,從而以減少實現(xiàn)List接口的復(fù)雜度家破。Deque一個線性 collection颜说，支持在兩端插入和移除元素，定義了雙端隊列的操作汰聋。

1.2门粪、屬性

在LinkedList中提供了兩個基本屬性size、header烹困。

private transient Entry?header = new Entry(null, null, null);

private transient int size = 0;

其中size表示的LinkedList的大小玄妈，header表示鏈表的表頭，Entry為節(jié)點對象髓梅。

private static class Entry { E element; //元素節(jié)點 Entry next; //下一個元素 Entry previous; //上一個元素 Entry(E element, Entry next, Entry previous) { this.element = element; this.next = next; this.previous = previous; } } 上面為Entry對象的源代碼拟蜻，Entry為LinkedList的內(nèi)部類，它定義了存儲的元素枯饿。該元素的前一個元素酝锅、后一個元素，這是典型的雙向鏈表定義方式奢方。

1.3搔扁、構(gòu)造方法

LinkedList提供了兩個構(gòu)造方法：LinkedList()和LinkedList(Collection c)。

/** * 構(gòu)造一個空列表蟋字。 */ public LinkedList() { header.next = header.previous = header; } /** * 構(gòu)造一個包含指定 collection 中的元素的列表阁谆，這些元素按其 collection 的迭代器返回的順序排列。 */ public LinkedList(Collection c) { this(); addAll(c); }

LinkedList()構(gòu)造一個空列表愉老。里面沒有任何元素，僅僅只是將header節(jié)點的前一個元素剖效、后一個元素都指向自身嫉入。

LinkedList(Collection c)： 構(gòu)造一個包含指定 collection 中的元素的列表，這些元素按其 collection 的迭代器返回的順序排列璧尸。該構(gòu)造函數(shù)首先會調(diào)用LinkedList()咒林，構(gòu)造一個空列表，然后調(diào)用了addAll()方法將Collection中的所有元素添加到列表中爷光。以下是addAll()的源代碼：

/** * 添加指定 collection 中的所有元素到此列表的結(jié)尾垫竞，順序是指定 collection 的迭代器返回這些元素的順序。 */ public boolean addAll(Collection c) { return addAll(size, c); } /** * 將指定 collection 中的所有元素從指定位置開始插入此列表。其中index表示在其中插入指定collection中第一個元素的索引 */ public boolean addAll(int index, Collection c) { //若插入的位置小于0或者大于鏈表長度欢瞪，則拋出IndexOutOfBoundsException異常 if (index < 0 || index > size) throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size); Object[] a = c.toArray(); int numNew = a.length; //插入元素的個數(shù) //若插入的元素為空活烙，則返回false if (numNew == 0) return false; //modCount:在AbstractList中定義的，表示從結(jié)構(gòu)上修改列表的次數(shù) modCount++; //獲取插入位置的節(jié)點啸盏，若插入的位置在size處次企，則是頭節(jié)點蛉谜，否則獲取index位置處的節(jié)點 Entry successor = (index == size ? header : entry(index)); //插入位置的前一個節(jié)點狰贯，在插入過程中需要修改該節(jié)點的next引用：指向插入的節(jié)點元素 Entry predecessor = successor.previous; //執(zhí)行插入動作 for (int i = 0; i < numNew; i++) { //構(gòu)造一個節(jié)點e摸柄，這里已經(jīng)執(zhí)行了插入節(jié)點動作同時修改了相鄰節(jié)點的指向引用 // Entry e = new Entry((E) a[i], successor, predecessor); //將插入位置前一個節(jié)點的下一個元素引用指向當(dāng)前元素 predecessor.next = e; //修改插入位置的前一個節(jié)點跃脊，這樣做的目的是將插入位置右移一位橡疼，保證后續(xù)的元素是插在該元素的后面废酷，確保這些元素的順序 predecessor = e; } successor.previous = predecessor; //修改容量大小 size += numNew; return true; } 在addAll()方法中澈蟆，涉及到了兩個方法，一個是entry(int index)卓研，該方法為LinkedList的私有方法趴俘，主要是用來查找index位置的節(jié)點元素。 /** * 返回指定位置(若存在)的節(jié)點元素 */ private Entry entry(int index) { if (index < 0 || index >= size) throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size); //頭部節(jié)點 Entry 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; }

從該方法有兩個遍歷方向中我們也可以看出LinkedList是雙向鏈表奏赘，這也是在構(gòu)造方法中為什么需要將header的前寥闪、后節(jié)點均指向自己。

如果對數(shù)據(jù)結(jié)構(gòu)有點了解磨淌，對上面所涉及的內(nèi)容應(yīng)該問題疲憋，我們只需要清楚一點：LinkedList是雙向鏈表，其余都迎刃而解梁只。

由于篇幅有限缚柳，下面將就LinkedList中幾個常用的方法進行源碼分析。

1.4搪锣、增加方法

add(E e): 將指定元素添加到此列表的結(jié)尾秋忙。 public boolean add(E e) { addBefore(e, header); return true; } 該方法調(diào)用addBefore方法，然后直接返回true构舟，對于addBefore()而已灰追，它為LinkedList的私有方法。 private Entry addBefore(E e, Entry entry) { //利用Entry構(gòu)造函數(shù)構(gòu)建一個新節(jié)點 newEntry狗超， Entry newEntry = new Entry(e, entry, entry.previous); //修改newEntry的前后節(jié)點的引用弹澎，確保其鏈表的引用關(guān)系是正確的 newEntry.previous.next = newEntry; newEntry.next.previous = newEntry; //容量+1 size++; //修改次數(shù)+1 modCount++; return newEntry; }

在addBefore方法中無非就是做了這件事：構(gòu)建一個新節(jié)點newEntry，然后修改其前后的引用抡谐。

LinkedList還提供了其他的增加方法：

add(int index, E element)：在此列表中指定的位置插入指定的元素。 addAll(Collection c)：添加指定 collection 中的所有元素到此列表的結(jié)尾桐猬，順序是指定 collection 的迭代器返回這些元素的順序麦撵。 addAll(int index, Collection c)：將指定 collection 中的所有元素從指定位置開始插入此列表。 AddFirst(E e): 將指定元素插入此列表的開頭。 addLast(E e): 將指定元素添加到此列表的結(jié)尾免胃。

1.5音五、移除方法

remove(Object o)：從此列表中移除首次出現(xiàn)的指定元素（如果存在）。該方法的源代碼如下： public boolean remove(Object o) { if (o==null) { for (Entry e = header.next; e != header; e = e.next) { if (e.element==null) { remove(e); return true; } } } else { for (Entry e = header.next; e != header; e = e.next) { if (o.equals(e.element)) { remove(e); return true; } } } return false; }

該方法首先會判斷移除的元素是否為null羔沙，然后迭代這個鏈表找到該元素節(jié)點躺涝，最后調(diào)用remove(Entry?e)，remove(Entry?e)為私有方法扼雏，是LinkedList中所有移除方法的基礎(chǔ)方法坚嗜，如下：

private E remove(Entry e) { if (e == header) throw new NoSuchElementException(); //保留被移除的元素：要返回 E result = e.element; //將該節(jié)點的前一節(jié)點的next指向該節(jié)點后節(jié)點 e.previous.next = e.next; //將該節(jié)點的后一節(jié)點的previous指向該節(jié)點的前節(jié)點 //這兩步就可以將該節(jié)點從鏈表從除去：在該鏈表中是無法遍歷到該節(jié)點的 e.next.previous = e.previous; //將該節(jié)點歸空 e.next = e.previous = null; e.element = null; size--; modCount++; return result; }

其他的移除方法：

clear()： 從此列表中移除所有元素。 remove()：獲取并移除此列表的頭（第一個元素）诗充。 remove(int index)：移除此列表中指定位置處的元素苍蔬。 remove(Objec o)：從此列表中移除首次出現(xiàn)的指定元素（如果存在）。 removeFirst()：移除并返回此列表的第一個元素蝴蜓。 removeFirstOccurrence(Object o)：從此列表中移除第一次出現(xiàn)的指定元素（從頭部到尾部遍歷列表時）碟绑。 removeLast()：移除并返回此列表的最后一個元素。 removeLastOccurrence(Object o)：從此列表中移除最后一次出現(xiàn)的指定元素（從頭部到尾部遍歷列表時）茎匠。

1.6格仲、查找方法

對于查找方法的源碼就沒有什么好介紹了，無非就是迭代诵冒，比對凯肋，然后就是返回當(dāng)前值。 get(int index)：返回此列表中指定位置處的元素造烁。 getFirst()：返回此列表的第一個元素否过。 getLast()：返回此列表的最后一個元素。 indexOf(Object o)：返回此列表中首次出現(xiàn)的指定元素的索引惭蟋，如果此列表中不包含該元素苗桂，則返回 -1。 lastIndexOf(Object o)：返回此列表中最后出現(xiàn)的指定元素的索引告组，如果此列表中不包含該元素煤伟，則返回 -1。

2木缝、Queue

Queue接口定義了隊列數(shù)據(jù)結(jié)構(gòu)便锨，元素是有序的(按插入順序)，先進先出我碟。Queue接口相關(guān)的部分UML類圖如下：

2.1放案、DeQueue

DeQueue(Double-ended queue)為接口，繼承了Queue接口矫俺，創(chuàng)建雙向隊列吱殉，靈活性更強父款，可以前向或后向迭代富腊，在隊頭隊尾均可心插入或刪除元素。它的兩個主要實現(xiàn)類是ArrayDeque和LinkedList。

2.2所刀、ArrayDeque （底層使用循環(huán)數(shù)組實現(xiàn)雙向隊列）

創(chuàng)建

public ArrayDeque() { // 默認(rèn)容量為16 elements = new Object[16]; } public ArrayDeque(int numElements) { // 指定容量的構(gòu)造函數(shù) allocateElements(numElements); } private void allocateElements(int numElements) { int initialCapacity = MIN_INITIAL_CAPACITY;// 最小容量為8 // Find the best power of two to hold elements. // Tests "<=" because arrays aren't kept full. // 如果要分配的容量大于等于8栅受，擴大成2的冪（是為了維護頭抠刺、尾下標(biāo)值）剑辫；否則使用最小容量8 if (numElements >= initialCapacity) { initialCapacity = numElements; initialCapacity |= (initialCapacity >>> 1); initialCapacity |= (initialCapacity >>> 2); initialCapacity |= (initialCapacity >>> 4); initialCapacity |= (initialCapacity >>> 8); initialCapacity |= (initialCapacity >>> 16); initialCapacity++; if (initialCapacity < 0) // Too many elements, must back off initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements } elements = new Object[initialCapacity]; }

add操作

add(E e) 調(diào)用 addLast(E e) 方法： public void addLast(E e) { if (e == null) throw new NullPointerException("e == null"); elements[tail] = e; // 根據(jù)尾索引，添加到尾端 // 尾索引+1流礁，并與數(shù)組（length - 1）進行取‘&’運算涕俗，因為length是2的冪，所以（length-1）轉(zhuǎn)換為2進制全是1崇棠， // 所以如果尾索引值 tail 小于等于（length - 1）咽袜，那么‘&’運算后仍為 tail 本身；如果剛好比（length - 1）大1時枕稀， // ‘&’運算后 tail 便為0（即回到了數(shù)組初始位置）询刹。正是通過與（length - 1）進行取‘&’運算來實現(xiàn)數(shù)組的雙向循環(huán)。 // 如果尾索引和頭索引重合了萎坷，說明數(shù)組滿了凹联，進行擴容。 if ((tail = (tail + 1) & (elements.length - 1)) == head) doubleCapacity();// 擴容為原來的2倍 } addFirst(E e) 的實現(xiàn)： public void addFirst(E e) { if (e == null) throw new NullPointerException("e == null"); // 此處如果head為0哆档，則-1（1111 1111 1111 1111 1111 1111 1111 1111）與（length - 1）進行取‘&’運算蔽挠，結(jié)果必然是（length - 1），即回到了數(shù)組的尾部瓜浸。 elements[head = (head - 1) & (elements.length - 1)] = e; // 如果尾索引和頭索引重合了澳淑，說明數(shù)組滿了，進行擴容 if (head == tail) doubleCapacity(); }

remove操作

remove()方法最終都會調(diào)對應(yīng)的poll()方法： public E poll() { return pollFirst(); } public E pollFirst() { int h = head; @SuppressWarnings("unchecked") E result = (E) elements[h]; // Element is null if deque empty if (result == null) return null; elements[h] = null; // Must null out slot // 頭索引 + 1 head = (h + 1) & (elements.length - 1); return result; } public E pollLast() { // 尾索引 - 1 int t = (tail - 1) & (elements.length - 1); @SuppressWarnings("unchecked") E result = (E) elements[t]; if (result == null) return null; elements[t] = null; tail = t; return result; }

2.3插佛、PriorityQueue（底層用數(shù)組實現(xiàn)堆的結(jié)構(gòu)）

優(yōu)先隊列跟普通的隊列不一樣杠巡，普通隊列是一種遵循FIFO規(guī)則的隊列，拿數(shù)據(jù)的時候按照加入隊列的順序拿取雇寇。 而優(yōu)先隊列每次拿數(shù)據(jù)的時候都會拿出優(yōu)先級最高的數(shù)據(jù)氢拥。優(yōu)先隊列內(nèi)部維護著一個堆，每次取數(shù)據(jù)的時候都從堆頂拿數(shù)據(jù)（堆頂?shù)膬?yōu)先級最高）锨侯，這就是優(yōu)先隊列的原理嫩海。

add，添加方法

public boolean add(E e) { return offer(e); // add方法內(nèi)部調(diào)用offer方法 } public boolean offer(E e) { if (e == null) // 元素為空的話囚痴，拋出NullPointerException異常 throw new NullPointerException(); modCount++; int i = size; if (i >= queue.length) // 如果當(dāng)前用堆表示的數(shù)組已經(jīng)滿了叁怪，調(diào)用grow方法擴容 grow(i + 1); // 擴容 size = i + 1; // 元素個數(shù)+1 if (i == 0) // 堆還沒有元素的情況 queue[0] = e; // 直接給堆頂賦值元素 else // 堆中已有元素的情況 siftUp(i, e); // 重新調(diào)整堆，從下往上調(diào)整深滚，因為新增元素是加到最后一個葉子節(jié)點 return true; } private void siftUp(int k, E x) { if (comparator != null) // 比較器存在的情況下 siftUpUsingComparator(k, x); // 使用比較器調(diào)整 else // 比較器不存在的情況下 siftUpComparable(k, x); // 使用元素自身的比較器調(diào)整 } private void siftUpUsingComparator(int k, E x) { while (k > 0) { // 一直循環(huán)直到父節(jié)點還存在 int parent = (k - 1) >>> 1; // 找到父節(jié)點索引奕谭，等同于（k - 1）/ 2 Object e = queue[parent]; // 獲得父節(jié)點元素 // 新元素與父元素進行比較耳璧，如果滿足比較器結(jié)果，直接跳出展箱，否則進行調(diào)整 if (comparator.compare(x, (E) e) >= 0) break; queue[k] = e; // 進行調(diào)整，新位置的元素變成了父元素 k = parent; // 新位置索引變成父元素索引蹬昌，進行遞歸操作 } queue[k] = x; // 新添加的元素添加到堆中 }

poll混驰，出隊方法

public E poll() { if (size == 0) return null; int s = --size; // 元素個數(shù)-1 modCount++; E result = (E) queue[0]; // 得到堆頂元素 E x = (E) queue[s]; // 最后一個葉子節(jié)點 queue[s] = null; // 最后1個葉子節(jié)點置空 if (s != 0) siftDown(0, x); // 從上往下調(diào)整，因為刪除元素是刪除堆頂?shù)脑? return result; } private void siftDown(int k, E x) { if (comparator != null) // 比較器存在的情況下 siftDownUsingComparator(k, x); // 使用比較器調(diào)整 else // 比較器不存在的情況下 siftDownComparable(k, x); // 使用元素自身的比較器調(diào)整 } private void siftDownUsingComparator(int k, E x) { int half = size >>> 1; // 只需循環(huán)節(jié)點個數(shù)的一般即可 while (k < half) { int child = (k << 1) + 1; // 得到父節(jié)點的左子節(jié)點索引皂贩，即（k * 2）+ 1 Object c = queue[child]; // 得到左子元素 int right = child + 1; // 得到父節(jié)點的右子節(jié)點索引 if (right < size && comparator.compare((E) c, (E) queue[right]) > 0) // 左子節(jié)點跟右子節(jié)點比較栖榨，取更大的值 c = queue[child = right]; if (comparator.compare(x, (E) c) <= 0) // 然后這個更大的值跟最后一個葉子節(jié)點比較 break; queue[k] = c; // 新位置使用更大的值 k = child; // 新位置索引變成子元素索引，進行遞歸操作 } queue[k] = x; // 最后一個葉子節(jié)點添加到合適的位置 }

remove明刷，刪除隊列元素

public boolean remove(Object o) { int i = indexOf(o); // 找到數(shù)據(jù)對應(yīng)的索引 if (i == -1) // 不存在的話返回false return false; else { // 存在的話調(diào)用removeAt方法婴栽，返回true removeAt(i); return true; } } private E removeAt(int i) { modCount++; int s = --size; // 元素個數(shù)-1 if (s == i) // 如果是刪除最后一個葉子節(jié)點 queue[i] = null; // 直接置空，刪除即可辈末，堆還是保持特質(zhì)愚争，不需要調(diào)整 else { // 如果是刪除的不是最后一個葉子節(jié)點 E moved = (E) queue[s]; // 獲得最后1個葉子節(jié)點元素 queue[s] = null; // 最后1個葉子節(jié)點置空 siftDown(i, moved); // 從上往下調(diào)整 if (queue[i] == moved) { // 如果從上往下調(diào)整完畢之后發(fā)現(xiàn)元素位置沒變，從下往上調(diào)整 siftUp(i, moved); // 從下往上調(diào)整 if (queue[i] != moved) return moved; } } return null; }

先執(zhí)行 siftDown() 下濾過程：

再執(zhí)行 siftUp() 上濾過程：

2.4挤聘、總結(jié)和同步的問題

1轰枝、jdk內(nèi)置的優(yōu)先隊列PriorityQueue內(nèi)部使用一個堆維護數(shù)據(jù)，每當(dāng)有數(shù)據(jù)add進來或者poll出去的時候會對堆做從下往上的調(diào)整和從上往下的調(diào)整组去。

2鞍陨、PriorityQueue不是一個線程安全的類，如果要在多線程環(huán)境下使用从隆，可以使用 PriorityBlockingQueue 這個優(yōu)先阻塞隊列诚撵。其中add、poll键闺、remove方法都使用 ReentrantLock 鎖來保持同步寿烟，take() 方法中如果元素為空，則會一直保持阻塞艾杏。