How can i bulid this function

[dwain200010]

orderedLinearSearch (ListNode<NODETYPE> &currPtr, ListNode<NODETYPE>
&predPtr, bool &found, bool &doneSearching,
NODETYPE & dataToSearch)
{
/*
‘doneSearching’ becomes true when either:
1.) Your search finds a listNode within the List whose data is equal in value to ‘dataToSearch’ or
2.) Your search finds a listNode within the List whose data is greater in value than that of ‘dataToSearch’
*/

//’found’ will be set to true if the search successfully located a listnode whose data is equal in value to ‘dataToSearch’. Otherwise, found is set to false.

//’predPtr’ is the pointer that will eventually point to the listnode whose position is before the location you want to insert at.

//’currPtr’ is the pointer that is used to traverse the list and keep track of the current listnode position as you move through the list

[Duthomhas]

It looks like your function is trying to do too much, and it is inappropriately mixing operations between caller and callee. Also, it has some confusing naming conventions. Finally, it lacks proper error termination conditions (for example, if you run out of nodes to search).

Did you get this function from your professor, or did you create it yourself?

If your professor gave it to you
Well, then, you've got to work with what you've got, alas.

This function is designed to work in a loop. That is, your calling code will look something like:

// givens:
ListNode <NODETYPE> firstNodePtr;
NODETYPE           itemToFind;

// locals:
ListNode <NODETYPE> currPtr;
ListNode <NODETYPE> predPtr;
bool found;
bool done;

// algorithm:
currPtr = firstNodePtr;  // the list to search
done    = false;         // we aren't done yet

while (!done)
  {
  orderedLinearSearch( currPtr, predPtr, found, done, itemToFind );
  }

// results:
// predPtr == place to insert data
// found   == true iff *currPtr has the same value as itemToFind; false otherwise 

If you created it yourself
Then I suggest a simple rewrite. When searching for something, you only need to provide the list to search and the item to find. The function then only needs to return the place where it was found. If it wasn't found, it can return NULL.

Here's a side-note about the design of your list. Typically a linked list is of the form:

template <typename NODETYPE>
struct ListNode
  {
  NODETYPE data;
  ListNode <NODETYPE> * next;
  ListNode <NODETYPE> * previous;  // (optional)
  };

I will assume a unidirectional list (which doesn't have a previous link).

A list starts at the head, and ends when next is NULL. This adds two complications:

» inserting at the head of the list means that you have a new head of the list
» inserting at the end of the list is the same as appending to the list

Each one of these introduces a small problem. For the first, you must replace your firstNodePtr when inserting at the head of the list (the trick is to know when you are inserting at the head of the list). The second is that if you hit the end of the list, you would have to traverse the entire list again to append an item to the list. We will solve both of these problems in a second.

Simplistically, you can search the list with a function as simple as:

template <NODETYPE>
ListNode <NODETYPE> *
orderedLinearSearch( ListNode <NODETYPE> * head, NODETYPE itemToFind );

And we will specify that the function returns the item before the matching item, or NULL if the matching item is the first item in the list. This solves both of our problems:

» If we match at the head of the list, we know it because the function returned NULL
» If we match at the end of the list, we know it because the result->next is NULL

This works because in order to insert you need to have the node before the node to insert at.

The original function also wanted to report whether or not the itemToFind was exactly matched. This new design allows you to find that information easily by simply comparing if against the next item's value.

ListNode <NODETYPE> * result      = orderedLinearSearch( firstNodePtr, itemToFind );
ListNode <NODETYPE> * matchedItem = (result ? result->next : firstNodePtr);
bool found = matchedItem && (matchedItem->data == itemToFind);

In this case, also, the loop is inside the orderedLinearSearch() function, instead of outside it, as it was before.

Hope this helps.

[edit] Linked lists are a bit tricky, specifically because of some of the points touched upon above. For example, handling the list head, and inserting after a specific item.