Очистить в LinkedList для O (N). Зачем? - PullRequest
Новая
       5

Очистить в LinkedList для O (N). Зачем?

0 голосов
/ 15 ноября 2018

Встроенная реализация LinkedList представляет собой дважды связанный круговой список.

Я вижу следующую реализацию метода Clear: 

public void Clear() {
        LinkedListNode<T> current = head;             
        while (current != null ) {
            LinkedListNode<T> temp = current;
            current = current.Next;
            temp.Invalidate();                
        }

        head = null;
        count = 0;             
        version++;     
    }

Итак, этот метод очистки, по-видимому,работает на O (N). 

public sealed class LinkedListNode<T> {
    internal LinkedList<T> list;
    internal LinkedListNode<T> next;
    internal LinkedListNode<T> prev;
    internal T item;

    public LinkedListNode( T value) {
        this.item = value;
    }

    internal LinkedListNode(LinkedList<T> list, T value) {
        this.list = list;
        this.item = value;
    }

    public LinkedList<T> List {
        get { return list;}
    }

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

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

    public T Value {
        get { return item;}
        set { item = value;}
    }

    internal void Invalidate() {
        list = null;
        next = null;
        prev = null;
    }           
}

Интересно, почему мы не можем просто присвоить null заголовку вместо обнуления всех ссылок?Насколько я вижу, присвоение нулю головы приведет к разрыву круга, и все узлы будут собраны GC довольно скоро.Или я что-то упустил?

1 Ответ

0 голосов
/ 15 ноября 2018

Это делается для того, чтобы после очистки связанного списка все, что содержит ссылки на его старые узлы, приводило к ошибкам при попытке навигации по списку.

Если бы старые ссылки не были установлены в нуль, старый связанный список оставался бы доступным, если бы что-либо имело ссылку на какой-либо из его узлов, что (а) скрыло бы проблему, потому что код продолжал бы работать и ( б) поддерживать в памяти объекты-узлы.

...