删除链表中的节点

2025年3月17日 | 阅读 12 分钟

引言

链表是计算机科学中的基本数据结构，对于动态内存分配以及强大的插入和删除功能非常重要。从链表中删除节点可能看起来很简单，但需要重要的技术和考虑因素来确保正确的功能和可伸缩性。本指南全面概述了链表删除，涵盖了不同的场景和链表类型，并提供了远程代码和代码示例。

删除链表的基本信息

在单向链表中，每个节点指向另一个节点。删除节点需要更新前一个节点的指针以反映后续节点的指针，除了被删除的节点。这有效地从链表中删除了该节点。

删除头节点：如果目标节点是头节点（第一个节点），则必须在第二个节点上更新主指示器，从而删除原始主节点。

删除中间节点：从中间删除节点需要将前一个节点的指针显示在新删除节点之后的节点上，从而跳过删除节点。

删除尾节点：要删除尾节点（最后一个节点），必须将倒数第二个节点的指针更新为新删除节点，从而删除原始尾节点。

链表删除的伪代码

function deleteNode(list, target):
    if list is empty:
        return

    if list.head.value == target:
        list.head = list.head.next
        return

    current = list.head
    while current.next is not null:
        if current.next.value == target:
            current.next = current.next.next
            return
        current = current.next

使用各种链表类型进行删除

单向链表：删除涉及调整前一个节点的指针以绕过目标节点。时间复杂度：O(n)。

双向链表：删除需要更新前一个节点和后一个节点的指针。时间复杂度：O(n)。允许双向遍历以高效定位节点。

循环链表：删除类似于单向链表，但需要特别考虑头节点和尾节点。

需要记住的要点

空指针检查：在尝试任何删除操作之前，务必检查空指针，以避免运行时错误。

内存管理：记住释放被删除节点占用的内存，以防止内存泄漏。

特殊情况处理：特别注意边界情况，例如删除头节点或尾节点，以维护链表的完整性。

更新引用：删除节点后，正确更新周围节点的引用或指针，以保持链表的连通性。

复杂性分析：请记住，链表中的删除操作通常具有 O(n) 的时间复杂度，其中 n 是链表中的节点数。

在单向链表中删除节点的示例

从头节点开始遍历链表，同时跟踪当前位置。
当您到达所需位置（位置 - 1）时，更新前一个节点的指针，使其指向要删除的节点之后的节点。
摆脱要删除的节点以释放内存。

