連結串列刪除

Harshit Jindal 2023年1月30日 2021年3月21日
  1. 連結串列刪除演算法
  2. 連結列表刪除圖解
  3. 連結列表刪除實施
  4. 連結串列刪除演算法的複雜性
連結串列刪除

在本文中,我們將學習如何從連結串列中刪除節點。

連結串列刪除演算法

head 為指向連結串列第一個節點的指標,令 temp 為要從連結串列中刪除的節點的值。

迭代演算法

  • 初始化指標 curr 指向 head 以遍歷連結列表,而將 prev 設定為 NULL 以在刪除時跟蹤 temp 之前的節點。
  • 如果要刪除的節點是 headtemp!=NULL && curr->data==temp,則將 head 設定為 curr->next 並刪除 curr
  • 否則,請執行以下操作,直到我們到達要刪除的節點為止。
    • prev=temp
    • temp=temp->next
  • 如果 temp==NULL,返回;
  • prev->next 設定為 temp->next,並刪除 temp 節點。

遞迴演算法

  • 如果 head==NULL,則連結串列為空,沒有要刪除的元素。因此,返回;
  • 如果 head->data==temp,即我們找到了要刪除的節點
    • head 儲存在臨時節點 t 中。
    • head 設定為 head->next 以刪除該節點。
    • 刪除 t 並返回到較早的遞迴呼叫。
  • 如果以上條件均不滿足,則遞迴呼叫 head->next 上的 deleteNode() 以繼續尋找節點。

連結列表刪除圖解

假設我們具有以下連結列表 1 -> 2 -> 3 -> 4,並且我們想刪除值為 3 的節點。

  • 用值 1prev 將指向 head 節點的指標 curr 初始化為 NULL
  • 反覆移動 curr,直到到達值為 3prev2 的節點。
  • prev(即 2)指向 curr->next(即 4)。
  • 刪除值為 3curr 節點。

連結列表刪除插圖

連結列表刪除實施

#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