Есть ли в c # /. Net x.x реализация двусвязного списка (который можно перебирать в обратном направлении)? - PullRequest
Новая
       50

Есть ли в c # /. Net x.x реализация двусвязного списка (который можно перебирать в обратном направлении)?

6 голосов
/ 26 января 2010

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

Если он существует, для какой версии c # /. Net он существует?

Обратная итерация в целом, похоже, не предназначена для выполнения в c #. Неужели мой разум слишком сильно застрял в режиме c ++ / stl или этого чего-то крайне не хватает в c #?

Я знаю о LinkedList, но, не найдя способа перебрать его в обратном направлении, я предположил, что он был связан по отдельности.

Если LinkedList связан дважды, как можно перебирать его обратно (эффективно)?

Ответы [ 4 ]

10 голосов
/ 26 января 2010

Следующий код будет эффективно перебирать LinkedList в обратном порядке: 

        LinkedList<string> list = new LinkedList<string>
            (new[] {"cat", "dog", "frog", "antelope", "gazelle"});
        LinkedListNode<string> item = list.Last;
        do
        {
            Console.WriteLine(item.Value);
            item = item.Previous;
        }
        while (item != null);
        Console.ReadKey();

Ключевым моментом здесь является то, что LinkedList содержит ссылку только на первый и последний экземпляры LinkedListNode списка. Каждый экземпляр LinkedListNode содержит ссылку на следующий и предыдущий элемент в списке (или ноль на каждом конце списка), а также свойство Value. Это означает, что итерация первого или последнего LinkedListNode проста, но произвольный доступ требует итерации первого или последнего в списке.

Если вам нужно сделать вставку по пути, используйте LinkedList.AddBefore или AddAfter, чтобы вставить новый LinkedListNode.

6 голосов
/ 26 января 2010

Помимо ответов, приведенных здесь, вы можете написать метод расширения для LinkedList<T>, чтобы сделать его немного проще для повторного использования: 

public static IEnumerable<T> Backwards(this LinkedList<T> list)
{
    LinkedListNode<T> node= list.Last;
    while (node != null)
    {
        yield return node.Value;
        node = node.Previous;
    }
}

Используйте с: 

foreach (string x in list.Backwards())
{
    // ...
}
2 голосов
/ 26 января 2010

Как насчет System.Collections.Generic.LinkedList ()

Вот документы на MSDN:

http://msdn.microsoft.com/en-us/library/he2s3bh7.aspx

Информация о версии
.NET Framework: Поддерживается в версиях: 3.5, 3.0, 2.0
.NET Compact Framework: поддерживается в версиях: 3.5, 2.0
Платформа XNA: поддерживается в версиях: 3.0, 2.0, 1.0

Тем не менее, я с другими, как правило, предпочтительнее использовать более высокую абстракцию при работе с таким богатым фреймворком.

1 голос
/ 26 января 2010

Как насчет LinkedList ?

...