5

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?

Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
Smartboy
  • 986
  • 6
  • 22
  • 37

5 Answers5

12

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

Community
  • 1
  • 1
vgru
  • 49,838
  • 16
  • 120
  • 201
  • i am pointing your answer as correct because answer should always be easy to understand , even for nerds – Smartboy Nov 15 '12 at 08:28
  • @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. – vgru Nov 15 '12 at 08:31
4

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.

Matthew Strawbridge
  • 19,940
  • 10
  • 72
  • 93
2
int index = linked.Select((item, inx) => new { item, inx })
                  .First(x=> x.item == 64).inx;
L.B
  • 114,136
  • 19
  • 178
  • 224
  • it gives me the result , but can you please elaborate it – Smartboy Nov 15 '12 at 08:16
  • Pointless with a [circular linked list](http://en.wikipedia.org/wiki/Linked_list#Circular_list). @Smartboy: That's linq, [`Enumerable.Select`](http://msdn.microsoft.com/en-us/library/bb534869.aspx) and `Enumerable.Where` can incorporate the element's index. – Tim Schmelter Nov 15 '12 at 08:21
  • @TimSchmelter I must be missing something. How do you create a circular linked list from `LinkedList`? – L.B Nov 15 '12 at 08:33
  • @Smartboy: when you use a `Select` extension method, it uses `LinkedList`s 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. – vgru Nov 15 '12 at 08:36
  • @TimSchmelter It seems you create your own problems and comment on those. I think question is very clear. – L.B Nov 15 '12 at 09:10
  • @L.B: Maybe, i was sure that LinkedList supports that by default already ;) – Tim Schmelter Nov 15 '12 at 09:12
1

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.

Florin Petriuc
  • 1,146
  • 9
  • 16
  • 1
    I don't thing that's the problem in OP's case. [`IndexOf`](http://msdn.microsoft.com/en-us/library/8bd0tetb.aspx) works the same way. – vgru Nov 15 '12 at 08:25
0

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.

Alan Corey
  • 577
  • 6
  • 10