CODEWITHSUNDEEP
c#linked-list
Anders Gustafsson
Anders Gustafsson

Reputation: 15981

C#: Counting number of elements between nodes in LinkedList

I want to calculate the total number of nodes between a start node and and end node in a System.Collections.Generic.LinkedList, similar to the STL algorithm std::count in C++ (except that I intend to include the end node in the count).

I have not been able to figure out e.g. how to use any LINQ extension methods to efficiently calculate this number, so I have implemented a counter like this (excluding all null and consistency checks): 

var counter = 1;
var node = iStartNode;
while (!ReferenceEquals(node, iEndNode))
{
  node = node.Next;
  ++counter;
}

But there must be a more efficient solution, mustn't there? Any suggestions are highly appreciated.

Upvotes: 0

Views: 2058

Answers (2)

Jon Skeet
Jon Skeet

Reputation: 1500825

The only way I can think of which might be slightly cleaner - or at least, make general code working with linked list nodes slightly cleaner - would be to write two extension methods:

static IEnumerable<LinkedListNode<T>> AsEnumerable<T>
    (this LinkedListNode<T> node)
{
    // Can even call list.Head.AsEnumerable() when the list is empty!
    while (node != null)
    {
        yield return node;
        node = node.Next;
    }
}

static IEnumerable<LinkedListNode<T>> ReverseEnumerable<T>
    (this LinkedListNode<T> node)
{
    while (node != null)
    {
        yield return node;
        node = node.Previous;
    }
}

Then you could use LINQ:

var count = node.AsEnumerable().TakeWhile(x => x != endNode).Count();

That wouldn't include endNode itself, so you might want to increment it by 1. (It would be nice to have TakeUntil and SkipUntil methods which were like TakeWhile and SkipWhile, but included the first predicate-non-matching node as the final one to take or skip.)

Note that this wouldn't go bang if it failed to find endNode - it would just give the count of the list from the start node onwards.

The nice thing about the extension methods is they basically let you operate on the list as a sequence from any point.

Upvotes: 4

David Heffernan
David Heffernan

Reputation: 613003

I believe your solution to be the most efficient and also the most readable. Even if you can find an implementation in LINQ it will surely be tortuous.

By excluding null checks I presume you mean that the real code doesn't throw in the event of node running off the end of the list.

Upvotes: 6

Related Questions