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?
I do not know how to write it. please help me.
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.
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.
#include <iostream>
#include <list>
#include <array>
#include <algorithm>
template < std::size_t N > using array_of_lists_t = std::array< std::list<int>, 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( constauto& 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' ;
}
}
Thank you for your help
My main problem is that I do not know how to show this linked list implemented in the one array in c ++ coding and how do I display a pointer that points to an array cell that contains a liked list node?(in search of element by element)
You don't need to implemented a linked-list yourself, because you can use the std::list class from the C++ Standard Library, which is a linked-list. If you want an array of linked-lists, use std::array of std::list's.
Internally, an std::list uses nodes that are linked together by pointers, but you don't need to bother about these implementation details. Just use the existing class via its "official" documented interface:
#include <iostream>
#include <list>
#include <array>
#include <algorithm>
template < std::size_t N > using array_of_lists_t = std::array< std::list<int>, N > ;
void print_list( const std::list<int>& 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( constauto& 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( constint& 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' ;
}
}