For Looping Link List using Templates

Question

Having used the various search engines (and the wonderful stackoverflow database), I have found some similar situations, but they are either far more complex, or not nearly as complex as what I'm trying to accomplish.

C++ List Looping Link Error Using Templates C++:Linked List Ordering Pointer Address Does Not Change In A Link List

I'm trying to work with Link List and Node templates to store and print non-standard class objects (in this case, a collection of categorized contacts). Particularly, I want to print multiple objects that have the same category, out of a bunch of objects with different categories. When printing by category, I compare an sub-object tmpCategory (= "business") with the category part of a categorized contact.

But how to extract this data for comparison in int main()?

Here's what I'm thinking. I create a GetItem member function in LinkList.tem This would initialize the pointer cursor and then run a For loop until the function input matches the iteration number. At which point, GetItem returns object Type using (cursor -> data).

template <class Type>
Type LinkList<Type>::GetItem(int itemNumber) const
{
    Node<Type>* cursor = NULL;

    for(cursor = first;
        cursor != NULL;
        cursor = (cursor -> next))
    {
        for(int i = 0; i < used; i++)
        {
            if(itemNumber == i)
            {
                return(cursor -> data);
            }
        }
    }
}

Here's where int main() comes in. I set my comparison object tmpCategory to a certain value (in this case, "Business"). Then, I run a For loop that iterates for cycles equal to the number of Nodes I have (as determined by a function GetUsed()). Inside that loop, I call GetItem, using the current iteration number. Theoretically, this would let the int main loop return the corresponding Node from LinkList.tem. From there, I call the category from the object inside that Node's data (which currently works), which would be compared with tmpCategory. If there's a match, the loop will print out the entire Node's data object.

tmpCategory = "Business";

for(int i = 0; i < myCategorizedContact.GetUsed(); i++)
{
    if(myCategorizedContact.GetItem(i).getCategory() == tmpCategory)
       cout << myCategorizedContact.GetItem(i);
}

The problem is that the currently setup (while it does run), it returns nothing at all. Upon further testing ( cout << myCategorizedContact.GetItem(i).getCategory() ), I found that it's just printing out the category of the first Node over and over again. I want the overall scheme to evaluate for every Node and print out matching data, not just spit out the same Node.

Any ideas/suggestions are greatly appreciated.

Answer 1

Please look at this very carefully:

template <class Type>
Type LinkList<Type>::GetItem(int itemNumber) const
{
    Node<Type>* cursor = NULL;

    // loop over all items in the linked list    
    for(cursor = first;
        cursor != NULL;
        cursor = (cursor -> next))
    {
        // for each item in the linked list, run a for-loop 
        // counter from 0 to (used-1). 
        for(int i = 0; i < used; i++)
        {
            // if the passed in itemNumber matches 'i' anytime
            //  before we reach the end of the for-loop, return
            //  whatever the current cursor is.
            if(itemNumber == i)
            {
                return(cursor -> data);
            }
        }
    }
}

You're not walking the cursor down the list itemNumber times. The very first item cursor references will kick off the inner-for-loop. The moment that loop index reaches itemNumber you return. You never advance your cursor if the linked list has at least itemNumber items in the list.. In fact, the two of them (cursor and itemNumber) are entirely unrelated in your implementation of this function. And to really add irony, since used and cursor are entirely unrelated, if used is ever less than itemNumber, it will ALWAYS be so, since used doesn't change when cursor advances through the outer loop. Thus cursor eventually becomes NULL and the results of this function are undefined (no return value). In summary, as written you will always either return the first item (if itemNumber < used), or undefined behavior since you have no return value.

I believe you need something like the following instead:

template< class Type >
Type LinkList<Type>::GetItem(int itemNumber) const
{
    const Node<Type>* cursor = first;
    while (cursor && itemNumber-- > 0)
        cursor = cursor->next;

    if (cursor)
        return cursor->data;

    // note: this is here because you're definition is to return
    //  an item COPY. This case would be better off returning a 
    //  `const Type*` instead, which would at least allow you to
    //  communicate to the caller that there was no item at the 
    //  proposed index (because the list is undersized) and return
    //  NULL, which the caller could check.
    return Type();
}