LinkedList и LinkedListNode

Question

LinkedList и LinkedListNode

Рейтинг: 0Ответов: 2Опубликовано: 12.03.2015

Всем привет!

Уважаемые знатоки, подскажите, пожалуйста, каким образом работает связный список в целом и конкретно какова роль LinkedListNode<T>?

Вначале я решил, что LinkedListNode<T> имеет такой же смысл, что и KeyValyePair или DictionaryEntry в словарях. Но понял, что ошибся. Теперь не могу понять, зачем он вообще нужен и что конкретно добавляется в коллекцию при вызове метода AddFirst(). Я так понимаю, что помимо данных (например int) добавляется еще и какая-то дополнительная информация о том, что и куда ссылается. И что это как-то связано с этим классом LinkedListNode<T>. Но вот как связано и что он делает, не пойму. Подскажите, кто в теме. Спасибо.

ПС Недоразумение еще связано с тем, что мне показалось, будто LinkedList может хранить только объекты LinkedListNode. Но оказывается, что он может хранить любые объекты, в таком случае как происходит ссылка на след. (пред.) элемент, если, например, храниться тип int?

c# коллекции

Источник: Stack Overflow на русском

Answer 1

▲ 2Принят

Вот довольно нехитрый пример того, как это может быть устроено

// класс-аналог LinkedListNode<T>
class Node<T>
{
    public Node(T data)
    {
        Data = data;
    }

    public T Data { get; set; }
}

// класс-аналог LinkedList<T>
class MyContainer<T> : IEnumerable<T>
{
    private List<Node<T>> data = new List<Node<T>>();

    public void Add(Node<T> item)
    {
        data.Add(item);
    }

    public IEnumerator<T> GetEnumerator()
    {
        return data.Select(x => x.Data).GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

Пример использования всего этого хзяйства:

var container = new MyContainer<string>();
container.Add(new Node<string>("first"));
container.Add(new Node<string>("second"));
container.Add(new Node<string>("third"));

foreach (string item in container)    
    Console.WriteLine(item);

выводится:

first
second
third

Как можно видеть, в MyContainer хранятся и добавляются в него экземпляры Node<T>, однако итерация идет по типу дженерика (в данном случае string). А вот если написать так:

foreach (Node<string> item in container)

то получим ошибку. Как видите, это вполне возможно

Answer 2

▲ 2

LinkedList<T> это связанный список. То есть элементы внутри него ссылаются друг на друга. Может представить эти элементы как тройку - [значение, ссылка на следующий элемент списка, ссылка на предыдущий элемент списка].

Сам LinkedList<T> внутри себя хранит только два LinkedListNode<T> - первый и последний из списка. Таким образом, чтобы получить, скажем, третий элемент списка:

list.First.Next.Next

Касательно итератора гуглите оператор yield return и yield break.

Если вкратце, то в LinkedList<int> что-то вроде этого:

public IEnumerable<int> GetEnumerator()
{
     var t = this.First;
     while(t != null)
     {
          yield return t.Value;
          t = t.Next;
     }
}

LinkedList и LinkedListNode

Ответы