刪除演算法原理

❶ 順序表、單鏈表的刪除演算法

單鏈表的刪除操作是指刪除第i個結點，返回被刪除結點的值。刪除操作也需要從頭引用開始遍歷單鏈表，直到找到第i個位置的結點。如果i為1，則要刪除第一個結點，則需要把該結點的直接後繼結點的地址賦給頭引用。對於其它結點，由於要刪除結點，所以在遍歷過程中需要保存被遍歷到的結點的直接前驅，找到第i個結點後，把該結點的直接後繼作為該結點的直接前驅的直接後繼。刪除操作如圖

單鏈表的刪除操作示意圖

刪除操作的演算法實現如下：
public T Delete(int i)
{
if (IsEmpty()|| i < 0)
{
Console.WriteLine("Link is empty or Position is error!");
return default(T);
}
Node q = new Node();
if (i == 1)
{
q = head;
head = head.Next;
return q.Data;
}
Node p = head;
int j = 1;
while (p.Next != null&& j < i)
{
++j;
q = p;
p = p.Next;
}
if (j == i)
{
q.Next = p.Next;
return p.Data;
}
else
{
Console.WriteLine("The ith node is not exist!");
return default(T);
}
}
演算法的時間復雜度分析：單鏈表上的刪除操作與插入操作一樣，時間主要消耗在結點的遍歷上。如果表為空則不進行遍歷。當表非空時，刪除第i個位置的結點， i等於1遍歷的結點數最少（1個），i等於n遍歷的結點數最多（n個，n為單鏈表的長度），平均遍歷的結點數為n/2。所以，刪除操作的時間復雜度為O（n）。