Does c#/.net x.x have an implementation of a doubly linked list (that can be iterated over backwards)?

Question

I've been searching for the standard implementation of a doubly linked list in c# (so that I have a linked list I can iterate over backwards) and cannot find one. I feel like something so simple must have an implementation that I'm just missing.

If it does exist, for which version of c#/.net does it exist?

Reverse iteration in general seems to be something not intended to be done in c#. Is my mind just stuck too much in c++/stl mode or is this something sorely lacking in c#?

I'm aware of LinkedList but in failing to find a way to iterate over it backwards had assumed it was singly linked.

If LinkedList is doubly linked how does one go about iterating over it backwards (Efficiently)?

Answer 1

Yes, it does. Check out the LinkedList class which is part of the System.Collections.Generic namespace. The documentation provides a decent sample to get you started.

EDIT: reversing with a LinkedList using the ElementAt extension method:

string[] words = { "the", "fox", "jumped", "over", "the", "dog" };

LinkedList<string> list = new LinkedList<string>(words);
for (int index = list.Count - 1; index >= 0; index--)
{
    Console.WriteLine(list.ElementAt(index));
}

As others have noted, this isn't the most efficient solution. The proper way is to use the data structure's intended properties. See spender's answer.

Answer 2

How about System.Collections.Generic.LinkedList()

Here are the docs on MSDN:

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

Version Info
.NET Framework: Supported in: 3.5, 3.0, 2.0
.NET Compact Framework: Supported in: 3.5, 2.0
XNA Framework: Supported in: 3.0, 2.0, 1.0

That said, I am with the others that it is generally preferrable to use a higher abstraction when working with such a rich framework.

Answer 3

How about LinkedList?

Answer 4

The following code will efficiently iterate over a LinkedList in reverse:

        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();

The key here is that a LinkedList contains reference to only the First and Last LinkedListNode instances of the list. Each LinkedListNode instance holds a reference to the next and previous item in the list (or null at each end of the list) and also a Value property. This means iteration from the first or last LinkedListNode is easy, but random access requires iteration from the first or last in the list.

If you need to make an insertion along the way, use LinkedList.AddBefore or AddAfter to insert a new LinkedListNode.

Answer 5

As well as the answers given here, you can write an extension method to LinkedList<T> to make this slightly easier to reuse:

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

Use with:

foreach (string x in list.Backwards())
{
    // ...
}