如何在Java 中實現LinkedList

這期內容當中小編將會給大家帶來有關如何在Java 中實現LinkedList，文章內容豐富且以專業的角度為大家分析和敘述，閱讀完這篇文章希望大家可以有所收獲。

來看一下 LinkedList 中的屬性：

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

1、結點結構

Node 是在 LinkedList 里定義的一個靜態內部類，它表示鏈表每個節點的結構，包括一個數據域 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、添加元素

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

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

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

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

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

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

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

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

當向指定節點之前插入一個節點時，當前節點的后繼為指定節點，而前驅結點為指定節點的前驅節點。此外，還要修改前驅節點的后繼為當前節點，以及后繼節點的前驅為當前節點，源碼的實現如下：

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

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