Python 代码

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    # Add a new node to the end of the linked list
    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node

    # Display the linked list
    def display(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

    # Delete a node at a given position
    def delete_node_at_position(self, position):
        if not self.head:
            print("List is empty. Nothing to delete.")
            return

        if position == 0:
            self.head = self.head.next
            return

        current = self.head
        prev = None
        current_position = 0

        while current is not None and current_position < position:
            prev = current
            current = current.next
            current_position += 1

        if current is None:
            print("Position is out of bounds.")
            return

        prev.next = current.next

# Example usage
linked_list = LinkedList()
linked_list.append(5)
linked_list.append(6)
linked_list.append(7)
linked_list.append(8)

print("Original linked list:")
linked_list.display()

position = 2
linked_list.delete_node_at_position(position)
print(f"Linked list after deleting node at position {position}:")
linked_list.display()

输出

Java 代码

class Node {
    int data;
    Node next;

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

class LinkedList {
    Node head;

    // Add a new node to the end of the linked list
    void append(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
    }

    // Display the linked list
    void display() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }

    // Delete a node at a given position
    void deleteNodeAtPosition(int position) {
        if (head == null) {
            System.out.println("List is empty. Nothing to delete.");
            return;
        }

        if (position == 0) {
            head = head.next;
            return;
        }

        Node current = head;
        Node prev = null;
        int currentPosition = 0;

        while (current != null && currentPosition < position) {
            prev = current;
            current = current.next;
            currentPosition++;
        }

        if (current == null) {
            System.out.println("Position is out of bounds.");
            return;
        }

        prev.next = current.next;
    }
}

public class Main {
    public static void main(String[] args) {
        LinkedList linkedList = new LinkedList();
        linkedList.append(5);
        linkedList.append(6);
        linkedList.append(7);
        linkedList.append(8);

        System.out.println("Original linked list:");
        linkedList.display();

        int position = 2;
        linkedList.deleteNodeAtPosition(position);
        System.out.println("Linked list after deleting node at position " + position + ":");
        linkedList.display();
    }
}

输出

C++ 代码

#include <iostream>

class Node {
public:
    int data;
    Node* next;

    Node(int data) {
        this->data = data;
        this->next = nullptr;
    }
};

class LinkedList {
public:
    Node* head;

    LinkedList() {
        head = nullptr;
    }

    // Add a new node to the end of the linked list
    void append(int data) {
        Node* newNode = new Node(data);
        if (head == nullptr) {
            head = newNode;
            return;
        }
        Node* current = head;
        while (current->next != nullptr) {
            current = current->next;
        }
        current->next = newNode;
    }

    // Display the linked list
    void display() {
        Node* current = head;
        while (current != nullptr) {
            std::cout << current->data << " -> ";
            current = current->next;
        }
        std::cout << "nullptr" << std::endl;
    }

    // Delete a node at a given position
    void deleteNodeAtPosition(int position) {
        if (head == nullptr) {
            std::cout << "List is empty. Nothing to delete." << std::endl;
            return;
        }

        if (position == 0) {
            head = head->next;
            return;
        }

        Node* current = head;
        Node* prev = nullptr;
        int currentPosition = 0;

        while (current != nullptr && currentPosition < position) {
            prev = current;
            current = current->next;
            currentPosition++;
        }

        if (current == nullptr) {
            std::cout << "Position is out of bounds." << std::endl;
            return;
        }

        prev->next = current->next;
        delete current;
    }
};

int main() {
    LinkedList linkedList;
    linkedList.append(5);
    linkedList.append(6);
    linkedList.append(7);
    linkedList.append(8);

    std::cout << "Original linked list:" << std::endl;
    linkedList.display();

    int position = 2;
    linkedList.deleteNodeAtPosition(position);
    std::cout << "Linked list after deleting node at position " << position << ":" << std::endl;
    linkedList.display();

    return 0;
}

输出

在双向链表中删除开头的节点

在双向链表开头删除节点的伪代码

function deleteNodeAtBeginning(doublyLinkedList):
    if doublyLinkedList is empty:
        return

    if doublyLinkedList.head == null:
        return

    if doublyLinkedList.head == doublyLinkedList.tail:
        doublyLinkedList.head = null
        doublyLinkedList.tail = null
        return

    newHead = doublyLinkedList.head.next
    newHead.previous = null
    doublyLinkedList.head = newHead

如果列表为空，则无内容可删除。
如果列表只有一个节点，则将头指针和尾指针设置为 null。
否则，更新头指针以指向下一个节点。
将新头的上一个指针设置为 null，以切断与已删除节点的连接。

Java 代码

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.previous = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.previous = self.tail
            self.tail.next = new_node
            self.tail = new_node

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" <-> ")
            current = current.next
        print("None")

    def delete_node_at_beginning(self):
        if not self.head:
            print("List is empty. Nothing to delete.")
            return

        if self.head == self.tail:
            self.head = None
            self.tail = None
            return

        new_head = self.head.next
        new_head.previous = None
        self.head = new_head

# Example usage
doubly_linked_list = DoublyLinkedList()
doubly_linked_list.append(5)
doubly_linked_list.append(6)
doubly_linked_list.append(7)
doubly_linked_list.append(8)

print("Original doubly linked list:")
doubly_linked_list.display()

doubly_linked_list.delete_node_at_beginning()
print("Doubly linked list after deleting node at the beginning:")
doubly_linked_list.display()

输出

Java 代码

class Node {
    int data;
    Node next;
    Node previous;

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

class DoublyLinkedList {
    Node head;
    Node tail;

    // Add a new node to the end of the doubly linked list
    void append(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            tail = newNode;
        } else {
            newNode.previous = tail;
            tail.next = newNode;
            tail = newNode;
        }
    }

    // Display the doubly linked list
    void display() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " <-> ");
            current = current.next;
        }
        System.out.println("null");
    }

    // Delete a node at the beginning of the doubly linked list
    void deleteNodeAtBeginning() {
        if (head == null) {
            System.out.println("List is empty. Nothing to delete.");
            return;
        }

        if (head == tail) {
            head = null;
            tail = null;
            return;
        }

        Node newHead = head.next;
        newHead.previous = null;
        head = newHead;
    }
}

public class Main {
    public static void main(String[] args) {
        DoublyLinkedList doublyLinkedList = new DoublyLinkedList();
        doublyLinkedList.append(5);
        doublyLinkedList.append(6);
        doublyLinkedList.append(7);
        doublyLinkedList.append(8);

        System.out.println("Original doubly linked list:");
        doublyLinkedList.display();

        doublyLinkedList.deleteNodeAtBeginning();
        System.out.println("Doubly linked list after deleting node at the beginning:");
        doublyLinkedList.display();
    }
}

输出

C++ 代码

#include <iostream>

class Node {
public:
    int data;
    Node* next;
    Node* previous;

    Node(int data) {
        this->data = data;
        this->next = nullptr;
        this->previous = nullptr;
    }
};

