一、概述

先來看看源碼中的這一段注釋，我們先嘗試從中提取一些信息：

Doubly-linked list implementation of the List and Deque interfaces. Implements all optional list operations, and permits all elements (including null).All of the operations perform as could be expected for a doubly-linked list. Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.Note that this implementation is not synchronized. If multiple threads access a linked list concurrently, and at least one of the threads modifies the list structurally, it must be synchronized externally. (A structural modification is any operation that adds or deletes one or more elements; merely setting the value of an element is not a structural modification.) This is typically accomplished by synchronizing on some object that naturally encapsulates the list.

從這段注釋中，我們可以得知 LinkedList 是通過一個雙向鏈表來實現(xiàn)的，它允許插入所有元素，包括 null，同時，它是線程不同步的。如果對雙向鏈表這個數(shù)據(jù)結(jié)構(gòu)很熟悉的話，學(xué)習(xí)LinkedList 就沒什么難度了。下面是雙向鏈表的結(jié)構(gòu)：

雙向鏈表每個結(jié)點除了數(shù)據(jù)域之外，還有一個前指針和后指針，分別指向前驅(qū)結(jié)點和后繼結(jié)點（如果有前驅(qū)/后繼的話）。另外，雙向鏈表還有一個 first 指針，指向頭節(jié)點，和 last 指針，指向尾節(jié)點。

二、屬性

接下來看一下 LinkedList 中的屬性：

//鏈表的節(jié)點個數(shù)
transient int size = 0;
//指向頭節(jié)點的指針
transient Node<E> first;
//指向尾節(jié)點的指針
transient Node<E> last;

LinkedList 的屬性非常少，就只有這些。通過這三個屬性，其實我們大概也可以猜測出它是怎么實現(xiàn)的了。

三、方法

1、結(jié)點結(jié)構(gòu)

Node 是在 LinkedList 里定義的一個靜態(tài)內(nèi)部類，它表示鏈表每個節(jié)點的結(jié)構(gòu)，包括一個數(shù)據(jù)域 item，一個后置指針 next，一個前置指針 prev。

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

2、添加元素

對于鏈表這種數(shù)據(jù)結(jié)構(gòu)來說，添加元素的操作無非就是在表頭/表尾插入元素，又或者在指定位置插入元素。因為 LinkedList 有頭指針和尾指針，所以在表頭或表尾進行插入元素只需要 O(1) 的時間，而在指定位置插入元素則需要先遍歷一下鏈表，所以復(fù)雜度為 O(n)。

在表頭添加元素的過程如下：

當(dāng)向表頭插入一個節(jié)點時，很顯然當(dāng)前節(jié)點的前驅(qū)一定為 null，而后繼結(jié)點是 first 指針指向的節(jié)點，當(dāng)然還要修改 first 指針指向新的頭節(jié)點。除此之外，原來的頭節(jié)點變成了第二個節(jié)點，所以還要修改原來頭節(jié)點的前驅(qū)指針，使它指向表頭節(jié)點，源碼的實現(xiàn)如下：

private void linkFirst(E e) {
 final Node<E> f = first;
 //當(dāng)前節(jié)點的前驅(qū)指向 null，后繼指針原來的頭節(jié)點
 final Node<E> newNode = new Node<>(null, e, f);
 //頭指針指向新的頭節(jié)點
 first = newNode;
 //如果原來有頭節(jié)點，則更新原來節(jié)點的前驅(qū)指針，否則更新尾指針
 if (f == null)
 last = newNode;
 else
 f.prev = newNode;
 size++;
 modCount++;
}

在表尾添加元素跟在表頭添加元素大同小異，如圖所示

當(dāng)向表尾插入一個節(jié)點時，很顯然當(dāng)前節(jié)點的后繼一定為 null，而前驅(qū)結(jié)點是 last指針指向的節(jié)點，然后還要修改 last 指針指向新的尾節(jié)點。此外，還要修改原來尾節(jié)點的后繼指針，使它指向新的尾節(jié)點，源碼的實現(xiàn)如下：

void linkLast(E e) {
 final Node<E> l = last;
 //當(dāng)前節(jié)點的前驅(qū)指向尾節(jié)點，后繼指向 null
 final Node<E> newNode = new Node<>(l, e, null);
 //尾指針指向新的尾節(jié)點
 last = newNode;
 //如果原來有尾節(jié)點，則更新原來節(jié)點的后繼指針，否則更新頭指針
 if (l == null)
 first = newNode;
 else
 l.next = newNode;
 size++;
 modCount++;
}

最后，在指定節(jié)點之前插入，如圖所示

當(dāng)向指定節(jié)點之前插入一個節(jié)點時，當(dāng)前節(jié)點的后繼為指定節(jié)點，而前驅(qū)結(jié)點為指定節(jié)點的前驅(qū)節(jié)點。此外，還要修改前驅(qū)節(jié)點的后繼為當(dāng)前節(jié)點，以及后繼節(jié)點的前驅(qū)為當(dāng)前節(jié)點，源碼的實現(xiàn)如下：

void linkBefore(E e, Node<E> succ) {
 // assert succ != null;
 //指定節(jié)點的前驅(qū)
 final Node<E> pred = succ.prev;
 //當(dāng)前節(jié)點的前驅(qū)為指點節(jié)點的前驅(qū)，后繼為指定的節(jié)點
 final Node<E> newNode = new Node<>(pred, e, succ);
 //更新指定節(jié)點的前驅(qū)為當(dāng)前節(jié)點
 succ.prev = newNode;
 //更新前驅(qū)節(jié)點的后繼
 if (pred == null)
 first = newNode;
 else
 pred.next = newNode;
 size++;
 modCount++;
}

總結(jié)

以上就是這篇文章的全部內(nèi)容了，希望本文的內(nèi)容對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，謝謝大家對腳本之家的支持。如果你想了解更多相關(guān)內(nèi)容請查看下面相關(guān)鏈接

最新評論