## 深入分析 Java 中的 `LinkedList` 源碼

`LinkedList` 是 Java 集合框架中的一個重要類，它基于雙向鏈表實現，提供了高效的插入和刪除操作。與 `ArrayList` 不同，`LinkedList` 的結構使其在特定操作上有更優的性能表現。本文將詳細分析 `LinkedList` 的源碼，包括其數據結構、構造方法、核心操作等。

### 1. `LinkedList` 的基本數據結構

`LinkedList` 是基于雙向鏈表實現的，這意味著每個節點都包含對前一個節點和后一個節點的引用。`LinkedList` 主要由以下幾個關鍵字段組成：

```java
public class LinkedList<E> extends AbstractSequentialList<E>
? ? ? ? implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
? ? transient int size = 0;
? ? transient Node<E> first;
? ? transient Node<E> last;

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

- `size`：鏈表中的元素數量。
- `first`：指向鏈表的第一個節點。
- `last`：指向鏈表的最后一個節點。
- `Node`：鏈表節點的內部類，每個節點包含元素數據和前后節點的引用。

### 2. 構造方法

`LinkedList` 提供了多個構造方法：

#### 2.1 默認構造方法

```java
public LinkedList() {
}
```

默認構造方法初始化一個空的鏈表。

#### 2.2 從另一個集合創建 `LinkedList`

```java
public LinkedList(Collection<? extends E> c) {
? ? this();
? ? addAll(c);
}
```

此構造方法從另一個集合創建 `LinkedList`，并將集合中的所有元素添加到鏈表中。

### 3. 核心操作方法

#### 3.1 添加元素

`LinkedList` 提供了多種添加元素的方法：

##### 3.1.1 在鏈表末尾添加元素

```java
public boolean add(E e) {
? ? linkLast(e);
? ? return true;
}

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

- `add(E e)`：在鏈表末尾添加元素。
- `linkLast(E e)`：將新節點鏈接到鏈表的末尾。如果鏈表為空，則新節點既是 `first` 也是 `last`。

##### 3.1.2 在指定位置插入元素

```java
public void add(int index, E element) {
? ? checkPositionIndex(index);

? ? if (index == size)
? ? ? ? linkLast(element);
? ? else
? ? ? ? linkBefore(element, node(index));
}

void linkBefore(E e, Node<E> succ) {
? ? 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++;
}
```

- `add(int index, E element)`：在指定位置插入元素。
- `linkBefore(E e, Node<E> succ)`：在指定節點之前插入新節點。
- `node(int index)`：返回指定位置的節點。

##### 3.1.3 添加元素到鏈表的頭部

```java
public void addFirst(E e) {
? ? linkFirst(e);
}

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

- `addFirst(E e)`：在鏈表頭部添加元素。
- `linkFirst(E e)`：將新節點鏈接到鏈表的頭部。如果鏈表為空，則新節點既是 `first` 也是 `last`。

#### 3.2 刪除元素

`LinkedList` 提供了多種刪除元素的方法：

##### 3.2.1 刪除指定位置的元素

```java
public E remove(int index) {
? ? checkElementIndex(index);
? ? return unlink(node(index));
}

E unlink(Node<E> x) {
? ? 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;
}
```

- `remove(int index)`：刪除指定位置的元素。
- `unlink(Node<E> x)`：斷開指定節點的鏈接，并返回節點中的元素。

##### 3.2.2 刪除鏈表的頭部元素

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

private E unlinkFirst(Node<E> f) {
? ? final E element = f.item;
? ? final Node<E> next = f.next;
? ? f.item = null;
? ? f.next = null; // help GC
? ? first = next;
? ? if (next == null)
? ? ? ? last = null;
? ? else
? ? ? ? next.prev = null;
? ? size--;
? ? modCount++;
? ? return element;
}
```

- `removeFirst()`：刪除鏈表的頭部元素。
- `unlinkFirst(Node<E> f)`：斷開頭部節點的鏈接，并返回節點中的元素。

##### 3.2.3 刪除鏈表的尾部元素

```java
public E removeLast() {
? ? final Node<E> l = last;
? ? if (l == null)
? ? ? ? throw new NoSuchElementException();
? ? return unlinkLast(l);
}

private E unlinkLast(Node<E> l) {
? ? final E element = l.item;
? ? final Node<E> prev = l.prev;
? ? l.item = null;
? ? l.prev = null; // help GC
? ? last = prev;
? ? if (prev == null)
? ? ? ? first = null;
? ? else
? ? ? ? prev.next = null;
? ? size--;
? ? modCount++;
? ? return element;
}
```

- `removeLast()`：刪除鏈表的尾部元素。
- `unlinkLast(Node<E> l)`：斷開尾部節點的鏈接，并返回節點中的元素。

#### 3.3 獲取元素和修改元素

`LinkedList` 提供了獲取和修改元素的方法：

##### 3.3.1 獲取元素

```java
public E get(int index) {
? ? checkElementIndex(index);
? ? return node(index).item;
}

Node<E> node(int 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;
? ? }
}
```

- `get(int index)`：根據索引獲取元素。
- `node(int index)`：返回指定位置的節點，通過判斷索引位置決定從前往后還是從后往前遍歷，提高效率。

##### 3.3.2 修改元素

```java
public E set(int index, E element) {
? ? checkElementIndex(index);
? ? Node<E> x = node(index);
? ? E oldVal = x.item;
? ? x.item = element;
? ? return oldVal;
}
```

- `set(int index, E element)`：根據索引修改元素，并返回舊元素。

### 4. 雙向鏈表的結構特點

#### 4.1 鏈表節點的定義

在 `LinkedList` 中，每個節點包含一個元素和對前后節點的引用：

```java
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;
? ? }
}
```

- `item`：存儲節點的元素。
- `next`：指向下一個節點。
- `prev`：指向前一個節點。

#### 4.2 鏈表的首尾節點

`LinkedList` 通過 `first` 和 `last` 字段分別指向鏈表的首節點和尾節點，這樣可以高效地進行頭部和尾部的插入和刪除操作。