在Java中，`LinkedList` 类实现了 `List` 接口和 `Deque` 接口，它本质上是一个双向链表。双向链表是一种链式数据结构，其中每个节点都包含三个部分：数据域、指向前一个节点的指针（prev），以及指向后一个节点的指针（next）。这种结构允许从链表的头部或尾部高效地添加、删除元素，同时也支持快速的随机访问（尽管在实际应用中，由于链表的特性，随机访问的效率相对较低，特别是在链表很长时）。下面，我们将深入探讨Java中`LinkedList`类是如何实现双向链表的，以及它提供的一些关键操作。 ### 双向链表的基本结构 在双向链表中，每个节点（`Node`）通常包含以下部分： - **数据域**：存储节点的数据。 - **prev指针**：指向前一个节点的引用（或`null`，如果是第一个节点）。 - **next指针**：指向后一个节点的引用（或`null`，如果是最后一个节点）。 在Java的`LinkedList`类中，这样的节点被封装为内部类`Node`，以保持封装性。 ### LinkedList的内部实现 #### Node内部类 Java的`LinkedList`类中定义了一个名为`Node`的静态内部类，用于表示链表中的节点。这个内部类大致如下（简化版）： ```java private static class Node { E item; // 数据域 Node next; // 指向下一个节点的指针 Node prev; // 指向前一个节点的指针 Node(Node prev, E element, Node next) { this.item = element; this.next = next; this.prev = prev; } } ``` #### 主要成员变量 `LinkedList`类还包含几个关键的成员变量，用于维护链表的状态： - `size`：链表中元素的数量。 - `first`：指向链表第一个节点的引用。 - `last`：指向链表最后一个节点的引用。 #### 构造函数 `LinkedList`的构造函数主要初始化这些成员变量，通常将`first`和`last`都设置为`null`，表示一个空链表。 #### 添加元素 在双向链表中添加元素通常涉及修改`prev`和`next`指针。例如，在链表末尾添加元素时，需要更新最后一个节点的`next`指针，使其指向新节点，并更新新节点的`prev`指针指向原来的最后一个节点，然后将`last`指针指向新节点。 ```java public boolean add(E e) { linkLast(e); return true; } void linkLast(E e) { final Node l = last; final Node newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; } ``` 在链表头部添加元素时，过程类似，但方向相反。 #### 删除元素 删除元素同样需要修改指针。例如，删除链表中的某个节点时，需要将其前一个节点的`next`指针指向其后一个节点，并将其后一个节点的`prev`指针指向前一个节点（如果这两个节点存在的话）。然后，将待删除节点的`prev`和`next`都设置为`null`（这一步是可选的，因为一旦没有其他引用指向该节点，它就会被垃圾收集器回收）。 ```java public E remove(int index) { checkElementIndex(index); return unlink(node(index)); } E unlink(Node x) { // assert x != null; final E element = x.item; final Node next = x.next; final Node 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; } ``` #### 遍历链表 遍历双向链表可以从头部开始，沿着`next`指针一直走到链表末尾；或者从尾部开始，沿着`prev`指针一直走到链表开头。`LinkedList`类提供了多种遍历方式，包括迭代器（Iterator）和分割器（Spliterator），它们内部都利用了这种双向遍历的能力。 ### 双向链表的优势 双向链表相比单向链表的主要优势在于其双向遍历的能力，这使得在链表两端添加或删除元素变得更加高效。此外，双向链表还可以支持更复杂的操作，比如在不改变元素顺序的情况下反转链表，这在某些应用场景下非常有用。 ### 总结 Java中的`LinkedList`类通过内部类`Node`实现了双向链表，利用`prev`和`next`指针维护了节点之间的双向连接。这种结构使得`LinkedList`在添加、删除元素时具有高效的性能，尤其是在链表的两端操作时。同时，双向链表还支持快速的遍历，以及更复杂的链表操作，如反转链表等。通过深入研究`LinkedList`的内部实现，我们可以更好地理解双向链表的工作原理及其在Java集合框架中的应用。 在码小课网站上，我们深入探讨了更多关于数据结构和算法的内容，不仅限于Java的`LinkedList`，还包括其他高级数据结构和算法的实现与优化，帮助开发者们更好地掌握编程技能，提升代码质量和效率。希望这篇文章能为您在理解Java中`LinkedList`的双向链表实现上提供一些帮助。