如何在Java 中實(shí)現(xiàn)LinkedList

這期內(nèi)容當(dāng)中小編將會(huì)給大家?guī)碛嘘P(guān)如何在Java 中實(shí)現(xiàn)LinkedList，文章內(nèi)容豐富且以專業(yè)的角度為大家分析和敘述，閱讀完這篇文章希望大家可以有所收獲。

來看一下 LinkedList 中的屬性：

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

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)來說，添加元素的操作無非就是在表頭/表尾插入元素，又或者在指定位置插入元素。因?yàn)?LinkedList 有頭指針和尾指針，所以在表頭或表尾進(jìn)行插入元素只需要 O(1) 的時(shí)間，而在指定位置插入元素則需要先遍歷一下鏈表，所以復(fù)雜度為 O(n)。

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

當(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)。除此之外，原來的頭節(jié)點(diǎn)變成了第二個(gè)節(jié)點(diǎn)，所以還要修改原來頭節(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，后繼指針原來的頭節(jié)點(diǎn)
 final Node<E> newNode = new Node<>(null, e, f);
 //頭指針指向新的頭節(jié)點(diǎn)
 first = newNode;
 //如果原來有頭節(jié)點(diǎn)，則更新原來節(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)。此外，還要修改原來尾節(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;
 //如果原來有尾節(jié)點(diǎn)，則更新原來節(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++;
}

上述就是小編為大家分享的如何在Java 中實(shí)現(xiàn)LinkedList了，如果剛好有類似的疑惑，不妨參照上述分析進(jìn)行理解。如果想知道更多相關(guān)知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道。