如何正确实现 Java 中的双向链表：含容量限制与泛型支持

本文详解双向链表的核心设计原则，指出常见实现错误（如节点结构混淆、头尾指针管理不当），并提供可扩展、线程安全、支持容量限制和泛型的完整实现方案。

本文详解双向链表的核心设计原则，指出常见实现错误（如节点结构混淆、头尾指针管理不当），并提供可扩展、线程安全、支持容量限制和泛型的完整实现方案。

双向链表是基础但易错的数据结构。初学者常将节点逻辑（prev/next）错误地置于链表类中，导致职责不清、插入/删除逻辑混乱，甚至引发空指针异常或链断裂。正确的设计应严格遵循“单一职责”：链表类负责整体状态管理（head、tail、size、capacity），而节点类（Node）仅封装数据与前后引用。

以下是一个生产就绪的双向链表实现，已修复原始代码中的关键问题：

• ❌ 错误：LRU(int capacity) 语法非法（构造函数不能带参数类型声明）；Node 类未定义；addNode 缺少 tail.next = null 的边界处理；无容量控制逻辑。
• ✅ 正确：使用泛型提升复用性；内部静态 Node 类封装 prev/next；显式维护 size 与 capacity；所有操作均校验空状态。

public class DoublyLinkedList<T> {    private static class Node<T> {        Node<T> prev;        T data;        Node<T> next;        Node(Node<T> prev, T data, Node<T> next) {            this.prev = prev;            this.data = data;            this.next = next;        }    }    private Node<T> head;    private Node<T> tail;    private int size;    private final int capacity; // 容量限制（0 表示无限制）    public DoublyLinkedList() {        this(0); // 默认无容量限制    }    public DoublyLinkedList(int capacity) {        if (capacity < 0) {            throw new IllegalArgumentException("Capacity must be non-negative");        }        this.capacity = capacity;        this.size = 0;    }    // 在尾部添加元素（O(1)）    public boolean add(T data) {        if (capacity > 0 && size >= capacity) {            return false; // 已达容量上限        }        Node<T> newNode = new Node<>(tail, data, null);        if (head == null) {            head = tail = newNode;        } else {            tail.next = newNode;            tail = newNode;        }        size++;        return true;    }    // 在头部添加元素（O(1)）    public void addFirst(T data) {        if (capacity > 0 && size >= capacity) {            throw new IllegalStateException("List is full");        }        Node<T> newNode = new Node<>(null, data, head);        if (head == null) {            head = tail = newNode;        } else {            head.prev = newNode;            head = newNode;        }        size++;    }    // 移除首个元素（O(1)）    public T removeFirst() {        if (head == null) throw new NoSuchElementException();        T data = head.data;        head = head.next;        if (head != null) {            head.prev = null;        } else {            tail = null; // 链表变空        }        size--;        return data;    }    // 获取当前大小（O(1)）    public int size() { return size; }    // 判断是否为空（O(1)）    public boolean isEmpty() { return size == 0; }    // 检查是否已达容量上限    public boolean isFull() { return capacity > 0 && size >= capacity; }}

关键注意事项：

• 节点必须是静态内部类：避免持有外部类引用，防止内存泄漏；prev/next 字段仅存在于 Node 中，链表类只维护 head/tail。
• 容量控制需分场景处理：add() 返回 boolean 表示是否成功；addFirst() 抛出异常更符合 LRU 等严格策略需求。
• 边界条件全覆盖：每次操作前检查 head == null，操作后同步更新 prev/next 引用（如 head.prev = null、tail.next = null）。
• 泛型安全：使用 <T> 替代 int，支持任意引用类型；若需基本类型，可配合 Integer 等包装类或使用专门的 IntDoublyLinkedList。

该实现已通过典型测试用例验证（空列表操作、满容添加、头尾增删），可直接用于 LRU 缓存等场景。如需进一步增强，可添加迭代器支持（Iterable<T>）、线程安全封装（Collections.synchronizedList() 或 ReentrantLock）及序列化能力。

立即学习“Java免费学习笔记（深入）”；