這篇文章主要講解了“Java集合的Queue和LinkedList怎么使用”，文中的講解內(nèi)容簡單清晰，易于學(xué)習(xí)與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學(xué)習(xí)“Java集合的Queue和LinkedList怎么使用”吧！
奇臺(tái)ssl適用于網(wǎng)站、小程序/APP、API接口等需要進(jìn)行數(shù)據(jù)傳輸應(yīng)用場景，ssl證書未來市場廣闊！成為創(chuàng)新互聯(lián)的ssl證書銷售渠道，可以享受市場價(jià)格4-6折優(yōu)惠！如果有意向歡迎電話聯(lián)系或者加微信：18980820575（備注：SSL證書合作）期待與您的合作！
LinkedList與ArrayList一樣實(shí)現(xiàn)List接口，只是ArrayList是List接口的大小可變數(shù)組的實(shí)現(xiàn)，LinkedList是List接口鏈表的實(shí)現(xiàn)?；阪湵韺?shí)現(xiàn)的方式使得LinkedList在插入和刪除時(shí)更優(yōu)于ArrayList，而隨機(jī)訪問則比ArrayList遜色些。
LinkedList實(shí)現(xiàn)所有可選的列表操作，并允許所有的元素包括null。
除了實(shí)現(xiàn) List 接口外，LinkedList 類還為在列表的開頭及結(jié)尾 get、remove 和 insert 元素提供了統(tǒng)一的命名方法。這些操作允許將鏈接列表用作堆棧、隊(duì)列或雙端隊(duì)列。
此類實(shí)現(xiàn) Deque 接口，為 add、poll 提供先進(jìn)先出隊(duì)列操作，以及其他堆棧和雙端隊(duì)列操作。
所有操作都是按照雙重鏈接列表的需要執(zhí)行的。在列表中編索引的操作將從開頭或結(jié)尾遍歷列表（從靠近指定索引的一端）。
同時(shí)，與ArrayList一樣此實(shí)現(xiàn)不是同步的。
首先我們先看LinkedList的定義：
public class LinkedListextends AbstractSequentialList implements List , Deque , Cloneable, java.io.Serializable 從這段代碼中我們可以清晰地看出LinkedList繼承AbstractSequentialList，實(shí)現(xiàn)List、Deque、Cloneable、Serializable。其中AbstractSequentialList提供了 List 接口的骨干實(shí)現(xiàn)，從而最大限度地減少了實(shí)現(xiàn)受“連續(xù)訪問”數(shù)據(jù)存儲(chǔ)（如鏈接列表）支持的此接口所需的工作,從而以減少實(shí)現(xiàn)List接口的復(fù)雜度。Deque一個(gè)線性 collection，支持在兩端插入和移除元素，定義了雙端隊(duì)列的操作。
在LinkedList中提供了兩個(gè)基本屬性size、header。
private transient Entry
private transient int size = 0;
其中size表示的LinkedList的大小，header表示鏈表的表頭，Entry為節(jié)點(diǎn)對象。
private static class Entry{ E element; //元素節(jié)點(diǎn) Entry next; //下一個(gè)元素 Entry previous; //上一個(gè)元素 Entry(E element, Entry next, Entry previous) { this.element = element; this.next = next; this.previous = previous; } } 上面為Entry對象的源代碼，Entry為LinkedList的內(nèi)部類，它定義了存儲(chǔ)的元素。該元素的前一個(gè)元素、后一個(gè)元素，這是典型的雙向鏈表定義方式。
LinkedList提供了兩個(gè)構(gòu)造方法：LinkedList()和LinkedList(Collection c)。
重慶分公司
重慶分公司
/**
* 構(gòu)造一個(gè)空列表。
*/
public LinkedList() {
header.next = header.previous = header;
}
/**
* 構(gòu)造一個(gè)包含指定 collection 中的元素的列表，這些元素按其 collection 的迭代器返回的順序排列。
*/
public LinkedList(Collection c) {
this();
addAll(c);
}LinkedList()構(gòu)造一個(gè)空列表。里面沒有任何元素，僅僅只是將header節(jié)點(diǎn)的前一個(gè)元素、后一個(gè)元素都指向自身。
LinkedList(Collection c)： 構(gòu)造一個(gè)包含指定 collection 中的元素的列表，這些元素按其 collection 的迭代器返回的順序排列。該構(gòu)造函數(shù)首先會(huì)調(diào)用LinkedList()，構(gòu)造一個(gè)空列表，然后調(diào)用了addAll()方法將Collection中的所有元素添加到列表中。以下是addAll()的源代碼：
/**
* 添加指定 collection 中的所有元素到此列表的結(jié)尾，順序是指定 collection 的迭代器返回這些元素的順序。
*/
public boolean addAll(Collection c) {
return addAll(size, c);
}
/**
* 將指定 collection 中的所有元素從指定位置開始插入此列表。其中index表示在其中插入指定collection中第一個(gè)元素的索引
*/
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; //插入元素的個(gè)數(shù)
//若插入的元素為空，則返回false
if (numNew == 0)
return false;
//modCount:在AbstractList中定義的，表示從結(jié)構(gòu)上修改列表的次數(shù)
modCount++;
//獲取插入位置的節(jié)點(diǎn)，若插入的位置在size處，則是頭節(jié)點(diǎn)，否則獲取index位置處的節(jié)點(diǎn)
Entry successor = (index == size ? header : entry(index));
//插入位置的前一個(gè)節(jié)點(diǎn)，在插入過程中需要修改該節(jié)點(diǎn)的next引用：指向插入的節(jié)點(diǎn)元素
Entry predecessor = successor.previous;
//執(zhí)行插入動(dòng)作
for (int i = 0; i < numNew; i++) {
//構(gòu)造一個(gè)節(jié)點(diǎn)e，這里已經(jīng)執(zhí)行了插入節(jié)點(diǎn)動(dòng)作同時(shí)修改了相鄰節(jié)點(diǎn)的指向引用
//
Entry e = new Entry((E) a[i], successor, predecessor);
//將插入位置前一個(gè)節(jié)點(diǎn)的下一個(gè)元素引用指向當(dāng)前元素
predecessor.next = e;
//修改插入位置的前一個(gè)節(jié)點(diǎn)，這樣做的目的是將插入位置右移一位，保證后續(xù)的元素是插在該元素的后面，確保這些元素的順序
predecessor = e;
}
successor.previous = predecessor;
//修改容量大小
size += numNew;
return true;
}
在addAll()方法中，涉及到了兩個(gè)方法，一個(gè)是entry(int index)，該方法為LinkedList的私有方法，主要是用來查找index位置的節(jié)點(diǎn)元素。
/**
* 返回指定位置(若存在)的節(jié)點(diǎn)元素
*/
private Entry entry(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("Index: " + index + ", Size: "
+ size);
//頭部節(jié)點(diǎn)
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;
} 從該方法有兩個(gè)遍歷方向中我們也可以看出LinkedList是雙向鏈表，這也是在構(gòu)造方法中為什么需要將header的前、后節(jié)點(diǎn)均指向自己。
如果對數(shù)據(jù)結(jié)構(gòu)有點(diǎn)了解，對上面所涉及的內(nèi)容應(yīng)該問題，我們只需要清楚一點(diǎn)：LinkedList是雙向鏈表，其余都迎刃而解。
由于篇幅有限，下面將就LinkedList中幾個(gè)常用的方法進(jìn)行源碼分析。
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)建一個(gè)新節(jié)點(diǎn) newEntry，
Entry newEntry = new Entry(e, entry, entry.previous);
//修改newEntry的前后節(jié)點(diǎn)的引用，確保其鏈表的引用關(guān)系是正確的
newEntry.previous.next = newEntry;
newEntry.next.previous = newEntry;
//容量+1
size++;
//修改次數(shù)+1
modCount++;
return newEntry;
} 在addBefore方法中無非就是做了這件事：構(gòu)建一個(gè)新節(jié)點(diǎn)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é)尾。
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;
} 該方法首先會(huì)判斷移除的元素是否為null，然后迭代這個(gè)鏈表找到該元素節(jié)點(diǎn)，最后調(diào)用remove(Entry
private E remove(Entrye) { if (e == header) throw new NoSuchElementException(); //保留被移除的元素：要返回 E result = e.element; //將該節(jié)點(diǎn)的前一節(jié)點(diǎn)的next指向該節(jié)點(diǎn)后節(jié)點(diǎn) e.previous.next = e.next; //將該節(jié)點(diǎn)的后一節(jié)點(diǎn)的previous指向該節(jié)點(diǎn)的前節(jié)點(diǎn) //這兩步就可以將該節(jié)點(diǎn)從鏈表從除去：在該鏈表中是無法遍歷到該節(jié)點(diǎn)的 e.next.previous = e.previous; //將該節(jié)點(diǎn)歸空 e.next = e.previous = null; e.element = null; size--; modCount++; return result; }
其他的移除方法：
clear()： 從此列表中移除所有元素。 remove()：獲取并移除此列表的頭（第一個(gè)元素）。 remove(int index)：移除此列表中指定位置處的元素。 remove(Objec o)：從此列表中移除首次出現(xiàn)的指定元素（如果存在）。 removeFirst()：移除并返回此列表的第一個(gè)元素。 removeFirstOccurrence(Object o)：從此列表中移除第一次出現(xiàn)的指定元素（從頭部到尾部遍歷列表時(shí)）。 removeLast()：移除并返回此列表的最后一個(gè)元素。 removeLastOccurrence(Object o)：從此列表中移除最后一次出現(xiàn)的指定元素（從頭部到尾部遍歷列表時(shí)）。
對于查找方法的源碼就沒有什么好介紹了，無非就是迭代，比對，然后就是返回當(dāng)前值。 get(int index)：返回此列表中指定位置處的元素。 getFirst()：返回此列表的第一個(gè)元素。 getLast()：返回此列表的最后一個(gè)元素。 indexOf(Object o)：返回此列表中首次出現(xiàn)的指定元素的索引，如果此列表中不包含該元素，則返回 -1。 lastIndexOf(Object o)：返回此列表中最后出現(xiàn)的指定元素的索引，如果此列表中不包含該元素，則返回 -1。
Queue接口定義了隊(duì)列數(shù)據(jù)結(jié)構(gòu)，元素是有序的(按插入順序)，先進(jìn)先出。Queue接口相關(guān)的部分UML類圖如下：
DeQueue(Double-ended queue)為接口，繼承了Queue接口，創(chuàng)建雙向隊(duì)列，靈活性更強(qiáng)，可以前向或后向迭代，在隊(duì)頭隊(duì)尾均可心插入或刪除元素。它的兩個(gè)主要實(shí)現(xiàn)類是ArrayDeque和LinkedList。
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，擴(kuò)大成2的冪（是為了維護(hù)頭、尾下標(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(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）進(jìn)行取‘&’運(yùn)算，因?yàn)閘ength是2的冪，所以（length-1）轉(zhuǎn)換為2進(jìn)制全是1，
// 所以如果尾索引值 tail 小于等于（length - 1），那么‘&’運(yùn)算后仍為 tail 本身；如果剛好比（length - 1）大1時(shí)，
// ‘&’運(yùn)算后 tail 便為0（即回到了數(shù)組初始位置）。正是通過與（length - 1）進(jìn)行取‘&’運(yùn)算來實(shí)現(xiàn)數(shù)組的雙向循環(huán)。
// 如果尾索引和頭索引重合了，說明數(shù)組滿了，進(jìn)行擴(kuò)容。
if ((tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();// 擴(kuò)容為原來的2倍
}
addFirst(E e) 的實(shí)現(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）進(jìn)行取‘&’運(yùn)算，結(jié)果必然是（length - 1），即回到了數(shù)組的尾部。
elements[head = (head - 1) & (elements.length - 1)] = e;
// 如果尾索引和頭索引重合了，說明數(shù)組滿了，進(jìn)行擴(kuò)容
if (head == tail)
doubleCapacity();
}remove()方法最終都會(huì)調(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;
}
優(yōu)先隊(duì)列跟普通的隊(duì)列不一樣，普通隊(duì)列是一種遵循FIFO規(guī)則的隊(duì)列，拿數(shù)據(jù)的時(shí)候按照加入隊(duì)列的順序拿取。 而優(yōu)先隊(duì)列每次拿數(shù)據(jù)的時(shí)候都會(huì)拿出優(yōu)先級(jí)最高的數(shù)據(jù)。
優(yōu)先隊(duì)列內(nèi)部維護(hù)著一個(gè)堆，每次取數(shù)據(jù)的時(shí)候都從堆頂拿數(shù)據(jù)（堆頂?shù)膬?yōu)先級(jí)最高），這就是優(yōu)先隊(duì)列的原理。
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方法擴(kuò)容
grow(i + 1); // 擴(kuò)容
size = i + 1; // 元素個(gè)數(shù)+1
if (i == 0) // 堆還沒有元素的情況
queue[0] = e; // 直接給堆頂賦值元素
else // 堆中已有元素的情況
siftUp(i, e); // 重新調(diào)整堆，從下往上調(diào)整，因?yàn)樾略鲈厥羌拥阶詈笠粋€(gè)葉子節(jié)點(diǎn)
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é)點(diǎn)還存在
int parent = (k - 1) >>> 1; // 找到父節(jié)點(diǎn)索引，等同于（k - 1）/ 2
Object e = queue[parent]; // 獲得父節(jié)點(diǎn)元素
// 新元素與父元素進(jìn)行比較，如果滿足比較器結(jié)果，直接跳出，否則進(jìn)行調(diào)整
if (comparator.compare(x, (E) e) >= 0)
break;
queue[k] = e; // 進(jìn)行調(diào)整，新位置的元素變成了父元素
k = parent; // 新位置索引變成父元素索引，進(jìn)行遞歸操作
}
queue[k] = x; // 新添加的元素添加到堆中
}
public E poll() {
if (size == 0)
return null;
int s = --size; // 元素個(gè)數(shù)-1
modCount++;
E result = (E) queue[0]; // 得到堆頂元素
E x = (E) queue[s]; // 最后一個(gè)葉子節(jié)點(diǎn)
queue[s] = null; // 最后1個(gè)葉子節(jié)點(diǎn)置空
if (s != 0)
siftDown(0, x); // 從上往下調(diào)整，因?yàn)閯h除元素是刪除堆頂?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é)點(diǎn)個(gè)數(shù)的一般即可
while (k < half) {
int child = (k << 1) + 1; // 得到父節(jié)點(diǎn)的左子節(jié)點(diǎn)索引，即（k * 2）+ 1
Object c = queue[child]; // 得到左子元素
int right = child + 1; // 得到父節(jié)點(diǎn)的右子節(jié)點(diǎn)索引
if (right < size &&
comparator.compare((E) c, (E) queue[right]) > 0) // 左子節(jié)點(diǎn)跟右子節(jié)點(diǎn)比較，取更大的值
c = queue[child = right];
if (comparator.compare(x, (E) c) <= 0) // 然后這個(gè)更大的值跟最后一個(gè)葉子節(jié)點(diǎn)比較
break;
queue[k] = c; // 新位置使用更大的值
k = child; // 新位置索引變成子元素索引，進(jìn)行遞歸操作
}
queue[k] = x; // 最后一個(gè)葉子節(jié)點(diǎn)添加到合適的位置
}
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; // 元素個(gè)數(shù)-1
if (s == i) // 如果是刪除最后一個(gè)葉子節(jié)點(diǎn)
queue[i] = null; // 直接置空，刪除即可，堆還是保持特質(zhì)，不需要調(diào)整
else { // 如果是刪除的不是最后一個(gè)葉子節(jié)點(diǎn)
E moved = (E) queue[s]; // 獲得最后1個(gè)葉子節(jié)點(diǎn)元素
queue[s] = null; // 最后1個(gè)葉子節(jié)點(diǎn)置空
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() 上濾過程：
1、jdk內(nèi)置的優(yōu)先隊(duì)列PriorityQueue內(nèi)部使用一個(gè)堆維護(hù)數(shù)據(jù)，每當(dāng)有數(shù)據(jù)add進(jìn)來或者poll出去的時(shí)候會(huì)對堆做從下往上的調(diào)整和從上往下的調(diào)整。
2、PriorityQueue不是一個(gè)線程安全的類，如果要在多線程環(huán)境下使用，可以使用 PriorityBlockingQueue 這個(gè)優(yōu)先阻塞隊(duì)列。其中add、poll、remove方法都使用 ReentrantLock 鎖來保持同步，take() 方法中如果元素為空，則會(huì)一直保持阻塞。
感謝各位的閱讀，以上就是“Java集合的Queue和LinkedList怎么使用”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對Java集合的Queue和LinkedList怎么使用這一問題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是創(chuàng)新互聯(lián)，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！
