Search method for singly linked list
 

Hi,

Is there any effective search method for a singly linked list?

linear search is too costly.

Linear search is all you've got, boy. If you want a more efficient search, use a different data structure.

couldn't you sort the linked list, then use a binary search

Thats what a binary tree is for, is it not?

I suppose you could sort it, though it would be painful. However, the reason a binary search won't work (at least not with the expected efficiency) is not because the list is unsorted. It's because the list is not random access. In order to access a given element, you need to iterate through all the preceding elements. A linked list is thus O(N) for accessing elements, and therefore, your search won't be more efficient.

Thanks for the update.

I have tried binary search, but is not efficient for a singly linked list.

You got a primo answer in response #1. Resonse #2 should never have been posted. You should be Googling for data structures and searching/sorting thereof by now....

>I have tried binary search, but is not efficient for a singly linked list.
Duh. Binary search relies on random access (or a suitable data structure) for its speed. Linked lists are notoriously bad at random access unless you want to go for broke and write something ridiculously complicated.

If a sorted linear search is too slow, you're not using the right data structure. Do some research on skip lists, and consider using a binary search tree or hash table.

Re: Search method for singly linked list
 

I will suggest you to use indexd search even for singly linked list! just create a array of structure for linked list. also for this you have to keep the linked list sorted. the code for that is also easy and this method is usefull if heavy searching is there and less insertions are to be done.insertion can be done in sorted manner!