Searching a Linked List

Step 1: Define a linked list

A linked list is a list constructed using pointers. A linked list is a list of nodes in which each node has a member variable that is a pointer that points to the next node in the list. It is not fixed in size and can grow and shrink while the program is running. In real life, useful dynamic variables are seldom of a simple type such as int or double. They normally are of more complex types such as struct or class. A structure may have several members. An example of a struct definition that could be used to build a linked list is shown below.

struct ListNode { string item; int count; ListNode *link; };

typedef ListNode* ListNodePtr;

Now if we use this to create a pointer variable head as: ListNodePtr head;

Then we have something that looks like this:

Step 2: Searching a Linked List

In the previous discussion, we learned to create linked lists. In this part, you will learn to search a linked list to locate a particular node and remove it (remove operation is optional).

Find the searchList.cpp from Lab 9 introduction. Fill in the missing codes.

As it is the case with every search, we should have a clear and precise idea of what we are searching for. Because structs are the building blocks of a linked list, we should search search for something that is defined as a member of the struct. For example, in the linked list that we defined in the previous activity, we could search for an item or a count. We could search for item "Jam" or a count 10. It seems that the first search is more common. In any case, a search function that searches the list for one of these two, should have two parameters. The first parameter is the linked list and the second one is the item.

NodePtr search(NodePtr head, string target_item)

Note that due the fact that we do not modify the linked list, we don't pass the list as call-by-reference.

The Pseudocode for the search function may look like this:

//Make the pointer variable here point to the head node (that is, the first node) of the linked list.

while( here is not pointing to a node containing the target_item and here is not pointing to the last node) { Make here point to the next node in the list.

}

if(the node pointed to by here contains target) return here; else return NULL:

Now suppose we want to search the linked list that we have created.

// Program to demonstrate the function search.

// filling in the blank

#include

#include

#include

using namespace std;

struct Node

{

};

typedef Node* NodePtr;

NodePtr search(NodePtr head, string an_item);

void head_insert(NodePtr& head, string an_item, int a_number);

void show_list(NodePtr& head);

int main()

{

NodePtr head = NULL;

head_insert(head, "Tea", 2);

head_insert(head, "Jam", 3);

head_insert(head, "Rolls", 10);

return 0;

}

NodePtr search(NodePtr head, string target)

{

}

void head_insert(NodePtr& head, string an_item, int a_number)

{

}

void show_list(NodePtr& head)

{

}