Java手写链表全攻略：从单链表到双向链表的底层实现艺术

在Java集合框架中，LinkedList虽然提供了现成的链表实现，但手写链表却是深入理解数据结构、提升编程能力的必经之路。本文将带领读者从零构建单链表与双向链表，剖析核心设计思想，并实现常见高阶操作。

一、链表的设计哲学：从理论到代码

1. 链表的本质
链表是一种非连续存储的线性表，每个节点（Node）包含数据域（存储元素）和指针域（指向相邻节点）。这种结构天然支持动态内存分配，避免了数组扩容时的数据迁移开销。

2. 节点类的定义
单链表节点只需next指针，而双向链表需额外维护prev指针：

// 单链表节点
class SingleNode<T> {T data;SingleNode<T> next;public SingleNode(T data) {this.data = data;}
}// 双向链表节点
class DoubleNode<T> {T data;DoubleNode<T> prev;DoubleNode<T> next;public DoubleNode(T data) {this.data = data;}
}

3. 抽象层次设计
通过接口与抽象类实现代码复用（面向接口编程）：

// 链表操作接口
interface MyList<T> {void add(T element);void add(int index, T element);T remove(int index);T get(int index);int size();
}// 抽象共性逻辑
abstract class AbstractList<T> implements MyList<T> {protected int size;@Overridepublic int size() {return size;}protected void checkIndexForAdd(int index) {if (index < 0 || index > size) throw new IndexOutOfBoundsException();}
}

二、单链表的实现：增删查改全流程

1. 核心属性与初始化

public class SingleLinkedList<T> extends AbstractList<T> {private SingleNode<T> head; // 虚拟头节点private SingleNode<T> tail; // 尾指针优化public SingleLinkedList() {head = new SingleNode<>(null); // 哨兵节点tail = head;}
}

2. 尾部插入（O(1)时间复杂度）
利用尾指针避免遍历：

@Override
public void add(T element) {SingleNode<T> newNode = new SingleNode<>(element);tail.next = newNode;tail = newNode;size++;
}

3. 指定位置插入（O(n)时间复杂度）
通过遍历定位前驱节点：

@Override
public void add(int index, T element) {checkIndexForAdd(index);SingleNode<T> prev = getPrevNode(index);SingleNode<T> newNode = new SingleNode<>(element);newNode.next = prev.next;prev.next = newNode;if (prev == tail) tail = newNode;size++;
}private SingleNode<T> getPrevNode(int index) {SingleNode<T> curr = head;for (int i = 0; i < index; i++) {curr = curr.next;}return curr;
}

4. 删除操作
调整指针引用并释放节点：

@Override
public T remove(int index) {checkIndex(index);SingleNode<T> prev = getPrevNode(index);SingleNode<T> removed = prev.next;prev.next = removed.next;if (removed == tail) tail = prev;size--;return removed.data;
}

三、双向链表的进阶实现

1. 结构优化
维护头尾指针实现双向遍历：

public class DoubleLinkedList<T> extends AbstractList<T> {private DoubleNode<T> head; // 虚拟头节点private DoubleNode<T> tail; // 虚拟尾节点public DoubleLinkedList() {head = new DoubleNode<>(null);tail = new DoubleNode<>(null);head.next = tail;tail.prev = head;}
}

2. 中间插入的高效实现

@Override
public void add(int index, T element) {checkIndexForAdd(index);DoubleNode<T> nextNode = getNode(index);DoubleNode<T> prevNode = nextNode.prev;DoubleNode<T> newNode = new DoubleNode<>(element);prevNode.next = newNode;newNode.prev = prevNode;newNode.next = nextNode;nextNode.prev = newNode;size++;
}private DoubleNode<T> getNode(int index) {// 二分法优化遍历方向if (index < size / 2) {DoubleNode<T> curr = head.next;for (int i = 0; i < index; i++) {curr = curr.next;}return curr;} else {DoubleNode<T> curr = tail;for (int i = size; i > index; i--) {curr = curr.prev;}return curr;}
}

四、高阶操作实战：算法思维训练

1. 链表反转（迭代法）
三指针法实现原地反转：

public void reverse() {SingleNode<T> prev = null;SingleNode<T> curr = head.next;while (curr != null) {SingleNode<T> next = curr.next;curr.next = prev;prev = curr;curr = next;}head.next = prev;
}

2. 环形检测（快慢指针）
Floyd判圈算法的经典应用：

public boolean hasCycle() {if (head.next == null) return false;SingleNode<T> slow = head.next;SingleNode<T> fast = head.next.next;while (fast != null && fast.next != null) {if (slow == fast) return true;slow = slow.next;fast = fast.next.next;}return false;
}

3. 合并有序链表
递归实现更简洁：

public static SingleNode<Integer> mergeSortedLists(SingleNode<Integer> l1, SingleNode<Integer> l2) {if (l1 == null) return l2;if (l2 == null) return l1;if (l1.data < l2.data) {l1.next = mergeSortedLists(l1.next, l2);return l1;} else {l2.next = mergeSortedLists(l1, l2.next);return l2;}
}