LinkedList.FindNext and FindPrevious
The generic collections in the .NET framework do a good job of hiding algorithmic details and instead let you focus on the purpose of a class instead of how it’s implemented. For example, instead of using a Hashtable you use a Dictionary. And instead of using an Array you use a List. A Dictionary might use a Hashtable underneath, and a List might use an Array, but you don’t have to concern yourself or even know about the internal data structures.
But there’s a class in the System.Collections.Generic namespace that’s an exception to this rule, and it’s the LinkedList (with its partner in crime, the LinkedListNode). I don’t use it very often, but I was implementing an algorithm the other day and it required rapid removal and insertion into an ordered list while traversing that list. I probably could have mangled something together with SortedDictionary, but my list items didn’t really have “keys and values”, and I’d be forced to use its Enumerator to traverse the list but that would prevent me from modifying the list as I traversed it. Fortunately, LinkedList was perfect for the job!
One of the main portions of my algorithm involves searching the list for the next instance of a value. LinkedList contains a handy Find method, but it always starts at the head of the list. So if the sought value shows up more than once in the list, or if you simply want to start the search from somewhere within the list, you have to write a loop and do it yourself. The Find method was so close to satisfying this need, if only it let you specify where to start searching instead of always searching from the beginning. So I wrote an extension method called FindNext that does just that:
public static LinkedListNode<T> FindNext<T>(this LinkedList<T> list, LinkedListNode<T> node, T value)
{
EqualityComparer<T> comparer = EqualityComparer<T>.Default;
// Skip the given node.
node = node.Next;
while (node != null)
{
if (value != null)
{
if (comparer.Equals(node.Value, value))
{
return node;
}
}
else if (node.Value == null)
{
return node;
}
node = node.Next;
}
return null;
}
[Comments and argument checking omitted for brevity.]
The code is basically the exact same as LinkedList.Find, except that you can specify where to start the search. You actually specify the node preceding where to start the search, since the idea is that you can just keep calling this method multiple times with the last result found in order to find all of the duplicate values within the list.
LinkedList also contains FindLast, so I created the corresponding FindPrevious method to match. I also added the ability to pass null as the argument for node, which means that the search will start at the head of the list (just like the default Find). Without the ability to pass null, your calling code loop would have to special case the first call and decide whether to call Find or FindNext, which isn’t elegant at all.
The source code for LinkedListExtensions is attached. Enjoy!