• C

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
prasad2315Asked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

evilrixSenior Software Engineer (Avast)Commented:
From the start of the list you'll have to traverse it until you find the node you are looking for.
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
ozoCommented:
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
0
Infinity08Commented:
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.
0
Webinar: Miercom Evaluates Wi-Fi Security

It's not just about Wi-Fi connectivity anymore. A wireless security breach can cost your business large amounts of time, trouble, and expense. Plus, hear first-hand from Miercom how WatchGuard's Wi-Fi security stacks up against the competition in our upcoming webinar!

prasad2315Author Commented:
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
0
evilrixSenior Software Engineer (Avast)Commented:
Traversal of a linked list, by it's very nature, is sequential unless you have indexed it in some way. So, the answer is you'd have to implement some indexing system.
0
Infinity08Commented:
>> So, the answer is you'd have to implement some indexing system.

Or use a different data structure, like a BST (binary search tree).
0
prasad2315Author Commented:
what type of indexing  sytem we can implement
0
evilrixSenior Software Engineer (Avast)Commented:
>> 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.
0
evilrixSenior Software Engineer (Avast)Commented:
0
evilrixSenior Software Engineer (Avast)Commented:
0
prasad2315Author Commented:
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
0
evilrixSenior Software Engineer (Avast)Commented:
>> 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
0
Infinity08Commented:
>> 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.
0
evilrixSenior Software Engineer (Avast)Commented:
This article discussing indexing linked lists using arrays.
http://www.awitness.org/delphi_pascal_tutorial/source3/array_indexed_linked_list.html

I have not read it in detail so I am not sure how appropriate it is.
0
Infinity08Commented:
>> 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 ?
0
evilrixSenior Software Engineer (Avast)Commented:
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.
0
evilrixSenior Software Engineer (Avast)Commented:
>> 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
0
Infinity08Commented:
It wasn't directed at you, evilrix ;) It was directed at prasad2315 in reply to him insisting on using a linked list.
0
Infinity08Commented:
Ah I see that I quoted you, and that caused the (understandable) confusion ... Sorry ;)
0
evilrixSenior Software Engineer (Avast)Commented:
>> It wasn't directed at you, evilrix ;)
Roger that cap'n.
0
ozoCommented:
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.
0
Infinity08Commented:
>> 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 ?
0
evilrixSenior Software Engineer (Avast)Commented:
I wonder if this provides a possible way forward?
http://en.wikipedia.org/wiki/Unrolled_linked_list
0
Infinity08Commented:
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 ?
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
C

From novice to tech pro — start learning today.