How to search LinkedList<T> collection?

Question

I have a LinkedList<T> object where T is an arbitrary object which has a property named ID. I want search my collection using ID as search criteria.

Now I know I can search it using a while loop:

LinkedListNode<MyObject> element = myObject.First;
while (element != myObject.Last)
{
    if (element.Value.ID == myID)
    break;

    element = element.Next;
}

But I'm wondering if there is a more elegant solution. Note that I need LinkedListNode<T> as a result in order to navigate the list from there.

Solution 1

You can write an extension method to get you a sequence of the nodes and search that:

public static IEnumerable<LinkedListNode<T>> Nodes<T>(this LinkedList<T> list)
{
    for (var node = list.First; node != null; node = node.Next)
    {
        yield return node;
    }
}

then you can do

var matchingNode = list.Nodes().FirstOrDefault(n => n.Value.Id == myId);

Solution 2

Same idea as Lee, but simpler code:

    public static IEnumerable<LinkedListNode<T>> Nodes<T>(this LinkedList<T> list)
    {
        var node = list.First;
        while (node != null)
        {
            yield return node;
            node = node.Next;
        }
    }

EDIT

No need to use LINQ or extension methods. Simply use .Find() - it returns a LinkedListNode

var node = list.Find(5);

Note: For this to work your model with the id would need to override object.Equals to compare ID's (and therefore object.GetHashCode)

Solution 3

Will this give the result you expect?

Use @MartinLiversage answer and expand it to use the Find method which is part of the LinkedList<T>

int id = 1;
LinkedListNode<IHaveID> nodes = null;
LinkedList<IHaveID> testList = new LinkedList<IHaveID>();

var item = testList.FirstOrDefault(x => x.ID == id);
if(item != null)
{
    nodes = testList.Find(item);
}

Comments

[Sriram Sakthivel]

This doesn't looks readable. Earlier version was better after my edit. Any reason for this approach?

[Keith Payne]

How do you get IEnumerable<LinkedListNode<T>> from the LinkedList in order to invoke this method?

[Lee]

@KeithPayne - I don't understand your question - Nodes returns the IEnumerable<LinkedListNode<T>> from the linked list.

[Lee]

@SriramSakthivel - Sorry I was editing at the same time as you and didn't realise Last.Next can be null if the list is non-empty.

[Ben]

You don't need to check list.Count

[Nezreli]

It's correct but it iterates the list twice which is not optimal.

[Nezreli]

The Find(T) method expects a reference to MyObject which I don't have.

[Nezreli]

Thanks. It confirmed my suspicion that I can't do what I want without the loop. Is this a flaw of linked list collection? Should LINQ methods return IEnumerable<LinkedListNode<T>>??

[Lee]

@Nezreli - Yes, it would be nice if LinkedList<T> implemented IEnumerable<LinkedListNode<T>> as well. I don't know why it doesn't, possibly to remove confusion since it is mainly viewed as a collection of T, not a collection of nodes.

[yardpenalty.com]

How could I query a nested LinkedList using this helper? I will post my results if I get it working. Thanks in advance