class DoublyLinkedList {
public:
    Node* head;
    Node* tail;

    DoublyLinkedList() {
        head = nullptr;
        tail = nullptr;
    }

    // Add a new node to the end of the doubly linked list
    void append(int data) {
        Node* newNode = new Node(data);
        if (head == nullptr) {
            head = newNode;
            tail = newNode;
        } else {
            newNode->previous = tail;
            tail->next = newNode;
            tail = newNode;
        }
    }

    // Display the doubly linked list
    void display() {
        Node* current = head;
        while (current != nullptr) {
            std::cout << current->data << " <-> ";
            current = current->next;
        }
        std::cout << "null" << std::endl;
    }

    // Delete a node at the beginning of the doubly linked list
    void deleteNodeAtBeginning() {
        if (head == nullptr) {
            std::cout << "List is empty. Nothing to delete." << std::endl;
            return;
        }

        if (head == tail) {
            head = nullptr;
            tail = nullptr;
            return;
        }

        Node* newHead = head->next;
        newHead->previous = nullptr;
        head = newHead;
    }
};

int main() {
    DoublyLinkedList doublyLinkedList;
    doublyLinkedList.append(5);
    doublyLinkedList.append(6);
    doublyLinkedList.append(7);
    doublyLinkedList.append(8);

    std::cout << "Original doubly linked list:" << std::endl;
    doublyLinkedList.display();

    doublyLinkedList.deleteNodeAtBeginning();
    std::cout << "Doubly linked list after deleting node at the beginning:" << std::endl;
    doublyLinkedList.display();

    return 0;
}

输出

在双向链表中间删除节点

双向链表删除的伪代码

function deleteNodeAtMiddle(doublyLinkedList, targetNode):
    if doublyLinkedList is empty:
        return

    current = doublyLinkedList.head
    while current is not null:
        if current == targetNode:
            prev_node = current.previous
            next_node = current.next
            prev_node.next = next_node
            next_node.previous = prev_node
            return
        current = current.next

遍历列表以找到要删除的节点。
更新前一个节点的 next 指针以指向要删除的节点之后的节点。
更新下一个节点的 previous 指针以指向要删除的节点之前的节点。
摆脱要删除的节点以释放内存。

Python 代码

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.previous = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.previous = self.tail
            self.tail.next = new_node
            self.tail = new_node

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" <-> ")
            current = current.next
        print("None")

    def delete_node_at_middle(self, target_data):
        if not self.head:
            print("List is empty. Nothing to delete.")
            return

        current = self.head
        while current:
            if current.data == target_data:
                prev_node = current.previous
                next_node = current.next
                prev_node.next = next_node
                next_node.previous = prev_node
                return
            current = current.next

        print(f"Node with data {target_data} not found in the list.")

# Example usage
doubly_linked_list = DoublyLinkedList()
doubly_linked_list.append(5)
doubly_linked_list.append(6)
doubly_linked_list.append(7)
doubly_linked_list.append(8)

print("Original doubly linked list:")
doubly_linked_list.display()

target_data = 6
doubly_linked_list.delete_node_at_middle(target_data)
print(f"Doubly linked list after deleting node with data {target_data} from the middle:")
doubly_linked_list.display()

输出

Java 代码

class Node {
    int data;
    Node next;
    Node previous;

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

class DoublyLinkedList {
    Node head;
    Node tail;

    // Add a new node to the end of the doubly linked list
    void append(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            tail = newNode;
        } else {
            newNode.previous = tail;
            tail.next = newNode;
            tail = newNode;
        }
    }

    // Display the doubly linked list
    void display() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " <-> ");
            current = current.next;
        }
        System.out.println("null");
    }

    // Delete a node at the middle of the doubly linked list
    void deleteNodeAtMiddle(int targetData) {
        if (head == null) {
            System.out.println("List is empty. Nothing to delete.");
            return;
        }

        Node current = head;
        while (current != null) {
            if (current.data == targetData) {
                Node prevNode = current.previous;
                Node nextNode = current.next;

                if (prevNode != null) {
                    prevNode.next = nextNode;
                } else {
                    head = nextNode; // Update the head if the first node is the target
                }

                if (nextNode != null) {
                    nextNode.previous = prevNode;
                } else {
                    tail = prevNode; // Update the tail if the last node is the target
                }

                return;
            }
            current = current.next;
        }

        System.out.println("Node with data " + targetData + " not found in the list.");
    }
}

public class DoublyLinkedListMain {
    public static void main(String[] args) {
        DoublyLinkedList doublyLinkedList = new DoublyLinkedList();
        doublyLinkedList.append(5);
        doublyLinkedList.append(6);
        doublyLinkedList.append(7);
        doublyLinkedList.append(8);

        System.out.println("Original doubly linked list:");
        doublyLinkedList.display();

        int targetData = 6;
        doublyLinkedList.deleteNodeAtMiddle(targetData);
        System.out.println("Doubly linked list after deleting node with data " + targetData + " from the middle:");
        doublyLinkedList.display();
    }
}

