LinkedList就傳說中的雙向鏈表了。是List 接口的鏈接列表實現。實現所有可選的列表操作，并且允許所有元素（包括 null）。除了實現 List 接口外，LinkedList 類還為在列表的開頭及結尾 get、remove 和 insert 元素提供了統一的命名方法。這些操作允許將鏈接列表用作堆棧、隊列或雙端隊列。

查看LinkedList的構造函數： /*** Constructs an empty list.*/public LinkedList() {header.next = header.previous = header; }

這里的header變量的定義如下：

private transient Entry<E> header = new Entry<E>(null, null, null);

表示雙向循環鏈表的頭結點。其中的Entry定義了雙向鏈表的結構：

private static class Entry<E> {E element;Entry<E> next;Entry<E> previous;Entry(E element, Entry<E> next, Entry<E> previous) {this.element = element;this.next = next;this.previous = previous;} }

Entry中包括數據元素、前續結點和后續結點。

構造函數即是初始化一個只包含header頭結點一個元素的雙向鏈表。

可以得出：LinkedList實質上就是一個雙向鏈表，并把header作為頭結點。 查看LinkedList的add(E)方法： public boolean add(E e) {addBefore(e, header);return true; }

add(E)方法主要指向了addBefore(E, Entry)函數：

private Entry<E> addBefore(E e, Entry<E> entry) {Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);newEntry.previous.next = newEntry;newEntry.next.previous = newEntry;size++;modCount++;return newEntry; }

這個方法中傳入的第二個參數entry為header頭結點，表示把元素插入到header頭結點之前。然后后兩句分別表示設置前續結點的后續結點和后續結點的前續結點。以便連接成雙向鏈表。

可以得出：LinkedList的add(E)方法把新結點插入到header頭結點之前，即列表的結尾。 查看LinkedList的set(int, E)方法： /*** Replaces the element at the specified position in this list with the* specified element.** @param index index of the element to replace* @param element element to be stored at the specified position* @return the element previously at the specified position* @throws IndexOutOfBoundsException {@inheritDoc}*/public E set(int index, E element) {Entry<E> e = entry(index);E oldVal = e.element;e.element = element;return oldVal; }

這個函數主要是設置某個索引位置的結點。首先調用了entry(int)方法：

/*** Returns the indexed entry.*/private Entry<E> entry(int index) {if (index < 0 || index >= size)throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);Entry<E> 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; }

這里首先判斷需要設置的位置是否越界，如果越界則拋出異常。然后通過循環找到需要替換的結點。

接下來回到set(int ,E)函數，把舊的結點替換成新的結點，并返回舊的結點。

可以得出：set(int ,E)方法需要循環遍歷鏈表，時間開銷比較大。 查看LinkedList的push(E)方法： /*** Pushes an element onto the stack represented by this list. In other* words, inserts the element at the front of this list.** <p>This method is equivalent to {@link #addFirst}.** @param e the element to push* @since 1.6*/public void push(E e) {addFirst(e); }

push(E)方法主要調用了addFirst(E)方法：

/*** Inserts the specified element at the beginning of this list.** @param e the element to add*/public void addFirst(E e) {addBefore(e, header.next); }

這里繼續調用addBefore(E, Entity)表示把新節點插入到header頭結點之后。

可以得出：push(E)方法主要是把新節點插入到header頭結點之后。 查看LinkedList的pop()方法： /*** Pops an element from the stack represented by this list. In other* words, removes and returns the first element of this list.** <p>This method is equivalent to {@link #removeFirst()}.** @return the element at the front of this list (which is the top* of the stack represented by this list)* @throws NoSuchElementException if this list is empty* @since 1.6*/public E pop() {return removeFirst(); }

這里繼續調用了removeFirst()方法：

/*** Removes and returns the first element from this list.** @return the first element from this list* @throws NoSuchElementException if this list is empty*/public E removeFirst() {return remove(header.next); }

這里繼續調用remove(Entry<E>)方法：

/*** Retrieves and removes the head (first element) of this list.** @return the head of this list* @throws NoSuchElementException if this list is empty* @since 1.5*/private E remove(Entry<E> e) {if (e == header)throw new NoSuchElementException();E result = e.element;e.previous.next = e.next;e.next.previous = e.previous;e.next = e.previous = null;e.element = null;size--;modCount++;return result; }

在調用remove(Entry<E>)方法時，傳入了header的下一個結點。如果傳入的下一個結點是header的話，表示此事鏈表中只有一個結點header，此時拋出異常。如果找到則刪除該節點（注意這里雙向鏈表刪除結點時的步驟），并返回被刪除的結點。

可以得出：pop()方法刪除的是header頭結點之后的結點，并返回被刪除的結點。 ★ LinkedList實質上就是一個雙向鏈表，并把header作為頭結點。
★ LinkedList的add(E)方法把新結點插入到header頭結點之前。
★ set(int ,E)方法需要循環遍歷鏈表，時間開銷比較大。
★ push(E)方法主要是把新節點插入到header結點之前
★ pop()方法刪除的是header頭結點之后的結點，并返回被刪除的結點。

總結

以上是生活随笔為你收集整理的Java LinkedList双向链表源码分析的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。