Java中双向链表详解及实例

什么是双向链表？

双向链表是一种经典的线性数据结构，它不仅能够支持插入、删除操作，而且还能够支持在链表中任何位置进行查找操作。

双向链表的每个节点都有两个指针，分别是指向前驱节点和后继节点的指针，这样就可以通过前向和后向遍历节点，从而实现各种操作。

双向链表的定义

下面是Java语言中双向链表的定义：

class Node {
    int data;
    Node prev;
    Node next;

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

其中，data表示节点中的数据，prev表示节点的前驱节点，next表示节点的后继节点。

双向链表的基本操作

双向链表的基本操作包括插入、删除和查找，下面分别讲解。

插入操作

双向链表的插入操作有三中情况：

1. 在双向链表的头部插入节点
2. 在双向链表的尾部插入节点
3. 在双向链表的中间插入节点

在双向链表的头部插入节点

在双向链表的头部插入节点的代码如下：

public void addFirst(Node node) {
    if(head == null) {
        head = node;
        tail = node;
    } else {
        node.next = head;
        head.prev = node;
        head = node;
    }
}

说明：

• 如果链表为空，将新加入的节点同时作为头指针和尾指针。
• 如果链表不为空，则将新加入的节点与原来的头节点相连，同时将新加入的节点设为头节点。

在双向链表的尾部插入节点

在双向链表的尾部插入节点的代码如下：

public void addLast(Node node) {
    if(tail == null) {
        head = node;
        tail = node;
    } else {
        node.prev = tail;
        tail.next = node;
        tail = node;
    }
}

说明：

• 如果链表为空，将新加入的节点同时作为头指针和尾指针。
• 如果链表不为空，则将新加入的节点与原来的尾节点相连，同时将新加入的节点设为尾节点。

在双向链表的中间插入节点

在双向链表的中间插入节点的代码如下：

public void addAfter(Node node, Node newNode) {
    if(node == null || newNode == null) {
        return;
    }
    newNode.prev = node;
    newNode.next = node.next;
    if(node.next != null) {
        node.next.prev = newNode;
    } else {
        tail = newNode;
    }
    node.next = newNode;
}

说明：

• 首先判断空指针的情况。
• 将新加入的节点与原节点相连。
• 注意判断原节点是否为尾节点的情况。

删除操作

双向链表的删除操作也有三中情况：

1. 删除双向链表的头节点
2. 删除双向链表的尾节点
3. 删除双向链表的中间节点

删除双向链表的头节点

删除双向链表的头节点的代码如下：

public void removeFirst() {
    if(head == null) {
        return;
    }
    if(head == tail) {
        head = null;
        tail = null;
    } else {
        head = head.next;
        head.prev = null;
    }
}

说明：

• 如果链表为空，则直接退出。
• 如果链表中只有一个节点，则将头指针和尾指针都设为空。
• 如果链表中不止一个节点，则将头指针设为原来头节点的下一个节点，并将新头节点的前驱指针设为空。

删除双向链表的尾节点

删除双向链表的尾节点的代码如下：

public void removeLast() {
    if(tail == null) {
        return;
    }
    if(head == tail) {
        head = null;
        tail = null;
    } else {
        tail = tail.prev;
        tail.next = null;
    }
}

说明：

• 如果链表为空，则直接退出。
• 如果链表中只有一个节点，则将头指针和尾指针都设为空。
• 如果链表中不止一个节点，则将尾指针设为原来尾节点的前一个节点，并将新尾节点的后继指针设为空。

删除双向链表的中间节点

删除双向链表的中间节点的代码如下：

public void removeNode(Node node) {
    if(node == null) {
        return;
    }
    if(head == node) {
        removeFirst();
    } else if(tail == node) {
        removeLast();
    } else {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
}

说明：

• 首先判断空指针的情况。
• 如果要删除的是头节点，则直接调用上面的删除头节点的函数。
• 如果要删除的是尾节点，则直接调用上面的删除尾节点的函数。
• 如果要删除的节点在中间，则将要删除的节点相邻的节点相连起来即可。

查找操作

双向链表的查找操作可以按照元素值或者位置进行查找。以下示例演示如何通过元素值进行查找：

public Node findNode(int data) {
    Node cur = head;
    while(cur != null) {
        if(cur.data == data) {
            return cur;
        }
        cur = cur.next;
    }
    return null;
}

说明：

• 从头节点开始遍历整个链表。
• 如果节点的元素值等于要查找的值，则返回该节点。
• 如果遍历完整个链表都没有找到对应的节点，则返回空指针。

双向链表的测试示例

下面展示如何对上述代码进行测试：

public class Test {
    public static void main(string[] args) {
        DoublyLinkedList list = new DoublyLinkedList();
        list.addFirst(new Node(1));
        list.addFirst(new Node(2));
        list.addFirst(new Node(3));
        list.addLast(new Node(4));
        list.addLast(new Node(5));
        list.removeLast();
        list.removeFirst();
        Node node = list.findNode(2);
        list.removeNode(node);
    }
}

说明：

• 首先创建一个双向链表对象。
• 对链表进行一系列的插入、删除和查找操作。
• 最后打印出链表来查看结果。

双向链表的应用场景

双向链表可以用于许多数据存储的场景，比如某些排序算法的实现，也可以作为其他数据结构的底层实现，比如Java集合框架中的LinkedList类就是基于双向链表实现的。