删除c#链表中的操作

Question

我有一个关于c#删除链表操作的问题。LinkedListNode<T>是不可变的，但Remove(LinkedListNode<T>)是常数时间。为什么我对它有意见?原因如下:

通常，当删除时，我会写以下代码(忘记null):

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

但由于LinkedListNode<T>是不可变的，这不是一个选项。那么如何在O(1)时间内完成呢?

Answer 1

这不是不可变的，但这些属性是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

如果你查看参考源，你会看到实现如下:

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;

Answer 2

在内部，LinkedList(T)的Remove方法依赖于:

internal void InternalRemoveNode(LinkedListNode<T> node)

，它本身，反过来，直接操作相应的LinkedListNode(T)的后台字段，它们都是用内部可见性声明的:

internal LinkedListNode<T> prev;

和

internal LinkedListNode<T> next;