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?

Solution 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).

Solution 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.

Solution 3

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

Solution 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.

View more solutions

Comments

[Smartboy]

it gives me the result , but can you please elaborate it

[Tim Schmelter]

Pointless with a circular linked list. @Smartboy: That's linq, Enumerable.Select and Enumerable.Where can incorporate the element's index.

[Groo]

I don't thing that's the problem in OP's case. IndexOf works the same way.

[Smartboy]

i am pointing your answer as correct because answer should always be easy to understand , even for nerds

[Groo]

@Smartboy: thanks, but LINQ is not that hard once you get used to it. I also prefer LINQ over manually iterating, it's more concise. This was just meant to show the algorithm.

[L.B]

@TimSchmelter I must be missing something. How do you create a circular linked list from LinkedList<int>?

[Groo]

@Smartboy: when you use a Select extension method, it uses LinkedLists implementation of IEnumerable to simply iterate through elements, one at a time. The Select method then projects each element into a new instance of an anonymous class with two properties (item value "item", and its index "inx"), and the First method then accepts an anonymous method specifying a search predicate (takes an int, returns a bool) and returns the first element which satisfies the condition. One slight problem with First is that it throws an exception when no item is matched.

[L.B]

@TimSchmelter It seems you create your own problems and comment on those. I think question is very clear.

[Tim Schmelter]

@L.B: Maybe, i was sure that LinkedList supports that by default already ;)