链表删除 (删除指定位置的键)

17 Mar 2025 | 6 分钟阅读

链表是计算机科学中必不可少的基础数据结构。在特定位置删除节点是链表上基本且常用的操作。在这篇文章中，我们将深入探讨链表删除的复杂性，研究其相关性、基本概念以及全面的 Python 实现。

链表是一种线性数据结构，由节点组成，每个节点包含一个数据元素以及一个指向序列中下一个节点的引用（或链接）。最后一个节点通常指向 None，表示列表的结束。与数组相比，这种动态结构具有高效在任意位置插入和删除等优点。

删除的重要性

链表删除对于维护数据结构的完整性和性能至关重要。在特定位置删除节点需要更改节点之间的链接以保持数据的逻辑流。由于链表可以动态删除节点，因此它们可以适应不断变化的需求，使其成为处理不断发展的数据集的有效工具。

在给定位置删除：分步方法

1. 删除头节点

首先要探索的可能性是删除链表的头节点。如果第一个节点要被删除，将头节点更改为指向下一个节点可以有效地将其从列表中删除。此过程的时间复杂度为 O(1)，因此效率非常高。

时间复杂度： O(1) - 常数时间，因为它只涉及简单的指针更新。

空间复杂度： O(1) - 常数空间，因为没有使用额外的数据结构。

实施

#include <stdio.h>
#include <stdlib.h>
struct Node {
    int data;
    struct Node* next;
};
void deleteHead(struct Node** head) {
    if (*head == NULL) {
        printf("List is empty. Deletion failed.\n");
        return;
    }
    struct Node* temp = *head;
    *head = (*head)->next;
    free(temp); 
    printf("Head deleted successfully.\n");
}
void displayList(struct Node* head) {
    struct Node* current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}
int main() {
    struct Node* head = NULL;
    for (int i = 5; i >= 1; i--) {
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        newNode->data = i;
        newNode->next = head;
        head = newNode;
    }
    printf("Original Linked List: ");
    displayList(head);
    deleteHead(&head);
    printf("Linked List after Head Deletion: ");
    displayList(head);
    return 0;
}

此实现包括

结构体 Node 提供了链表节点的结构，其中包括一个整数（数据）和对下一个节点（next）的引用。
deleteHead 方法接受一个指向链表头部的双指针。如果列表不为空，它会将头节点更改为指向下一个节点，并释放前一个头节点占用的内存。
displayList 函数遍历并打印链表的项目。
主函数出于演示目的将节点插入链表，并显示原始和更新后的链表。

输出

Linked List Deletion (Deleting a key at a given position)

2. 删除其他节点

对于头节点以外的节点，需要更详细的方法。该算法包括遍历列表直到到达目标位置，然后将后续节点的指针重定向以绕过要销毁的节点。

时间复杂度： O(n) - 线性时间，其中 n 是链表中的节点数。

空间复杂度： O(1) - 常数空间，因为算法使用固定量的额外内存。

实施

#include <stdio.h>
#include <stdlib.h>
struct Node {
    int data;
    struct Node* next;
};
void deleteAtPosition(struct Node** head, int position) {
    if (*head == NULL) {
        printf("List is empty. Deletion failed.\n");
        return;
    }
    struct Node* current = *head;
    struct Node* prev = NULL;
    int count = 0;
    while (current != NULL && count < position) {
        prev = current;
        current = current->next;
        count++;
    }
    if (current == NULL) {
        printf("Position %d not found in the list. Deletion failed.\n", position);
        return;
    }
    if (prev != NULL) {
        prev->next = current->next;
        free(current); 
        printf("Node at position %d deleted successfully.\n", position);
    } else {
        *head = current->next;
        free(current); 
        printf("Node at position %d (head) deleted successfully.\n", position);
    }
}
void displayList(struct Node* head) {
    struct Node* current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}
