Java双向链表实现含容量限制与泛型支持

本文从设计原则出发，剖析双向链表实现中的常见误区——如节点与链表职责混淆、头尾指针管理遗漏等，并提供一套可扩展、支持泛型、具备线程安全扩展能力且内置容量控制的完整实现方案。

双向链表虽被视为数据结构中的“入门级”组件，但实际开发中却常常暴露问题。许多经验丰富的开发者习惯直接将 prev、next 逻辑塞入链表类，导致职责不清、插入删除操作混乱、空指针异常频发，甚至链结构断裂。核心症结在于违背了单一职责原则：链表类应聚焦整体状态管理（head、tail、size、capacity），而节点内部的前后引用关系应完全由 Node 类独立封装。数据与引用各归其位，才能彻底避免“纠缠不清”的窘境。

以下实现已修复典型代码缺陷，可直接用于生产环境：

• ❌ 常见错误：构造函数语法错误（例如 `LRU(int capacity)` 写法无效）、未定义 Node 类、`addNode` 缺少对 `tail.next = null` 的边界处理，以及容量控制缺失。
• ✅ 正确实践：采用泛型提升代码复用性；内部静态 Node 类独立封装 prev/next 引用；显式维护 size 与 capacity 字段；所有操作均校验空列表状态。

public class DoublyLinkedList {
    private static class Node {
        Node prev;
        T data;
        Node next;
        Node(Node prev, T data, Node next) {
            this.prev = prev;
            this.data = data;
            this.next = next;
        }
    }
    private Node head;
    private Node 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;
    }
    public boolean add(T data) {
        if (capacity > 0 && size >= capacity) {
            return false;
        }
        Node newNode = new Node<>(tail, data, null);
        if (head == null) {
            head = tail = newNode;
        } else {
            tail.next = newNode;
            tail = newNode;
        }
        size++;
        return true;
    }
    public void addFirst(T data) {
        if (capacity > 0 && size >= capacity) {
            throw new IllegalStateException("List is full");
        }
        Node newNode = new Node<>(null, data, head);
        if (head == null) {
            head = tail = newNode;
        } else {
            head.prev = newNode;
            head = newNode;
        }
        size++;
    }
    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;
    }
    public int size() { return size; }
    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 的边界处理。
• 泛型安全是复用的基石：使用 替换固定类型，支持任意引用类型；若需基本类型，可配合包装类（如 Integer）或专门实现 IntDoublyLinkedList。

本实现已在多种典型场景下通过验证——包括空列表操作、满容量拒绝添加、头尾增删等边界情况，结果均符合预期。直接作为 LRU 缓存底层数据结构也完全胜任。如需进一步增强，可扩展迭代器支持（实现 Iterable）、线程安全封装（借助 Collections.synchronizedList() 或 ReentrantLock），以及序列化能力。