Удалить операцию в связанном списке C#

У меня возникла проблема с операцией C# remove в связанном списке. 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

Почему п ot use ['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 Ну, это не так. Этот класс предоставляет только геттеры для Previous и Next. – 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 - добро пожаловать :) –

Внутри метода Удалить из LinkedList (Т) зависит от:

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#

ответ

Смежные вопросы