Link to home
Start Free TrialLog in
Avatar of prasad2315
prasad2315

asked on

search for an item in a single linked list in which numbers in random

how to find a number in a single linked list in which contains random numbers
assume that linked list contains 200 nodes
ASKER CERTIFIED SOLUTION
Avatar of evilrix
evilrix
Flag of United Kingdom of Great Britain and Northern Ireland image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
start at the head,
if the number is not in the current node, check the next node until you either find the number or get to the end of the list
It depends how your singly linked list is implemented, but usually, you'll have to iterate through the whole list from beginning to end until you find the item you want. You can sort the linked list too if you want.
Avatar of prasad2315
prasad2315

ASKER

traversing the linked list untill the item is found is good only when the number of nodes are less if the number of nodes are 2000 or more in that situation what i have to do to search the item faster
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
what type of indexing  sytem we can implement
>> what type of indexing  sytem we can implement
As I8 stated, it would be better to use a different, more appropriate structure such as a B-Tree.
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
i need to do with linked list only
if it is double linked list what is the implentation to search an item in the list faster
>> if it is double linked list what is the implentation to search an item in the list faster
The difference with a double linkly linked list is that you cna start from either end but since the data is in random order this provides no immediate benefit.

http://en.wikipedia.org/wiki/Linked_list
>> what type of indexing  sytem we can implement

It's not simple, and will be quite redundant. And you'll end up emulating tree-like behavior with a linked list. It's best to just use a tree structure ;)

A linked list is not made for searching fast. It's made to easily insert and remove elements in a sequential datatype, as well as have data orderings that don't depend on the location in memory of the data.

You could go for an ordered array instead. Then you can use binary search on it which is O(log n) instead of O(n) :

        http://en.wikipedia.org/wiki/Binary_search

But that's not possible with linked lists, since the elements in it are not indexed like in an array.
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
>> so I am not sure how appropriate it is.

It might be, but when you use indexing, you're no longer working with a normal linked list. As I said, you're emulating tree-like behavior with it - you're splitting up the linked list in several smaller linked lists that are accessed through an array. So, you'll have to lookup in the array which of the smaller linked lists you need, and then do a sequential search in that smaller linked list.

It also means that each time you insert/remove an item in the linked list, you also have to update the index.

Or in other words, you're invalidating several of the advantages of linked lists to obtain behavior that is standard in other data structures like trees. There's rarely a point to that.

What's the reason you need to use a linked list ?
You could possibly implement an additional linked list that indexes the first in blocks. So, for example, if you picked a granularity of 100 numbers, your index list would maintain an index into the start of where the 0-99 values live and then the next index item could index where the 100-199 values live and so on. The granularity of this would be up to you, the finer the granularity the quicker the index but the bigger it's become. The lower the granularity the slower but smaller it would be. You'd also have to implement an atomic mechanism for ensuring inserts and deletes from the main list updated the index. All in all it would be quite a bit of work and, ultimately, you'd be better off using a more suitable data structure.
>> As I said, you're emulating tree-like behavior
Hey, I'm agreeing with you not disagreeing. I provided the link as an example of what's involved and not as advocation! :-p
It wasn't directed at you, evilrix ;) It was directed at prasad2315 in reply to him insisting on using a linked list.
Ah I see that I quoted you, and that caused the (understandable) confusion ... Sorry ;)
>> It wasn't directed at you, evilrix ;)
Roger that cap'n.
If the numbers are in a random order, a tree doesn't help, you'd still need to search everything.
You could maintain a sorted index or a hashed index in another data structure.
A doublely linked list would make it easier to delete items that you found through the index without traversing the list.
>> If the numbers are in a random order

I interpreted the question to talk about "random numbers", not "numbers in random order". I might be mistaken though ... prasad2315 ?
I wonder if this provides a possible way forward?
http://en.wikipedia.org/wiki/Unrolled_linked_list
May I ask what the reason for the B grade is ? That usually means that something was missing in our answers. If so, I hope you know that you can always ask for clarification wherever needed ?