0

Всем привет!

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

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

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

7
  • 1
    > Вначале я решил, что LinkedListNode<T> имеет такой же смысл, что и KeyValyePair или DictionaryEntry в словарях. Но понял, что ошибся почему вы вдруг это поняли? >мне показалось , будто LinkedList может хранить только объекты LinkedListNode. Но оказывается, что он может хранить любые объекты с чего вы взяли?
    – DreamChild
    12 мар 2015 в 13:40
  • Просто в словарях это структуры, хранящие ключ/значение, и чтобы я не добавлял в словарь, получается, что все пары к/з обязательно преобразуются в эти структуры. Но в LinkedList это не так, потому что я туда могу внедрять любые значения, например, int и они сохраняются там как int, а не что-то другое. И выходит, что при извлечении словаря по индексу мне выдается одна из указанных структур, которую можно разложить на К. или З. А при извлечении LinkedList я получаю тот тип, который я и добавил. 12 мар 2015 в 13:47
  • Я так решил, потому что в типе int (например) нет никаких возможностей сделать ссылку на след/пред элемент, это можно сделать только в LinkedListNode 12 мар 2015 в 13:48
  • 1
    >Но в LinkedList это не так, потому что я туда могу внедрять любые значения, например int и они сохраняются там как int а не что-то другое кто вам сказал о том, как именно они там сохраняются? >Я так решил, потому что в типе int (например) нет никаких возможностей сделать ссылку на след/пред элемент, это можно сделать только в LinkedListNode эммм..и что же? Это как раз говорит о том, что LinkedList хранит именно эллементы типа LinkedListNode, а не что-то другое
    – DreamChild
    12 мар 2015 в 13:52
  • 1
    >Мне это подсказал компилятор. Потому что когда я в коде добавил 5 чисел типа int, потом написал такой вот код foreach(LinkedListNode<int> lln in LL) компилятор выдал, что нельзя привести тип int к LinkedListNode<int> ок, в таком случае, c чего вы взяли, что класс, реализующий IEnumerable<T> при каждой итерации foreach обязательно отдает именно "то, что хранит"? Иными словами, кто вам сказал, что если LinkedList<int> не может одновременно хранить LinkedListNode<int> и при этом итерировать по int внутри foreach?
    – DreamChild
    12 мар 2015 в 14:03

2 ответа 2

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)

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

1
  • О, спасибо нереальное!! Так гораздо понятнее, чем... Шилдт! Он в тех. подробности не вдается, а у меня от этого пар из головы. Спасибо 12 мар 2015 в 14:30
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;
     }
}

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.