输出

C++ 代码

// Online C++ compiler to run C++ program online
#include <iostream>

class Node {
public:
    int data;
    Node* next;
    Node* previous;

    Node(int data) {
        this->data = data;
        this->next = nullptr;
        this->previous = nullptr;
    }
};

class DoublyLinkedList {
public:
    Node* head;
    Node* tail;

    DoublyLinkedList() {
        head = nullptr;
        tail = nullptr;
    }

    // Add a new node to the end of the doubly linked list
    void append(int data) {
        Node* newNode = new Node(data);
        if (head == nullptr) {
            head = newNode;
            tail = newNode;
        } else {
            newNode->previous = tail;
            tail->next = newNode;
            tail = newNode;
        }
    }

    // Display the doubly linked list
    void display() {
        Node* current = head;
        while (current != nullptr) {
            std::cout << current->data << " <-> ";
            current = current->next;
        }
        std::cout << "null" << std::endl;
    }

    // Delete a node at the middle of the doubly linked list
    void deleteNodeAtMiddle(int targetData) {
        if (head == nullptr) {
            std::cout << "List is empty. Nothing to delete." << std::endl;
            return;
        }

        Node* current = head;
        while (current != nullptr) {
            if (current->data == targetData) {
                Node* prevNode = current->previous;
                Node* nextNode = current->next;

                if (prevNode != nullptr) {
                    prevNode->next = nextNode;
                } else {
                    head = nextNode; // Update the head if the first node is the target
                }

                if (nextNode != nullptr) {
                    nextNode->previous = prevNode;
                } else {
                    tail = prevNode; // Update the tail if the last node is the target
                }

                delete current; // Free the memory of the deleted node
                return;
            }
            current = current->next;
        }

        std::cout << "Node with data " << targetData << " not found in the list." << std::endl;
    }
};

int main() {
    DoublyLinkedList doublyLinkedList;
    doublyLinkedList.append(5);
    doublyLinkedList.append(6);
    doublyLinkedList.append(7);
    doublyLinkedList.append(8);

    std::cout << "Original doubly linked list:" << std::endl;
    doublyLinkedList.display();

    int targetData = 6;
    doublyLinkedList.deleteNodeAtMiddle(targetData);
    std::cout << "Doubly linked list after deleting node with data " << targetData << " from the middle:" << std::endl;
    doublyLinkedList.display();

    return 0;
}

输出

注意：虽然初始方法提供了健壮的解决方案，但重要的是要记住，根据应用程序的具体需求，可以采用其他优化策略。例如，当目标节点预计更靠近一端时，从列表两端搜索可以提高性能。

结论

提供的代码示例用于在链表中删除节点并检查复杂性方面。通过理解这些概念，您可以更好地管理链表删除并理解它们在不同场景和链表类型中的重要性。

下一个主题二叉树的直径

← 上一个下一个 →

删除链表中的节点

引言

删除链表的基本信息

链表删除的伪代码

使用各种链表类型进行删除

需要记住的要点

在单向链表中删除节点的示例

Python 代码

Java 代码

C++ 代码

在双向链表中删除开头的节点

Java 代码

Java 代码

C++ 代码

在双向链表中间删除节点

Python 代码

Java 代码

C++ 代码

注意：虽然初始方法提供了健壮的解决方案，但重要的是要记住，根据应用程序的具体需求，可以采用其他优化策略。例如，当目标节点预计更靠近一端时，从列表两端搜索可以提高性能。

结论

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

删除链表中的节点

引言

删除链表的基本信息

链表删除的伪代码

使用各种链表类型进行删除

需要记住的要点

在单向链表中删除节点的示例

Python 代码

Java 代码

C++ 代码

在双向链表中删除开头的节点

Java 代码

Java 代码

C++ 代码

在双向链表中间删除节点

Python 代码

Java 代码

C++ 代码

注意：虽然初始方法提供了健壮的解决方案，但重要的是要记住，根据应用程序的具体需求，可以采用其他优化策略。例如，当目标节点预计更靠近一端时，从列表两端搜索可以提高性能。

结论

相关帖子

数据结构中栈的表示

数据结构中的结构体

数据结构的应用

Hopcroft-Karp 算法用于最大匹配

内部排序和外部排序的区别

满二叉树

DSA 中的循环轮换数组一次问题

正整数数组中 k 个整数的最小乘积

如何检查给定数组是否代表堆

最小堆和最大堆的区别

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器