如何从 Java 中的链表中删除节点

Java 3月前 152

在 Java 中，链表是一种常用的数据结构，用于存储和操作一系列元素。在实际开发中，我们经常需要删除链表中的某个节点。本文将详细介绍如何在 Java 中删除链表中的节点，并提供一些注意事项。

单向链表删除节点：

在单向链表中，每个节点通常只包含指向下一个节点的引用，因此删除节点需要特殊处理。我们需要找到要删除的节点的前一个节点，然后将其引用指向要删除的节点的下一个节点。

示例：

public class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }
}

public class LinkedList {
    private ListNode head;

    public void deleteNode(int value) {
        ListNode current = head;
        ListNode previous = null;

        while (current != null) {
            if (current.val == value) {
                if (previous == null) {
                    // 删除头节点
                    head = current.next;
                } else {
                    previous.next = current.next;
                }
                return;
            }

            previous = current;
            current = current.next;
        }
    }
}

上述示例中，我们首先在 LinkedList 类中定义了一个 deleteNode 方法，接受一个参数 value，表示要删除的节点的值。然后我们使用双指针来遍历链表，current 指向当前节点，previous 指向前一个节点。如果当前节点的值等于要删除的值，则将前一个节点的 next 指向当前节点的下一个节点，实现删除。需要注意的是，如果要删除的节点是头节点，我们需要特殊处理。

双向链表删除节点：

双向链表相较于单向链表，每个节点包含对前一个节点和后一个节点的引用。因此，删除节点的过程比较简单，只需要更改当前节点前后节点的引用即可。

示例：

public class DoublyListNode {
    int val;
    DoublyListNode prev;
    DoublyListNode next;

    DoublyListNode(int val) {
        this.val = val;
    }
}

public class DoublyLinkedList {
    private DoublyListNode head;

    public void deleteNode(int value) {
        DoublyListNode current = head;

        while (current != null) {
            if (current.val == value) {
                if (current.prev != null) {
                    current.prev.next = current.next;
                } else {
                    // 删除头节点
                    head = current.next;
                }

                if (current.next != null) {
                    current.next.prev = current.prev;
                }
                return;
            }

            current = current.next;
        }
    }
}

上述示例中，我们定义了一个 DoublyLinkedList 类，包含一个 deleteNode 方法，删除双向链表中指定值的节点。与单向链表不同的是，我们需要同时更新当前节点的前一个节点和后一个节点的引用。