文章目錄
-
- 1、LinkedList 簡述
- 2、LinkedList 類圖
- 2.1、LinkedList 内部結構
- 3、LinkedList 成員變量
-
- 3.1、size 連結清單的節點數量
- 3.2、first 指向第一個節點的指針
- 3.3、last 指向最後一個節點的指針
- 4、LinkedList 構造函數
-
- 4.1、LinkedList()
- 4.2、LinkedList(Collection<? extends E> c)
- 5、LinkedList 方法
-
- 5.1、LinkedList 擷取元素
-
- 5.1.1、public E get(int index)
- 5.1.2、public E getFirst()
- 5.1.3、public E getLast()
- 5.1.4、public int indexOf(Object o)
- 5.1.5、public int lastIndexOf(Object o)
- 5.1.6、public E peek()
- 5.1.7、public E peekFirst() 同 peek()
- 5.1.8、public E peekLast()
- 5.1.9、public E element()
- 5.2、LinkedList 增加元素
-
- 5.2.1、public boolean add(E e) 等價 addLast
- 5.2.2、public void add(int index, E element)
- 5.2.3、public void addFirst(E e)
- 5.2.4、public void addLast(E e) 等價 add
- 5.2.5、public boolean addAll(Collection<? extends E> c)
- 5.2.6、public boolean addAll(int index, Collection<? extends E> c)
- 5.2.7、public boolean offer(E e) 等價于 add
- 5.2.8、public boolean offerFirst(E e) 等價于 addFirst(E e)
- 5.2.9、public boolean offerLast(E e) 等價于 addLast(E e)
- 5.2.10、public void push(E e) 等價于 addFirst(E e)
- 5.3、LinkedList 删除元素
-
- 5.3.1、public E remove()
- 5.3.2、public E remove(int index)
- 5.3.3、public boolean remove(Object o)
- 5.3.4、public E removeFirst()
- 5.3.5、public E removeLast()
- 5.3.6、public boolean removeFirstOccurrence(Object o)
- 5.3.7、public boolean removeLastOccurrence(Object o)
- 5.3.8、public E poll()
- 5.3.9、public E pollFirst()
- 5.3.10、public E pollLast()
- 5.3.11、public E pop() 等價于 removeFirst（）
- 5.3.12、public void clear()
- 5.4、LinkedList 其它方法
-
- 5.4.1、public boolean contains(Object o)
- 5.4.2、public int size()
- 5.4.3、public E set(int index,E element)
- 5.4.4、public ListIterator listIterator(int index)
- 5.4.5、public Iterator descendingIterator()
- 5.4.6、public Object clone()
- 5.4.7、public Object[] toArray()
- 5.4.8、public T[] toArray(T[] a)
- 5.4.9、public Spliterator spliterator()
1、LinkedList 簡述
1）Java LinkedList是List和Deque接口的實作。
2）在内部，LinkedList 是采用雙向連結清單實作的，它包含一個很重要的内部類 Node。Node是雙向連結清單節點所對應的資料結構，它包括的屬性有：目前節點所包含的值，上一個節點，下一個節點。
3）它支援重複元素，并且可以添加任意數量的null元素。
4）它以插入順序存儲或維護它的元素。
5）它不是線程安全的，我們可以使用Collections.synchronizedList(new LinkedList(…));方法建立一個同步的連結清單。
6）在Java應用中，LinkedList 可以用作List，LIFO(後進先出)的棧或FIFO(先進先出)的隊列。
7）它沒有實作RandomAccess接口。 是以我們隻能按順序通路元素。 它不支援随機通路元素。
8）當我們嘗試從 LinkedList 通路元素時，根據元素可用的位置搜尋該元素從LinkedList的開頭或結尾開始。
9）我們可以使用ListIterator來疊代LinkedList元素。
10）從LinkedList的實作方式中可以發現，它不存在LinkedList容量不足的問題。
11）LinkedList 的克隆函數（clone()），是将全部元素克隆到一個新的LinkedList對象中。
12）LinkedList 實作java.io.Serializable。當寫入到輸出流時，先寫入“容量”，再依次寫入“每一個節點保護的值”；當讀出輸入流時，先讀取“容量”，再依次讀取“每一個元素”。
13）由于LinkedList實作了Deque，而Deque接口定義了在雙端隊列兩端通路元素的方法。提供插入、移除和檢查元素的方法。每種方法都存在兩種形式：一種形式在操作失敗時抛出異常，另一種形式傳回一個特殊值（null 或 false，具體取決于操作）
14）從Java 8開始，我們可以将LinkedList 轉換為 Stream，反之亦然。
15）Java 9 添加了幾個工廠方法來建立一個Immutable LinkedList。
2、LinkedList 類圖
衆所周知，Java LinkedList是List實作類之一。
java.util.LinkedList 繼承了 AbstractSequentialList 并實作了List , Deque , Cloneable 以及Serializable 接口
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
2.1、LinkedList 内部結構
LinkedList内部結構是一個雙向連結清單
每一個節點都是一個Node 對象，由三個元素組成
private static class Node<E> {
// E類型的值item
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;
}
}
3、LinkedList 成員變量
3.1、size 連結清單的節點數量
初始化連結清單的長度為0
transient int size = 0;
3.2、first 指向第一個節點的指針
/**
* 指向第一個節點的指針
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first;
3.3、last 指向最後一個節點的指針
/**
* 指向最後一個節點的指針。
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;
4、LinkedList 構造函數
4.1、LinkedList()
構造一個空清單。
public LinkedList() {}
4.2、LinkedList(Collection<? extends E> c)
/**
* 按照集合的疊代器傳回的順序構造一個包含指定集合元素的清單。
*
* @param c 要将其元素放入此清單的集合
* @throws NullPointerException 如果指定集合為null
*/
public LinkedList(Collection<? extends E> c) {
this();
//使用addAll方法，實際上就是周遊c并且采用頭插法進行雙向連結清單插入值。
addAll(c);
}
5、LinkedList 方法
由于LinkedList實作了Deque，而Deque接口定義了在雙端隊列兩端通路元素的方法。提供插入、移除和檢查元素的方法。每種方法都存在兩種形式：一種形式在操作失敗時抛出異常，另一種形式傳回一個特殊值（null 或 false，具體取決于操作）
| 操作 | 頭部元素 | 尾部元素 | ||
| 傳回值 | 抛出異常 | 特殊值 | 抛出異常 | 特殊值 |
| 插入 | addFirst(e) | offerFirst(e) | addLast(e) | offerLast(e) |
| 移除 | removeFirst() | pollFirst() | removeLast() | pollLast() |
| 檢索 | getFirst() | peekFirst() | getLast() | peekLast() |
LinkedList 可以作為 FIFO(先進先出)的隊列，作為FIFO的隊列時，下面的方法是等價的
| 隊列方法 | 等價方法 |
|---|---|
| add(e) | addLast(e) |
| offer(e) | offerLast(e) |
| remove() | removeFirst() |
| poll() | pollFirst() |
| element() | getFirst() |
| peek() | peekFirst() |
LinkedList 可以作為 LIFO(後進先出)的棧，作為LIFO的棧時，下面的方法是等價的
| 棧方法 | 等價方法 |
|---|---|
| push(e) | addFirst(e) |
| pop() | removeFirst() |
| peek() | peekFirst() |
5.1、LinkedList 擷取元素
5.1.1、public E get(int index)
擷取指定索引處節點的元素，首先對指定索引進行越界檢查，如果未越界傳回相應位置node節點的元素；否則，抛出 IndexOutOfBoundsException 異常
/**
* 傳回此清單中指定位置的元素。
*
* @param index 要傳回的元素的索引值
* @return 清單中指定位置的元素
* @throws IndexOutOfBoundsException
*/
public E get(int index) {
//索引越界檢查
checkElementIndex(index);
return node(index).item;
}
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* 判斷參數是否是現有元素的索引。
*/
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
/**
* 構造一個IndexOutOfBoundsException詳細消息。
*
*/
private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+size;
}
/**
* 傳回指定元素索引處的（非null）節點。
*/
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;
}
}
5.1.2、public E getFirst()
傳回此清單中的第一個元素。
/**
* 傳回此清單中的第一個元素。
*
* @return 此清單中的第一個元素。
* @throws NoSuchElementException 如果清單為空
*/
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
5.1.3、public E getLast()
傳回此清單中最後一個元素
/**
* 傳回此清單中最後一個元素
*
* @return 此清單中最後一個元素
* @throws NoSuchElementException 如果清單為null
*/
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
5.1.4、public int indexOf(Object o)
傳回此清單中第一次出現的指定元素的索引，如果此清單不包含該元素，則傳回-1。
- 如果需要檢索的元素是null，對元素連結清單進行周遊，傳回x的元素為空的位置
- 如果需要檢索的元素不是null，對元素的連結清單周遊，直到找到相同的元素，傳回元素下标
public int indexOf(Object o) {
int index = 0;
//如果檢索的元素為null
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {
//如果檢索的元素不為null
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}
5.1.5、public int lastIndexOf(Object o)
傳回此清單中指定元素最後一次出現的索引，如果此清單不包含該元素，則傳回-1。
public int lastIndexOf(Object o) {
int index = size;
if (o == null) {
for (Node<E> x = last; x != null; x = x.prev) {
index--;
if (x.item == null)
return index;
}
} else {
for (Node<E> x = last; x != null; x = x.prev) {
index--;
if (o.equals(x.item))
return index;
}
}
return -1;
}
5.1.6、public E peek()
檢索并傳回此清單的第一個元素，但不删除該元素。如果清單為空，則傳回null
/**
* 檢索但不删除此清單的頭部（第一個元素）。
*/
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
5.1.7、public E peekFirst() 同 peek()
5.1.8、public E peekLast()
檢索但不删除此清單的最後一個元素，如果此清單為空，則傳回null。
public E peekLast() {
final Node<E> l = last;
return (l == null) ? null : l.item;
}
5.1.9、public E element()
與peek()相同的地方都是通路連結清單的第一個元素，不同是element元素在連結清單為null的時候會報空指針異常
public E element() {
return getFirst();
}
5.2、LinkedList 增加元素
5.2.1、public boolean add(E e) 等價 addLast
添加指定元素至list末尾，等價于 addLast
/**
* 添加指定元素至list末尾
*
* 該方法等價與addLast
*
* @param e 添加到清單的元素
* @return {@code true} (as specified by {@link Collection#add})
*/
public boolean add(E e) {
linkLast(e);
return true;
}
/**
* 連結e作為最後一個元素
*/
void linkLast(E e) {
//建立臨時節點l初始化為尾節點
final Node<E> l = last;
//初始化新節點，前驅節點為l，後繼暫為null
final Node<E> newNode = new Node<>(l, e, null);
//由于是在連結清單尾部插入節點，那麼新節點就作為尾節點
last = newNode;
/**
* l節點作為newNode節點的前驅節點。
* 如果l為空，那麼newNode前驅節點為空。
* 在雙向連結清單中，前驅節點為空，那麼該節點為頭節點。
*/
if (l == null)
first = newNode;
else
// 如果不是的話，就讓該節點的next 指向新的節點
l.next = newNode;
//插入節點後，連結清單的長度加1
size++;
modCount++;
}
5.2.2、public void add(int index, E element)
将元素插入指定位置，首先通過index擷取目前對應的定位節點。如果下标對應的定位節點就是尾節點，那麼直接使用linkLast方法在連結清單尾部插入節點。如果對應的定位節點不是尾節點，就插入到index節點的前面。
/**
* 在連結清單的指定位置插入指定元素
* 将目前位于該位置的元素（如果有）和任何後續元素向右移動。
*
* @param index 指定元素插入位置的索引
* @param element 待插入的元素
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
// 先檢查索引是否在連結清單的範圍内。
checkPositionIndex(index);
// 如果索引等于連結清單長度，那麼直接采用尾插法的linkLast方法。
if (index == size)
linkLast(element);
else
//否則就在指定位置的非空節點之前插入元素
linkBefore(element, node(index));
}
private void checkPositionIndex(int index) {
// 下标越界檢查
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* 判斷參數是否是有效位置
*/
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
/**
* 連結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;
else
l.next = newNode;
size++;
modCount++;
}
/**
* 在節點succ作為通過下标索引在連結清單中查詢出來的對應的節點。
* e值包裝的節點插入到succ節點之前。
*/
void linkBefore(E e, Node<E> succ) {
//succ節點的前驅為pred
final Node<E> pred = succ.prev;
//初始化新節點前驅為pred，後繼為succ，意思就是想在pred和succ節點之間插入newNode節點
final Node<E> newNode = new Node<>(pred, e, succ);
//到這步，newNode已經确立了，後繼節點為succ。succ節點的前驅為newNode。
succ.prev = newNode;
//如果pred為空，那麼newNode的前驅節點為空，可以确定newNode為頭節點。
if (pred == null)
first = newNode;
else
/* 如果pred不為空，則确定了pred節點後繼為newNode，之前已經确
* 定newNode的前驅為pred，這樣pred和newNode就确立關系了。
*/
pred.next = newNode;
size++;//新增節點，長度更新為原來長度加1
modCount++;
}
5.2.3、public void addFirst(E e)
在此清單的開頭插入指定的元素。要添加 元素至連結清單的頭部，需要先找到first節點，如果first節點為null，也就說明沒有頭節點，如果不為null，則頭節點的prev節點是新插入的節點。
如果雙向連結清單為空，那麼插入節點作為頭節點，如果雙向連結清單不為空，那麼插入節點作為頭結點的前驅節點。
/**
* 在此清單的開頭插入指定的元素。
*
* @param e 準備添加的元素
*/
public void addFirst(E e) {
linkFirst(e);
}
/**
* 将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;
else
//如果原頭結點不為空，那麼新節點插入到原頭結點前面
f.prev = newNode;
size++;
modCount++;
}
5.2.4、public void addLast(E e) 等價 add
将指定的元素追加到此清單的末尾。如果雙向連結清單為空，那麼直接新節點作為頭節點。如果雙向連結清單不為空，那麼在尾節點後面插入新節點。
/**
* 将指定的元素追加到此清單的末尾。
*
* 此方法等價與add
*
* @param 準備添加的元素
*/
public void addLast(E e) {
linkLast(e);
}
//采用雙向連結清單尾插法的方式插入元素
void linkLast(E e) {
//建立臨時節點l初始化為尾節點（那麼其後繼節點為null，前驅節點不為空）。
final Node<E> l = last;
//初始化新節點，前驅節點為l，後繼暫為null
final Node<E> newNode = new Node<>(l, e, null);
//由于是在連結清單尾部插入節點，那麼新節點就作為尾節點。
last = newNode;
/**
* l節點作為newNode節點的前驅節點。
* 如果l為空，那麼newNode前驅節點為空。
* 在雙向連結清單中，前驅節點為空，那麼該節點為頭節點。
*/
if (l == null)
first = newNode;
else
l.next = newNode;
size++;//再插入節點後，連結清單的長度加1
modCount++;
}
5.2.5、public boolean addAll(Collection<? extends E> c)
将指定集合中的所有元素按指定集合的疊代器傳回的順序附加到此清單的末尾。 如果在操作正在進行時修改了指定的集合，則此操作的行為是不确定的。
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
5.2.6、public boolean addAll(int index, Collection<? extends E> c)
将指定集合中的所有元素按指定集合的疊代器傳回的順序附加到此清單的末尾。 如果在操作正在進行時修改了指定的集合，則此操作的行為是不确定的。
插入一個Collection 的集合，沒有指定插入元素的位置，預設是向連結清單的尾部進行連結。
如果指定了插入位置，首先會進行數組越界檢查，然後會把集合轉換為數組，在判斷數組的大小是否為0，為0傳回，不為0，繼續下面操作
然後周遊數組，首先生成對應的節點，最後對節點進行連結
/**
* @param index 插入清單指定位置的索引
* @param c 包含要添加到此清單的元素的集合
* @return {@code true} if this list changed as a result of the call
* @throws IndexOutOfBoundsException 下标越界異常
* @throws NullPointerException 如果指定的集合為null，則抛出空指針異常
*/
public boolean addAll(int index, Collection<? extends E> c) {
//判斷下标元素是否在連結清單的長度範圍之内
checkPositionIndex(index);
//将集合c轉換成Object數組
Object[] a = c.toArray();
//插入元素的數量
int numNew = a.length;
//如果Object數組長度為0，那麼就傳回添加失敗
if (numNew == 0)
return false;
//pred節點為succ節點的前驅
Node<E> pred, succ;
//如果下标等于連結清單的長度時，pred為尾節點，succ指向為空
if (index == size) {
succ = null;
pred = last;
} else {
/* 如果下标不等于連結清單長度，node方法就是用來通過下标索引獲
* 取連結清單中的對應的節點對象。
*/
succ = node(index);
pred = succ.prev;
}
//周遊數組，建立node節點
for (Object o : a) {
//将周遊的值包裝成節點Node，初始化前驅節點為pred，後繼節點為null
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);
//如果前驅節點為空，那麼肯定是頭節點
if (pred == null)
first = newNode;
else
//否則不是頭節點，那麼前驅的後繼節點為目前節點，其實就是類似于連結清單的插入節點操作。
pred.next = newNode;
pred = newNode;
}
/*
* 因為pred節點是succ節點的前驅節點，反之succ是pred的後繼節點.
* 如果succ為空，說明pred為尾節點。
*/
if (succ == null) {
last = pred;
} else {
/*
如果succ不是尾節點，那麼隻要保證pred節點是succ節點的前驅
* 節點、succ是pred的後繼節點這種雙向連結清單的關系
*/
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
5.2.7、public boolean offer(E e) 等價于 add
public boolean offer(E e) {
return add(e);
}
5.2.8、public boolean offerFirst(E e) 等價于 addFirst(E e)
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
5.2.9、public boolean offerLast(E e) 等價于 addLast(E e)
public boolean offerLast(E e) {
addLast(e);
return true;
}
5.2.10、public void push(E e) 等價于 addFirst(E e)
public void push(E e) {
addFirst(e);
}
5.3、LinkedList 删除元素
5.3.1、public E remove()
檢索并删除此清單的第一個元素
/**
*
* @return 傳回清單的第一個元素
* @throws NoSuchElementException 如果目前清單為空
* @since 1.5
*/
public E remove() {
return removeFirst();
}
5.3.2、public E remove(int index)
删除此清單中指定位置的元素。 将任何後續元素向左移位。傳回從清單中删除的元素。
/**
* @param index 被删除元素的索引位置
* @return 傳回從清單中删除的指定索引位置的元素
* @throws IndexOutOfBoundsException
*/
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
5.3.3、public boolean remove(Object o)
從此清單中删除指定元素的第一個比對項（如果存在）。 如果此清單不包含該元素，則不會更改。
/**
*
* @param o 要從此清單中删除的元素（如果存在）
* @return {@code true} 如果此清單包含指定的元素，則傳回true
*/
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
5.3.4、public E removeFirst()
删除并傳回此清單的第一個元素
/**
* 删除并傳回此清單的第一個元素
*
* @return 此清單第一個元素
* @throws NoSuchElementException 如果清單為空
*/
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
5.3.5、public E removeLast()
删除并傳回此清單的最後一個元素
/**
* 删除并傳回此清單的最後一個元素
*
* @return 此清單最後一個元素
* @throws NoSuchElementException 如果清單為空
*/
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
5.3.6、public boolean removeFirstOccurrence(Object o)
删除此清單中第一次出現的指定元素（從頭到尾周遊清單時）。 如果清單不包含該元素，則不會更改。
/**
* @param o 從清單中删除的指定元素
* @return 如果清單包含指定的元素傳回true
* @since 1.6
*/
public boolean removeFirstOccurrence(Object o) {
return remove(o);
}
5.3.7、public boolean removeLastOccurrence(Object o)
删除此清單中最後一次出現的指定元素（從頭到尾周遊清單時）。 如果清單不包含該元素，則不會更改。
/**
* @param o 從清單中删除的指定元素
* @return 如果清單包含指定的元素傳回true
* @since 1.6
*/
public boolean removeLastOccurrence(Object o) {
if (o == null) {
for (Node<E> x = last; x != null; x = x.prev) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = last; x != null; x = x.prev) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
5.3.8、public E poll()
檢索并删除此清單的第一個元素，如果此清單為空，則傳回null。
/**
* @return 傳回此清單的第一個元素，如果清單為空則傳回null
* @since 1.5
*/
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
5.3.9、public E pollFirst()
檢索并删除此清單的第一個元素，如果此清單為空，則傳回null。
/**
* @return 傳回此清單的第一個元素，如果清單為空則傳回null
* @since 1.6
*/
public E pollFirst() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
5.3.10、public E pollLast()
檢索并删除此清單的最後一個元素，如果此清單為空，則傳回null。
/**
* @return 此清單的最後一個元素，如果此清單為空，則傳回null。
* @since 1.6
*/
public E pollLast() {
final Node<E> l = last;
return (l == null) ? null : unlinkLast(l);
}
5.3.11、public E pop() 等價于 removeFirst（）
彈出此清單所代表的堆棧中的元素。 換句話說，删除并傳回此清單的第一個元素。
此方法等同于removeFirst（）。
/**
* @return 此清單所代表的棧頂元素
* @throws NoSuchElementException 如果清單為空
* @since 1.6
*/
public E pop() {
return removeFirst();
}
5.3.12、public void clear()
從此清單中删除所有元素。 此調用傳回後，清單将為空。通過周遊斷開每個節點之間的連結并設定每個節點為null，以幫助GC回收。
public void clear() {
for (Node<E> x = first; x != null; ) {
Node<E> next = x.next;
x.item = null;
x.next = null;
x.prev = null;
x = next;
}
first = last = null;
size = 0;
modCount++;
}
5.4、LinkedList 其它方法
5.4.1、public boolean contains(Object o)
如果此清單包含指定的元素，則傳回true。 當且僅當此清單包含至少一個元素e時才傳回true（o == null？e == null：o.equals（e））。
/**
* @param o 要測試其在此清單中的存在的元素
* @return 如果此清單包含指定的元素，則傳回true
*/
public boolean contains(Object o) {
return indexOf(o) != -1;
}
5.4.2、public int size()
傳回此清單中的元素數量
public int size() {
return size;
}
5.4.3、public E set(int index,E element)
用指定的元素替換此清單中指定位置的元素，并傳回被替換的元素
/**
* Replaces the element at the specified position in this list with the
* specified element.
*
* @param index 指定位置的索引值
* @param element 要存儲在指定位置的元素
* @return 先前在指定位置的元素
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
5.4.4、public ListIterator listIterator(int index)
從清單中的指定位置開始，傳回此清單中元素的清單疊代器（按正确順序）。 遵守List.listIterator（int）的規則。
list-iterator是 fail-fast 的：如果在建立Iterator之後的任何時候對清單進行結構修改，除了通過list-iterator自己的remove或add方法之外，list-iterator将抛出ConcurrentModificationException。
/**
* @param 從list-iterator傳回的第一個元素的索引（通過調用next）
* @return 從清單中的指定位置開始，傳回此清單中元素的ListIterator
* @throws IndexOutOfBoundsException {@inheritDoc}
* @see List#listIterator(int)
*/
public ListIterator<E> listIterator(int index) {
checkPositionIndex(index);
return new ListItr(index);
}
5.4.5、public Iterator descendingIterator()
以相反的順序傳回此雙端隊列中元素的疊代器。 元素将按從尾部 到 頭部 的順序傳回。
/**
* @since 1.6
*/
public Iterator<E> descendingIterator() {
return new DescendingIterator();
}
/**
* Adapter to provide descending iterators via ListItr.previous
*/
private class DescendingIterator implements Iterator<E> {
private final ListItr itr = new ListItr(size());
public boolean hasNext() {
return itr.hasPrevious();
}
public E next() {
return itr.previous();
}
public void remove() {
itr.remove();
}
}
5.4.6、public Object clone()
傳回此LinkedList的淺副本。（元素本身未被克隆。）
public Object clone() {
LinkedList<E> clone = superClone();
// Put clone into "virgin" state
clone.first = clone.last = null;
clone.size = 0;
clone.modCount = 0;
// Initialize clone with our elements
for (Node<E> x = first; x != null; x = x.next)
clone.add(x.item);
return clone;
}
5.4.7、public Object[] toArray()
以适當的順序（從第一個元素到最後一個元素）傳回包含此清單中所有元素的數組。
傳回的數組将是“安全的”，因為此清單不會保留對它的引用。 （換句話說，此方法必須配置設定一個新數組）。 是以調用者可以自由修改傳回的數組。
public Object[] toArray() {
Object[] result = new Object[size];
int i = 0;
for (Node<E> x = first; x != null; x = x.next)
result[i++] = x.item;
return result;
}
5.4.8、public T[] toArray(T[] a)
以适當的順序傳回包含此清單中所有元素的數組（從第一個元素到最後一個元素）; 傳回數組的運作時類型是指定數組的運作時類型。 如果清單适合指定的數組，則傳回其中。 否則，将使用指定數組的運作時類型和此清單的大小配置設定新數組。
如果清單适合指定的數組，并且有空餘空間（即，數組的元素多于清單），則緊跟在清單末尾之後的數組中的元素将設定為null。 僅當調用者知道清單不包含任何null元素時，這在确定清單長度時很有用。
與toArray（）方法一樣，此方法充當基于數組的API和基于集合的API之間的橋梁。 此外，該方法允許精确控制輸出陣列的運作時類型，并且在某些情況下可以用于節省配置設定成本。
假設x是已知僅包含字元串的清單。 以下代碼可用于将清單轉儲到新配置設定的String數組中：
String[] y = x.toArray(new String[0]);
請注意，toArray（new Object [0]）在功能上與toArray（）相同。
public <T> T[] toArray(T[] a) {
if (a.length < size)
a = (T[])java.lang.reflect.Array.newInstance(
a.getClass().getComponentType(), size);
int i = 0;
Object[] result = a;
for (Node<E> x = first; x != null; x = x.next)
result[i++] = x.item;
if (a.length > size)
a[size] = null;
return a;
}
5.4.9、public Spliterator spliterator()
在此清單中的元素上建立一個 late-binding 和 fail-fast 的Spliterator。
@Override
public Spliterator<E> spliterator() {
return new LLSpliterator<E>(this, -1, 0);
}
參考資料：https://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html