刪除C＃鏈表中的操作

我有一個關於鏈接列表中的C＃刪除操作的問題。 LinkedListNode<T>是不可變的，但是Remove(LinkedListNode<T>)是恆定時間。爲什麼我遇到問題？這裏的原因是：刪除C＃鏈表中的操作

通常情況下，除去我會寫下面的代碼時（忘了空值）：

public void Remove(LinkedListNode<T> node) 
{ 
    node.Previous.Next = node.Next; 
    node.Next.Previous = node.Previous; 
}

但由於LinkedListNode<T>是不可改變的，這是不是一種選擇。那麼O（1）時間又是如何完成的呢？

來源

2016-10-10 sm21

爲什麼ñ使用['LinkedList .Remove（）']（https://msdn.microsoft.com/en-us/library/cwsxykxy（v = vs.110）.aspx）？我假設你指的'LinkedListNode '是[這一個]（https://msdn.microsoft.com/en-us/library/ahf4c754（v = vs.110）.aspx）？ –

@RafaelCardoso嗯，它不。此類僅爲「上一個」和「下一個」提供獲取者。 – sm21

@EdPlunkett我沒有使用問題。我知道我可以。我的問題與我寫的不同 - 它是如何在O（1）時間內工作的？ – sm21

它並不是一成不變的，但這些屬性是read-only屬性：

//Out of LinkListNode<T>: 

public LinkedListNode<T> Next { 
    get { return next == null || next == list.head? null: next;} //No setters 
} 

public LinkedListNode<T> Previous { 
    get { return prev == null || this == list.head? null: prev;} //No setters 
}

這就是爲什麼你不能爲它們分配。而是實現它自己使用LinkedList<T>.Remove()方法：

LinkedList<int> list = new LinkedList<int>(new int[] { 1, 2, 3, 4 }); 
list.Remove(3); 

// list: 1,2,4

如果你看看Reference Source下，你會看到執行情況：」

public bool Remove(T value) { 
    LinkedListNode<T> node = Find(value); 
    if (node != null) { 
     InternalRemoveNode(node);  // <============== 
     return true; 
    } 
    return false; 
} 

public void Remove(LinkedListNode<T> node) { 
    ValidateNode(node);   
    InternalRemoveNode(node);   // <============== 
} 

internal void InternalRemoveNode(LinkedListNode<T> node) { 
    Debug.Assert(node.list == this, "Deleting the node from another list!"); 
    Debug.Assert(head != null, "This method shouldn't be called on empty list!"); 
    if (node.next == node) { 
     Debug.Assert(count == 1 && head == node, "this should only be true for a list with only one node"); 
     head = null; 
    } 
    else { 
    /******************** Relevant part here *****************/ 
     node.next.prev = node.prev; 
     node.prev.next = node.next; 
     if (head == node) { 
      head = node.next; 
     } 
    } 
    node.Invalidate(); 
    count--; 
    version++;   
}

所以基本上他們實現它，你想太多，但他們可以使用不同的變量，是internal和不read-only：

internal LinkedListNode<T> next; 
internal LinkedListNode<T> prev;

來源

2016-10-10 19:39:36

@ sm21 - 查看我的最新更新 - 我添加了.Net使用的代碼 –

這就是我正在尋找的答案。謝謝！ – sm21

@ sm21 - 歡迎您:) –

內部，鏈表（T）的方法Remove依賴於：

internal void InternalRemoveNode(LinkedListNode<T> node)

其本身又直接操縱一個LinkedListNode（T）的相應後備字段，既與internal visibility也宣稱：

internal LinkedListNode<T> prev;

和

internal LinkedListNode<T> next;

「希望這有助於

來源

2016-10-10 19:47:28 YSharp

刪除C＃鏈表中的操作

回答

相關問題