1類簽名與注釋

public class LinkedList<E>extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, java.io.Serializable

雙向鏈表實現了List和Deque接口。 實現所有可選列表操作，并允許所有元素（包括null ）。

請注意，此實現不同步。 如果多個線程同時訪問鏈接列表，并且至少有一個線程在結構上修改列表，則必須在外部進行同步。 （結構修改是添加或刪除一個或多個元素的任何操作;僅設置元素的值不是結構修改。）這通常通過在自然封裝列表的對象上進行同步來實現。 如果沒有這樣的對象存在，列表應該使用Collections.synchronizedList方法“包裝”。 這最好在創建時完成，以防止意外的不同步訪問列表：

List list = Collections.synchronizedList(new LinkedList(...));

這個類的iterator和listIterator方法返回的迭代器是故障快速的：迭代器創建之后，除了自己的remove和add方法外的任何方法改變了集合的結構，迭代器會拋出ConcurrentModificationException異常。

注意：LinkedList實現了Deque接口，而Deque又繼承了Queue接口，所以LinkedList可以當作隊列（Queue）來使用。

?

?

2數據結構

LinkedList的基本屬性有三個

transient int size = 0;transient Node<E> first;transient Node<E> last;

size：集合中元素的個數

first：鏈表的第一個節點

last：鏈表的最后一個節點

Node的數據結構如下

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

Node類維護了本節點的元素item，以及前向節點prev和后向節點next的引用。

?

?

3添加元素

（1）add(E?e)

將指定的元素追加到此列表的末尾。

1 public boolean add(E e) { 2 linkLast(e); 3 return true; 4 } 5 6 void linkLast(E e) { 7 final Node<E> l = last; 8 final Node<E> newNode = new Node<>(l, e, null); 9 last = newNode; 10 if (l == null) 11 first = newNode; 12 else 13 l.next = newNode; 14 size++; 15 modCount++; 16 }

?

（2）add(int?index, E?element)

在此列表中的指定位置插入指定的元素。

public void add(int index, E element) {checkPositionIndex(index);if (index == size)linkLast(element);elselinkBefore(element, node(index));}//檢查索引是否越界（0<=index<=size） private void checkPositionIndex(int index) {if (!isPositionIndex(index))throw new IndexOutOfBoundsException(outOfBoundsMsg(index));} private boolean isPositionIndex(int index) {return index >= 0 && index <= size;}//在節點succ前插入新節點e 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;elsepred.next = newNode;size++;modCount++;}//返回對應索引位置的節點 Node<E> node(int index) {// assert isElementIndex(index);if (index < (size >> 1)) {Node<E> x = first;for (int i = 0; i < index; i++)x = x.next;return x;} else {Node<E> x = last;for (int i = size - 1; i > index; i--)x = x.prev;return x;}}

node方法做了優化，當index小于size/2時，從first開始往后遍歷，否則從last開始往前遍歷。這里是一個簡單的二分思路。

?

（3）addFirst(E?e)

在該列表開頭插入指定的元素。

public void addFirst(E e) {linkFirst(e);}private void linkFirst(E e) {final Node<E> f = first;final Node<E> newNode = new Node<>(null, e, f);first = newNode;if (f == null)last = newNode;elsef.prev = newNode;size++;modCount++;}

?

（4）addLast(E?e)

將指定的元素追加到此列表的末尾。 public void addLast(E e) {linkLast(e);}void linkLast(E e) {final Node<E> l = last;final Node<E> newNode = new Node<>(l, e, null);last = newNode;if (l == null)first = newNode;elsel.next = newNode;size++;modCount++;}

?

?

4刪除元素

（1）remove()

