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

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 2

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

public static IEnumerable<T> Backwards<T>(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())
{
    // ...
}