Obtain node number n of a linked list

Question

If I have a linked list:

first node -----> second node ------> third node ---> ?

Can I show the third node value ( for example ) without use a classic list-linear-searching algorithm?

My attempt of getting the n'th node:

struct node* indexof( struct node* head, int i )
{
    int offset = (int)((char*)head->next - (char*)head);
    return ((struct node*)((char*)head + offset * i));
}

Answer 1

That depends on your exact linked list implementation, but in general, no. You will have to traverse the list in order to access the nth element.

This is a characteristic of linked lists, in the sense that the normal tricks you could use for computing an offset into an array or other sequence-like structure will not work, as your individual list elements are not guaranteed to be laid out in memory in any sensible way, so you are forced to follow the next pointers in-order to retrieve the third element.

You could consider other data structures that provide constant-time indexed access into your linked list.

Answer 2

Sounds like you've picked the wrong data structure. If you want to go straight to nth then you should use an array.

Failing that, what's so bad about going through in linear fashion? Would have to be called a lot on a very long linked list to be causing performance problem.