Java如何实现双向链表功能

Java如何实现双向链表功能？

1. 双向链表简介

双向链表（Doubly Linked List），也叫作双向链式线性表，一般存在于数据结构相关的教材或面试题中，是一种线性数据结构。

和普通的链表不同的是，双向链表每个节点都有两个指针，一个指向下一个节点，一个指向上一个节点。这样可以从任何一个节点开始，依次向前或向后遍历整个链表，也可以在任何节点处插入或删除节点。

2. 双向链表实现方式

2.1 节点定义

在Java中，我们可以通过定义一个双向链表节点类来实现双向链表的基本功能。根据双向链表的定义，我们的节点需要手动维护两个指针，一个指向前一个节点，一个指向后一个节点。

public class DNode {
    Object data;
    DNode prev;
    DNode next;

    public DNode(Object data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

在这个例子中，我们定义了一个DNode（Double Linked Node，双向链表节点）类，每个节点包含了数据和前一个节点、后一个节点的指针。其中prev指针指向前一个节点，next指针指向后一个节点。初始时，prev和next为null，表示这个节点没有前一个节点和后一个节点。

2.2 添加节点

当我们需要在双向链表中添加节点时，需要在链表中找到需要添加的位置，然后插入新的节点。

public void add(Object data) {
    // 创建新节点，并赋值
    DNode newNode = new DNode(data);
    // 链表为空时，新节点即头节点又是尾节点
    if (head == null) {
        head = newNode;
        tail = newNode;
    } else {
        // 链表不为空，寻找合适的位置插入
        DNode current = head;
        while (current != null) {
            // 如果插入位置为头部
            if (current == head && (int)data < (int)head.data) {
                newNode.next = head;
                head.prev = newNode;
                head = newNode;
                break;
            }
            // 如果插入位置为中间
            if (current != tail && (int)data >= (int)current.data && (int)data < (int)current.next.data) {
                newNode.prev = current;
                newNode.next = current.next;
                current.next.prev = newNode;
                current.next = newNode;
                break;
            }
            // 如果插入位置为尾部
            if (current == tail && (int)data >= (int)current.data) {
                current.next = newNode;
                newNode.prev = current;
                tail = newNode;
                break;
            }
            current = current.next;
        }
    }
}

2.3 删除节点

当我们需要在双向链表中删除节点时，需要找到要删除的节点，并调整前后节点的指针指向。

public void remove(Object data) {
    if (head == null) {
        System.out.println("链表为空！");
        return;
    }

    DNode current = head;
    while (current != null) {
        if (current.data.equals(data)) {
            // 如果删除的节点是头节点
            if (current == head) {
                head = head.next;
                head.prev = null;
            // 如果删除的节点是尾节点
            } else if (current == tail) {
                tail = tail.prev;
                tail.next = null;
            } else {
                current.prev.next = current.next;
                current.next.prev = current.prev;
            }
            return;
        }
        current = current.next;
    }
    System.out.println("链表中无此节点！");
}

3. 示例说明

3.1 示例一 - 从头节点开始遍历

public void traverseForward() {
    System.out.println("正序遍历：");
    DNode current = head;
    while (current != null) {
        System.out.print(current.data + " -> ");
        current = current.next;
    }
    System.out.println("null");
}

3.2 示例二 - 从尾节点开始遍历

public void traverseBackward() {
    System.out.println("反序遍历：");
    DNode current = tail;
    while (current != null) {
        System.out.print(current.data + " -> ");
        current = current.prev;
    }
    System.out.println("null");
}

这两个示例都是遍历整个双向链表的方法，只是一种从头开始，一种从尾开始。遍历过程中，通过每个节点的next和prev指针，依此查找前一个节点和后一个节点，并依次遍历下去。