comp_wizard07

Hi,

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

linear search is too costly.

lectricpharaoh

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

__________________
And once again, Probability proves itself willing to sneak into a back alley and service Drama as would a copper-piece harlot.
- Vaarsuvius, Order of the Stick

mark

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

Wizard1988

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

__________________
JG-Webdesign

lectricpharaoh

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.

__________________
And once again, Probability proves itself willing to sneak into a back alley and service Drama as would a copper-piece harlot.
- Vaarsuvius, Order of the Stick

comp_wizard07

Thanks for the update.

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

DaWei

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

__________________
Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code.
Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers

Narue

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

__________________
Even if the voices aren't real, they have some pretty good ideas.

rhish.franks

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!