Dan D'amico

Ranch Hand

Posts: 94

posted 2 years ago

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

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.

"Il y a peu de choses qui me soient impossibles..."

Dan D'amico

Ranch Hand

Posts: 94

posted 2 years ago

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

posted 2 years ago

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.

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

"Il y a peu de choses qui me soient impossibles..."

Campbell Ritchie

Marshal

Posts: 56600

172

posted 2 years ago

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.

- 1

I think there is some confusion here.Dan D'amico wrote:with arrays its binary search which finds a value in O(Logn) time . . .

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

posted 2 years ago

actually thats all i wanted to ask. so tanks.

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.