一、概述

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

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 是通過(guò)一個(gè)雙向鏈表來(lái)實(shí)現(xiàn)的，它允許插入所有元素，包括 null，同時(shí)，它是線程不同步的。如果對(duì)雙向鏈表這個(gè)數(shù)據(jù)結(jié)構(gòu)很熟悉的話，學(xué)習(xí)LinkedList 就沒(méi)什么難度了。下面是雙向鏈表的結(jié)構(gòu)：

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

二、屬性

接下來(lái)看一下 LinkedList 中的屬性：

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

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

三、方法

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

Node 是在 LinkedList 里定義的一個(gè)靜態(tài)內(nèi)部類，它表示鏈表每個(gè)節(jié)點(diǎn)的結(jié)構(gòu)，包括一個(gè)數(shù)據(jù)域 item，一個(gè)后置指針 next，一個(gè)前置指針 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、添加元素

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

在表頭添加元素的過(guò)程如下：

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

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

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

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

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

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

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

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

總結(jié)

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

最新評(píng)論