### Forum

hello friends!
I have one array of linked list that Sorted in ascending order.i want to my program get a number and search in array of linked list and answer to this question , Is that number in the list?
Last edited on
Please show some code. Minimal example of what you currently have.

Use code tags to format it properly.

With "array of linked list" you mean that you are using an array of std::list, or what?
Last edited on
Well the logic to search an ascending sorted linked list is something like this - depending upon how the list is defined:

 ``1234567`` ``````bool doesExist(int n) { for (auto ptr = head; ptr && *ptr <= n; ptr = ptr->next) if (*ptr == n) return true; return false; }``````

Yes, with a "simple" linked-list it is not possible to use a binary search, which would be able to find the number in O(log2(n)) time. I think the best you can do with a linked-list is iterating through the list, element by element. You can stop iterating when the numbers become larger than the number you are looking for (assuming the list is sorted in ascending order), but that doesn't change the fact that you'll need O(n) time.

If you have an array of linked-lists, you'll have to repeat the whole process for each linked-list in the array.
Last edited on
a typical use of this is a hash bucket -- you hash to the array location and search a *very small* linked list for the answer. If the lists become long, its not much of an approach, but if you can ensure them to stay small, its very good.
that changes from what he said ^^ about O(n) to not quite O(1)

a stupid example...
say you have uniform values from 0 to 1000
if you take the numbers % 100 you can shove them into a 100 slot array's list storage.
if you had 5000 total numbers, the lists would be about 50 each, your max search would be about 50. Lot of ifs there... its on you to ensure uniform distribution across the array part.

if you instead had a binary search over a sorted array, you only need to search 13 or so items.
if you changed that to %100 and had 1000 buckets in the array, you only need to search 5 items or so, binsearch remains 13 .. twice as good... but probably not much faster due to the memory access and other considerations.
Last edited on
 ``1234567891011121314151617181920212223242526272829303132333435363738394041`` ``````#include #include #include #include template < std::size_t N > using array_of_lists_t = std::array< std::list, N > ; int main() { // an array of linked lists sorted in ascending order const array_of_lists_t<3> array_of_lists { std::list{0,1,2,3}, {4,5,6}, {7,8,9} } ; for( int number = -2 ; number < 12 ; ++number ) { // search for the presence of the number in the sorted array of linked lists // complexity: O(M) + O(N) if it is present, O(M) otherwise // where M is the size of the array, // N is the size of the list which could contain the number bool found = false ; for( const auto& lst : array_of_lists ) // for each sorted list in the array O(M) { // check if the number could be in this sorted list if( !lst.empty() ) { if( lst.back() >= number ) // would be in this list if it is there { if( lst.front() <= number ) // check if the number is in this list found = std::binary_search( lst.begin(), lst.end(), number ) ; // not random access iterator, so O(N) break ; // futile to search in later lists } } } std::cout << "found " << number << "? " << std::boolalpha << found << '\n' ; } }``````

https://coliru.stacked-crooked.com/a/cb0229e53317e7cd
 ``12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061`` ``````#include #include #include #include template < std::size_t N > using array_of_lists_t = std::array< std::list, N > ; void print_list( const std::list& lst ) { std::cout << "[ " ; for( int v : lst ) std::cout << v << ' ' ; std::cout << "]\n" ; } int main() { // an array of linked lists sorted in ascending order const array_of_lists_t<3> array_of_lists { std::list{ 10, 11, 14 }, { 18, 20 }, { 22, 24, 26, 28 } } ; for( int number = 0 ; number < 100 ; ++number ) { // search for the presence of the number in the sorted array of linked lists // complexity: O(M) + O(N) if it is present, O(M) otherwise // where M is the size of the array, // N is the size of the list which could contain the number [[maybe_unused]] bool found = false ; // *** note *** : high cyclomatic complexity below, ideally re-factor the code into small functions for( const auto& lst : array_of_lists ) // for each sorted list in the array O(M) { // check if the number could be in this sorted list if( !lst.empty() ) { if( lst.back() >= number ) // would be in this list if it is there { if( lst.front() <= number ) // check if the number is in this list { for( const int& value : lst ) // for each number in the list O(N) { if( value == number ) { found = true ; // found it // print the address where it is found and the contents of the list which contains the number std::cout << "found " << number << " at address " << std::addressof(value) << " in list " ; print_list(lst) ; } } } break ; // futile to search in later lists } } } // if(!found) std::cout << "did not find " << number << '\n' ; } }``````