連結串列刪除
Harshit Jindal
2023年1月30日
2021年3月21日
在本文中,我們將學習如何從連結串列中刪除節點。
連結串列刪除演算法
令 head
為指向連結串列第一個節點的指標,令 temp
為要從連結串列中刪除的節點的值。
迭代演算法
-
初始化指標
curr
指向head
以遍歷連結列表,而將prev
設定為NULL
以在刪除時跟蹤temp
之前的節點。 -
如果要刪除的節點是
head
即temp
!=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
的節點。
-
用值
1
和prev
將指向head
節點的指標curr
初始化為NULL
。 -
反覆移動
curr
,直到到達值為3
和prev
為2
的節點。 -
將
prev
(即2
)指向curr->next
(即4
)。 -
刪除值為
3
的curr
節點。
連結列表刪除實施
#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)
。
Author: Harshit Jindal
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