C++ Data Structures and Algorithms

Finding out the index of a selected item in the List ADT

The Search() method will also iterate each items' list until it finds the matched value. The return value of this method will be the index of List. It will return -1 if no result is found. The implementation should be as follows:

int List::Search(int val){    // Looping through the array elements    // return the array index if value is found    for(int i=0; i < m_count; ++i)    {        if(m_items[i] == val)        {            return i;        }    }    return -1;}

As you can guess, the complexity of this method will be O(n) for the average and worst case scenarios, since it will iterate through all list elements. However, in the best case, it can be O(1) if val is found at the first position.