深入理解Java双向链表（从零开始掌握Java数据结构中的双向链表实现与操作）

双向链表 vs 单向链表

• 单向链表只能从头到尾遍历；双向链表可以双向遍历。
• 删除或插入节点时，双向链表无需从头查找前驱节点，效率更高。
• 双向链表占用更多内存（每个节点多一个指针）。

Java双向链表的实现步骤

我们将通过以下三步来构建一个完整的双向链表：

1. 定义节点类（Node）
2. 定义双向链表类（DoublyLinkedList）
3. 实现常用操作方法（如添加、删除、遍历等）

1. 定义节点类

每个节点包含三个部分：数据（data）、指向前一个节点的引用（prev）、指向后一个节点的引用（next）。

class Node {    int data;    Node prev;    Node next;    public Node(int data) {        this.data = data;        this.prev = null;        this.next = null;    }}

2. 定义双向链表类

我们需要维护头节点（head）和尾节点（tail），并初始化为空。

public class DoublyLinkedList {    private Node head;    private Node tail;    public DoublyLinkedList() {        this.head = null;        this.tail = null;    }}

3. 实现常用操作方法

下面我们实现几个核心方法：

① 在尾部添加节点（append）

public void append(int data) {    Node newNode = new Node(data);    if (head == null) {        head = tail = newNode;    } else {        tail.next = newNode;        newNode.prev = tail;        tail = newNode;    }}

② 正向遍历（从头到尾）

public void printForward() {    Node current = head;    while (current != null) {        System.out.print(current.data + " ");        current = current.next;    }    System.out.println();}

③ 反向遍历（从尾到头）

public void printBackward() {    Node current = tail;    while (current != null) {        System.out.print(current.data + " ");        current = current.prev;    }    System.out.println();}

④ 删除指定值的节点

public void delete(int data) {    Node current = head;    while (current != null && current.data != data) {        current = current.next;    }    if (current == null) return; // 未找到    if (current.prev != null) {        current.prev.next = current.next;    } else {        head = current.next; // 删除的是头节点    }    if (current.next != null) {        current.next.prev = current.prev;    } else {        tail = current.prev; // 删除的是尾节点    }}

完整示例测试

public class Main {    public static void main(String[] args) {        DoublyLinkedList list = new DoublyLinkedList();        list.append(10);        list.append(20);        list.append(30);        System.out.print("正向遍历: ");        list.printForward(); // 输出: 10 20 30        System.out.print("反向遍历: ");        list.printBackward(); // 输出: 30 20 10        list.delete(20);        System.out.print("删除20后正向: ");        list.printForward(); // 输出: 10 30    }}

总结

通过本教程，你已经掌握了Java双向链表的基本原理和实现方式。双向链表虽然比单向链表占用更多内存，但在需要频繁反向访问或中间插入/删除的场景下，性能更优。建议你动手敲一遍代码，加深理解。

记住，掌握链表操作教程是通往高级数据结构（如树、图）的重要一步。继续加油，你离成为Java高手又近了一步！

SEO关键词回顾：Java双向链表、双向链表实现、Java数据结构、链表操作教程