c# - How do you get the index of a number in a linked list?

Question

I have a linked list constructed as follows:

LinkedList<int> linked = new LinkedList<int>();
var array = new int[] { 23, 55, 64, 65 };
foreach (var item in array)
{
    linked.AddLast(item);
}

How do I find the index of the number 64?

Answer 1

The only way is to check element by element and increase a counter (by "only way", I am saying that other methods like LINQ need to do the same thing internally).

A hand-written extension method would look something like this:

public static class LinkedListExt
{
    public static int IndexOf<T>(this LinkedList<T> list, T item)
    {
        var count = 0;
        for (var node = list.First; node != null; node = node.Next, count++)
        {
            if (item.Equals(node.Value))
                return count;
        }
        return -1;
    }
}

But it can easily be done using LINQ as @L.B wrote (yielding the same time complexity).

Answer 2

Here is an alternate LINQ implementation that avoids creating anonymous objects and returns -1 if the item is not in the list:

int index = linked.Select((n, i) => n == 64 ? (int?)i : null).
            FirstOrDefault(n => n != null) ?? -1;

It converts the sequence of numbers to a sequence containing the index of a match or null otherwise. It takes the first of these if there is one, otherwise converts the default int? to -1.

Edit:

Here is a better (simpler and more performant) alternative:

int i = linked.TakeWhile(n => n != 64).Count();

i will either be equal to the index, or equal to linked.Count if the value 64 was not found.

Answer 3

int index = linked.Select((item, inx) => new { item, inx })
                  .First(x=> x.item == 64).inx;

Answer 4

I think you should make your own function to parse the list and check. The "Find" function returns only the first occurrence and,for you, it is possible to have 2 or more occurrences of 64 in the list.

Answer 5

You can make one up. :) I found this question trying to figure out how to qsort a linked list. And it hit me since I'm sorting structs anyway all I have to do is give each one a unique identifier. Which will probably be the sequence in which they're created. Just add an int field called seq or idx to each node. Change your ints to structs with the ints inside and attach another int field that's your improvised index. Traversing the list will be cumbersome. But you bind the original ints to indexes.

If you don't expect the data to move around you could build an array of pointers to elements of your linked list. Start at the beginning, use the pointer to next, keep doing that and count how many hops. Then allocate your array, start at the beginning of the list again and record in your array the addresses of the next pointers. But someone or something (another thread?) could screw it up by moving or adding or removing an element. The list would continue to work but the array would need to be scrapped and redone. Could be relatively fast, but how to detect the change reliably?

Circular? Just use modulo so to move forward idx = (idx + 1) % N where N is the total count of fields. For normal C anyway, I don't know what C#'s limitations are.