链表删除

Harshit Jindal 2023年1月30日 2021年3月21日
  1. 链表删除算法
  2. 链接列表删除图解
  3. 链接列表删除实施
  4. 链表删除算法的复杂性
链表删除

在本文中,我们将学习如何从链表中删除节点。

链表删除算法

head 为指向链表第一个节点的指针,令 temp 为要从链表中删除的节点的值。

迭代算法

递归算法

链接列表删除图解

假设我们具有以下链接列表 1 -> 2 -> 3 -> 4,并且我们想删除值为 3 的节点。

链接列表删除插图

链接列表删除实施

C
++ cCopy#include <bits/stdc++.h>
using namespace std;

class Node {
    public:
        int data;
        Node* next;
        Node(int x) {
            this->data = x;
            this->next = NULL;
        }
};

void deleteNode(Node*& head, int val)
{

    if (head == NULL) {
        cout << "Element not present in the list\n";
        return;
    }
    if (head->data == val) {
        Node* t = head;
        head = head->next;
        delete (t);
        return;
    }
    deleteNode(head->next, val);
}

void deleteiter(Node** head, int x)
{

    Node* temp = *head;
    Node* prev = NULL;
    if (temp != NULL && temp->data == x)
    {
        *head = temp->next;
        delete temp;
        return;
    }
    else
    {
        while (temp != NULL && temp->data != x)
        {
            prev = temp;
            temp = temp->next;
        }

        if (temp == NULL)
            return;
        prev->next = temp->next;

        delete temp;
    }
}
void printList(Node* head)
{
    Node*curr = head;
    while (curr != NULL) {
        cout << curr->data << " ";
        curr = curr->next;
    }
    cout << "\n";
}
int main()
{
    Node* head = new Node(1);
    head -> next = new Node(2);
    head->next->next = new Node(3);
    head->next->next->next = new Node(4);
    head->next->next->next->next = new Node(5);
    printList(head);
    deleteNode(head, 3);
    printList(head);
    deleteiter(&head, 4);
    printList(head);
    return 0;
}

链表删除算法的复杂性

时间复杂度

  • 平均情况

要删除链接列表中第 i 个位置的节点,我们必须访问 i 个节点。因此,时间复杂度约为 O(i)。而且,链表中有 n 个节点,因此平均情况下的时间复杂度为 O(n/2)O(n)。时间复杂度约为 O(n)

  • 最佳情况

最好的情况是当我们要删除链接列表的开头时。最佳情况下的时间复杂度是 O(1)

  • 最坏情况

最坏情况下的时间复杂度是 O(n)。这与平均情况下的时间复杂度相同。

空间复杂度

在迭代实现的情况下,此算法的空间复杂度为 O(1),因为它除了临时变量外不需要任何数据结构。

在递归实现中,由于递归调用堆栈所需的空间,空间复杂度为 O(n)

Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn

相关文章 - Data Structure

相关文章 - Linked List