int main() {
    struct Node* head = NULL;
    for (int i = 5; i >= 1; i--) {
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        newNode->data = i;
        newNode->next = head;
        head = newNode;
    }
    printf("Original Linked List: ");
    displayList(head);
    int positionToDelete = 2;
    deleteAtPosition(&head, positionToDelete);
    printf("Linked List after Deleting Node at Position %d: ", positionToDelete);
    displayList(head);
    return 0;
}

此实现包括

deleteAtPosition 函数接受一个指向链表头部的双引用和要删除的位置。
它遍历列表直到到达所需位置，修改下一个节点的指针以跳过当前节点。
displayList 方法用于输出链表的项目。
节点出于演示目的被放置在主函数中的链表中，并在某个点删除一个节点。

输出

3. 处理边缘情况

在健壮的链表删除解决方案中必须考虑边缘情况。这些包括尝试从空列表中删除节点、尝试在不存在的位置删除节点以及处理超出列表末尾的删除。

时间复杂度： O(1) - 常数时间，因为它涉及基本的条件检查。

空间复杂度： O(1) - 常数空间，因为没有使用额外的内存。

实施

#include <stdio.h>
#include <stdlib.h>
struct Node {
    int data;
    struct Node* next;
};
void deleteAtPosition(struct Node** head, int position) {
    if (*head == NULL) {
        printf("List is empty. Deletion failed.\n");
        return;
    }
    struct Node* current = *head;
    struct Node* prev = NULL;
    int count = 0;
    while (current != NULL && count < position) {
        prev = current;
        current = current->next;
        count++;
    }
    if (current == NULL) {
        printf("Position %d not found in the list. Deletion failed.\n", position);
        return;
    }
    if (prev != NULL) {
        prev->next = current->next;
        free(current); 
        printf("Node at position %d deleted successfully.\n", position);
    } else {
        *head = current->next;
        free(current); 
        printf("Node at position %d (head) deleted successfully.\n", position);
    }
}
void displayList(struct Node* head) {
    struct Node* current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}
int main() {
    struct Node* head = NULL;
    printf("Original Linked List: ");
    displayList(head);
    deleteAtPosition(&head, 2);
    for (int i = 5; i >= 1; i--) {
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        newNode->data = i;
        newNode->next = head;
        head = newNode;
    }
    printf("Updated Linked List: ");
    displayList(head);
    deleteAtPosition(&head, 10);
    deleteAtPosition(&head, 5);
    printf("Final Linked List: ");
    displayList(head);
    return 0;
}

在此改进版本中

程序首先尝试从空列表中删除节点，然后插入节点作为演示。
它演示了尝试在无效位置删除节点以及处理超出列表末尾的删除。
每种情况都会显示适当的消息，指示删除是否成功。

输出

结论

最后，在特定位置删除链表是数据结构世界中的一个关键操作。理解此过程背后的思想，例如指针更新和处理异常情况，对于任何程序员或计算机科学爱好者来说都至关重要。链表是一种多功能且强大的工具，因为它们能够通过高效删除动态管理数据。通过研究链表删除的复杂性，我们深入了解了这些动态结构的底层工作原理，为更高级的数据操作任务打开了大门。掌握链表删除是您在计算机科学世界中旅程的重要一步，无论您是初学者还是经验丰富的开发人员。

下一个主题掌握竞争性编程中的括号问题

链表删除 (删除指定位置的键)

删除的重要性

在给定位置删除：分步方法

1. 删除头节点

2. 删除其他节点

3. 处理边缘情况

结论

联系信息

关注我们

教程

面试题

在线编译器

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 选择题

其他

链表删除 (删除指定位置的键)

删除的重要性

在给定位置删除：分步方法

1. 删除头节点

2. 删除其他节点

3. 处理边缘情况

结论

相关帖子

二叉树的直径

Boggle (在一组字符面板上查找所有可能的单词)

数据结构中的反转对问题

多数元素

单向链表的归并排序

最大尺寸矩形

伸展树

矩阵中最优单元以收集最多金币

DS 中的表达式树

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

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器