array of linkedlist

[aida1]

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.

[kigar64551]

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?

[seeplus]

Well the logic to search an ascending sorted linked list is something like this - depending upon how the list is defined:

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

	return false;
}

[kigar64551]

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.

[jonnin]

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.

[JLBorges]

#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( 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

[aida1]

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)

[kigar64551]

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:

https://www.cplusplus.com/reference/list/list/

https://www.cplusplus.com/reference/array/array/

[JLBorges]

#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( 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' ;
    }
}

https://coliru.stacked-crooked.com/a/4e272b4942d890cd