引言

鏈表作為基礎數據結構之一，在Java集合框架中以LinkedList的形式提供。本文將深入分析Java原生LinkedList的實現機制，并介紹我自定義實現的MyLinkedList，最后對比兩者的設計差異與實現特點。

Java原生LinkedList解析

基本結構

Java的LinkedList是基于雙向鏈表實現的列表，主要特點包括：

1. 雙向鏈表結構：每個節點包含前驅和后繼指針

2. 高效端點操作：頭尾插入/刪除時間復雜度為O(1)

3. 隊列功能：實現了Deque接口，支持隊列操作

核心實現機制

// JDK中的關鍵字段
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;}
}

插入操作示例：

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

時間復雜度分析：

• 頭尾插入/刪除：O(1)

• 按索引訪問：平均O(n/2)

• 中間插入/刪除：O(n)（需要先定位節點）

自定義MyLinkedList實現

package com.zsy;import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Objects;/*** 自定義雙向鏈表實現，支持泛型元素存儲和基本列表操作** <p>本實現提供類似Java LinkedList的核心功能，包括：</p>* <ul>*   <li>基于節點的雙向鏈表結構</li>*   <li>支持頭部和尾部高效操作</li>*   <li>提供元素遍歷功能</li>*   <li>實現基本的增刪改查操作</li>* </ul>** <p><b>特性說明：</b></p>* <ul>*   <li>時間復雜度：訪問O(n)，頭尾操作O(1)</li>*   <li>空間復雜度：O(n)</li>*   <li><b>非線程安全</b> - 多線程環境下需要外部同步</li>* </ul>** @param <E> 列表元素類型* @author zsy* @see List*/
public class MyLinkedList<E> implements List<E> {/*** 當前列表中元素的數量*/private int size;/*** 鏈表頭節點*/private Node<E> head;/*** 鏈表尾節點*/private Node<E> tail;/*** 將指定元素追加到列表末尾** @param element 要添加的元素*/@Overridepublic void add(E element) {Node<E> newNode = new Node<>(tail, element, null);if (tail != null) {tail.next = newNode;} else {head = newNode;}tail = newNode;size++;}/*** 在列表的指定位置插入指定元素** @param element 要插入的元素* @param index 插入位置的索引* @throws IndexOutOfBoundsException 如果索引超出范圍*/@Overridepublic void add(E element, int index) {rangeCheckForAdd(index);if (index == size) {add(element);return;}Node<E> target = getNode(index);Node<E> prev = target.pre;Node<E> newNode = new Node<>(prev, element, target);if (prev == null) {head = newNode;} else {prev.next = newNode;}target.pre = newNode;size++;}/*** 移除并返回列表中指定位置的元素** @param index 要移除元素的索引* @return 被移除的元素* @throws IndexOutOfBoundsException 如果索引超出范圍*/@Overridepublic E remove(int index) {rangeCheck(index);return unlink(getNode(index));}/*** 從列表中移除首次出現的指定元素** @param element 要移除的元素* @return 如果列表包含該元素則返回true*/@Overridepublic boolean remove(E element) {for (Node<E> x = head; x != null; x = x.next) {if (Objects.equals(element, x.value)) {unlink(x);return true;}}return false;}/*** 替換列表中指定位置的元素** @param index 要替換元素的索引* @param element 要存儲的元素* @return 先前在指定位置的元素* @throws IndexOutOfBoundsException 如果索引超出范圍*/@Overridepublic E set(int index, E element) {rangeCheck(index);Node<E> node = getNode(index);E oldVal = node.value;node.value = element;return oldVal;}/*** 返回列表中指定位置的元素** @param index 要返回元素的索引* @return 列表中指定位置的元素* @throws IndexOutOfBoundsException 如果索引超出范圍*/@Overridepublic E get(int index) {rangeCheck(index);return getNode(index).value;}/*** 返回列表中的元素數量** @return 列表中的元素數量*/@Overridepublic int size() {return size;}/*** 返回此列表中元素的迭代器** @return 按適當順序包含此列表中所有元素的迭代器*/@Overridepublic Iterator<E> iterator() {return new LinkedListIterator();}// ========== 私有輔助方法 ==========/*** 獲取指定索引處的節點*/private Node<E> getNode(int index) {if (index < (size >> 1)) {Node<E> x = head;for (int i = 0; i < index; i++)x = x.next;return x;} else {Node<E> x = tail;for (int i = size - 1; i > index; i--)x = x.pre;return x;}}/*** 從鏈表中移除指定節點*/private E unlink(Node<E> node) {final E element = node.value;final Node<E> next = node.next;final Node<E> prev = node.pre;if (prev == null) {head = next;} else {prev.next = next;node.pre = null;}if (next == null) {tail = prev;} else {next.pre = prev;node.next = null;}node.value = null;size--;return element;}/*** 檢查索引是否在有效范圍內*/private void rangeCheck(int index) {if (index < 0 || index >= size)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}/*** 檢查添加操作的索引是否在有效范圍內*/private void rangeCheckForAdd(int index) {if (index < 0 || index > size)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}/*** 構造索引越界異常信息*/private String outOfBoundsMsg(int index) {return "Index: "+index+", Size: "+size;}// ========== 內部類實現 ==========/*** 雙向鏈表節點實現*/private static class Node<E> {/*** 前驅節點*/Node<E> pre;/*** 后繼節點*/Node<E> next;/*** 節點存儲的值*/E value;Node(Node<E> pre, E value, Node<E> next) {this.pre = pre;this.value = value;this.next = next;}}/*** 鏈表迭代器實現*/private class LinkedListIterator implements Iterator<E> {/*** 當前迭代節點*/private Node<E> current = head;/*** 檢查是否還有更多元素可迭代** @return 如果迭代有更多元素則返回true*/@Overridepublic boolean hasNext() {return current != null;}/*** 返回迭代中的下一個元素** @return 迭代中的下一個元素* @throws NoSuchElementException 如果迭代沒有更多元素*/@Overridepublic E next() {if (!hasNext())throw new NoSuchElementException();E element = current.value;current = current.next;return element;}}
}

性能考慮

雙向鏈表與數組列表的性能對比：

操作	ArrayList	LinkedList
隨機訪問	O(1)	O(n)
頭部插入/刪除	O(n)	O(1)
尾部插入/刪除	平均O(1)	O(1)
中間插入/刪除	O(n)	O(n)
內存占用	更緊湊	每個元素額外占用空間