檢索并刪除此列表的頭（第一個元素）。 public E remove() {return removeFirst();}public E removeFirst() {final Node<E> f = first;if (f == null)throw new NoSuchElementException();return unlinkFirst(f);}private E unlinkFirst(Node<E> f) {// assert f == first && f != null;final E element = f.item;final Node<E> next = f.next;f.item = null;f.next = null; // help GCfirst = next;if (next == null)last = null;elsenext.prev = null;size--;modCount++;return element;}

?

（2）remove(int?index)

刪除該列表中指定位置的元素。 public E remove(int index) {checkElementIndex(index);return unlink(node(index));}E unlink(Node<E> x) {// assert x != null;final E element = x.item;final Node<E> next = x.next;final Node<E> prev = x.prev;if (prev == null) {first = next;} else {prev.next = next;x.prev = null;}if (next == null) {last = prev;} else {next.prev = prev;x.next = null;}x.item = null;size--;modCount++;return element;}

?

（3）removeFirst()

從此列表中刪除并返回第一個元素。

public E removeFirst() {final Node<E> f = first;if (f == null)throw new NoSuchElementException();return unlinkFirst(f);}

?

（4）removeLast()

從此列表中刪除并返回最后一個元素。 public E removeLast() {final Node<E> l = last;if (l == null)throw new NoSuchElementException();return unlinkLast(l);}private E unlinkLast(Node<E> l) {// assert l == last && l != null;final E element = l.item;final Node<E> prev = l.prev;l.item = null;l.prev = null; // help GClast = prev;if (prev == null)first = null;elseprev.next = null;size--;modCount++;return element;}

還有其他一些刪除方法（如下所示）這里就不放代碼，感興趣的可以自己去看一下。

boolean remove(Object o) 從列表中刪除指定元素的第一個出現（如果存在）。 boolean removeFirstOccurrence(Object o) 刪除此列表中指定元素的第一個出現（從頭到尾遍歷列表時）。 boolean removeLastOccurrence(Object o) 刪除此列表中指定元素的最后一次出現（從頭到尾遍歷列表時）。

?

?

5 LinkedList當作隊列使用

（1）入隊 offer

將指定的元素添加為此列表的尾部（最后一個元素）。

public boolean offer(E e) {return add(e);}

offer直接調用add（e）在隊列的末尾添加一個元素。

?

（2）出隊 poll

檢索并刪除此列表的頭（第一個元素）。 public E poll() {final Node<E> f = first;return (f == null) ? null : unlinkFirst(f);}

簡單使用如下

Queue<Integer> queue = new LinkedList<>(); for(int i = 1 ; i < 5 ; i++){queue.offer(i); } System.out.println(queue.poll()); for(int i : queue){System.out.print(i+" "); }

輸出

1 2 3 4

?

（3）查看隊頭元素 peek()

public E peek() {final Node<E> f = first;return (f == null) ? null : f.item;}

?

?

6 LinkedList當作棧來使用

（1）入棧 push(E?e)

public void push(E e) {addFirst(e);}

?

（2）出棧 pop()

public E pop() {return removeFirst();}

?

（3）查看棧頂元素 peek()

public E peek() {final Node<E> f = first;return (f == null) ? null : f.item;}

當作棧使用的時候，鏈表的表頭相當于棧頂，每次入棧都是往表頭插入，每次出棧都是刪除表頭指向的節點。簡單使用如下

LinkedList<Integer> stack = new LinkedList<>(); for(int i = 1 ; i < 5 ; i++){stack.push(i); } System.out.println(stack.pop()); for(int i : stack){System.out.print(i+" "); }

輸出

4 3 2 1

?

?

7總結

簡單來講，LinkedList就是一個雙向鏈表。分析一下數組與鏈表各自的優缺點，就可以很清楚的知道什么時候用ArrayList什么時候該用LinkedList。

鏈表的優勢在于增加和刪除節點。而數組的優勢在于遍歷。

轉載于:https://www.cnblogs.com/ouym/p/9019501.html

總結

以上是生活随笔為你收集整理的java源码阅读LinkedList的全部內容，希望文章能夠幫你解決所遇到的問題。

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