How fast can we search a node in a linked list, instead of traversing the whole list

Linked lists require a sequential search. If you want something faster, use a hash table, or at least a binary tree.

Well, if you keep your list sorted, then you might not need to fully traverse it in every case, since you can stop the search as soon as you find the node you want.
I think that the list is O(n), and you always end up traversing it all the way eventually. Unless you compliment it with another type of auxiliar index (like Dan04 said, a Tree [any kind] or a hash table).


But at the bottom line, nothing beats a good hash table in terms of direct access

Cheers!

As the others have said there are alternative structures out there which are better at searching, but it really depends on what you want to do, if the list is small the time doesn't really matter much, if the list is large but searching for a specific node is rare then again the time to access it might not be too important.

You can build an extra index structure that at the cost of memory will significantly speed up access (I guess from O(n) to O(logn)), but that will increase the overhead, an insert update and a delete will also require the index to be modified.