programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# what is the most effiecient algorithm, concerning time complexity, for searching in a linked list ?

Dan D'amico
Ranch Hand
Posts: 94
with arrays its binary search which finds a value in O(Logn) time
but what about linked lists ? the most effiecient algorithm will be O(n) ?

and i know that binary search cannot be implement on a linked list , therefore , the only way to search a linked list is a linear search ?

Stevens Miller
Bartender
Posts: 1445
30
• 2
It's been a long time since I took the courses that cover data structures and orders of computation, Dan, but I'll stick my neck out and say that, for a simple, singly-linked list, you are correct: searching is O(n). You only have one point of entry into a list, and that's the head. The only thing the head can tell you (in addition to whatever is stored at the head's node) is how to find the next node in the list. That next node is, effectively, the head of the rest of the list. As such, it can only tell you how to find the next node after that, and so on.

Now, during your pass through the list, you can be retaining other info that partitions the list into sections, which might make it easier to find nodes in the future, depending on how the list is ordered, maybe. But, in doing so, you are creating a new data structure that is no longer a simple, singly-linked list.

By the way, searching for an entry in an array is not necessarily O(log n). Binary search relies on the array being sorted by some comparison rule. If the array is not sorted, you're back to O(n), since you have to look at every entry, one by one, until you find the one you are looking for.

Dan D'amico
Ranch Hand
Posts: 94
Stevens Miller wrote:It's been a long time since I took the courses that cover data structures and orders of computation, Dan, but I'll stick my neck out and say that, for a simple, singly-linked list, you are correct: searching is O(n). You only have one point of entry into a list, and that's the head. The only thing the head can tell you (in addition to whatever is stored at the head's node) is how to find the next node in the list. That next node is, effectively, the head of the rest of the list. As such, it can only tell you how to find the next node after that, and so on.

Now, during your pass through the list, you can be retaining other info that partitions the list into sections, which might make it easier to find nodes in the future, depending on how the list is ordered, maybe. But, in doing so, you are creating a new data structure that is no longer a simple, singly-linked list.

By the way, searching for an entry in an array is not necessarily O(log n). Binary search relies on the array being sorted by some comparison rule. If the array is not sorted, you're back to O(n), since you have to look at every entry, one by one, until you find the one you are looking for.

thanks a lot !.
yes if the array is not sorted the search must be O(n), although if I do multiple searches, it will be better to first sort it , and then do binary search, depends on the sorting method ofcourse.

Stevens Miller
Bartender
Posts: 1445
30
If you are looking into these questions for academic/scholarly purposes, then you seem to be on the right track. As a practical matter, Java offers all sorts of classes that do a lot to help the speedy search/traversal/modification of structured sets of data. I'm partial to the ArrayList class for a lot of what I do, but that's hardly the only one worth knowing about.

If you say a little more about what you're interested in, someone can probably give you more guidance.

Campbell Ritchie
Marshal
Posts: 56600
172
• 1
Dan D'amico wrote:with arrays its binary search which finds a value in O(Logn) time . . .
I think there is some confusion here.

A binary search runs in logarithmic time and it can be applied to arrays, array lists and linked lists. But (big but), binary search is only ever reliable if the field of search is sorted. Yes, you can use binary search for arrays and any kind of list, but you would have to sort it first.

Dan D'amico
Ranch Hand
Posts: 94
Stevens Miller wrote:If you are looking into these questions for academic/scholarly purposes, then you seem to be on the right track. As a practical matter, Java offers all sorts of classes that do a lot to help the speedy search/traversal/modification of structured sets of data. I'm partial to the ArrayList class for a lot of what I do, but that's hardly the only one worth knowing about.

If you say a little more about what you're interested in, someone can probably give you more guidance.

actually thats all i wanted to ask. so tanks.