Templates: Generic Linked List, I stuck at returning type in template functions.

[babaliaris]

Hello.

Until now, I used to do things the old way (As I learned in the java course). For example, in order to create a generic linked list, I would create a Node class which the user can inherit to define what data this node will contain and a List class which the user can inherit in order to override things like the search method etc.

I started learning templates and for learning purposes, I'm trying to make a linked list. This is where I stuck:

        //Search.
        template<typename U>
        T *search(bool (*compare)(const T other, U custom), U custom)
        {
            //Current node starts from the head.
            LinkedListNode<T> *current = m_Head;

            //GO though each node until the end.
            while (current != NULL)
            {   
                //Do the comparison based on the user's custom function.
                if ( compare(current->m_Data, custom) )
                    return current->m_Data;

                //Next node.
                current = current->m_Next;
            }
      
            //??????????????????????????????????????????????????????
            //Not found.
            return null; //WHAT SHOULD I RETURN HERE????????????????????
           //??????????????????????????????????????????????????????
        }

If the comparison (as defined by the user) returns true, then I'm returning current->m_Data which is type T. But if the search fails what should I return? I don't know what type T is yet.

I solved this by returning the entire list node to the user as a pointer. This solves the problem but the following is very confusing:

//Search.
        template<typename U>
        LinkedListNode<T> *search(bool (*compare)(const T other, U custom), U custom)
        {
            //Current node starts from the head.
            LinkedListNode<T> *current = m_Head;

            //GO though each node until the end.
            while (current != NULL)
            {   
                //Do the comparison based on the user's custom function.
                if ( compare(current->m_Data, custom) )
                    return current;

                //Next node.
                current = current->m_Next;
            }

            //Not found.
            return NULL;
        }


        //Remove.
        template<typename U>
        bool remove(bool (*compare)(const T other, U custom), U custom)
        {
            LinkedListNode<T> *found = this->search(compare, custom);

            if (found != NULL)
            {
                delete found;
                return true;
            }

            return false;
        }

Remove() uses the search method to find and remove a node from the list. As you can see it returns a boolean. The thing is that I want to return the actual data T which is stored in found->m_Data. The reason is that if that data is an allocated object I want to give the user that object back to him because the deletion of the node won't handle the deletion of the data too. Also, I can't return the node as I did in the search method because I am deleting it.

Should I create another wrapper class to hold the data? But this is not good. After returning that wrapper object, who is going to delete it afterward, the user?

What should I do?

Should I ask the user through a constructor to provide me with a T value that will be returned in cases such as the above? For example, if the linked list stores int's the user might give me the value -1 in case of a search not found error. If he stores pointers, he might give me NULL.