Page 259 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures

Notes 14.1.3 Sequential Search on Linked Lists

Sequential search is the most common search used on linked list structures. Let’s take a look at
how this search can be applied to linked lists.
We define our linked list structure as:
typedef struct _list_t_ {
int data;
struct _list_t_ *next;
} list_t;
Our sequential search function for linked lists will take two arguments: a pointer to the first
element in the list and the value for which we are searching. The function will return a pointer
to the list structure containing the correct data, or will return NULL if the value wasn’t found.
Why do we need to pass in the number of elements in the array for the array version and not the
number of elements in the list for the linked list version? Because we can easily tell when we’re
at the end of our list by checking to see if the element is NULL, whereas with our array the
computer has no way of knowing how big it is without us telling it. Our function declaration is
as follows:
list_t *sequential_search(list_t *list, int value);
Step 1: Just like the array version, we need to look at every element in the list, so we need a loop.
We start at the first element in list, and while the current element is not NULL (meaning we
haven’t reached the end), we go on to the next element:
for( ; list!=NULL; list=list->next) {
...
}
Step 2: If the current element contains the data we’re looking for, then return a pointer to it.
for( ; list!=NULL; list=list->next) {
if (list->data == value) return list;
}
Step 3: If after looking at every element in the list, we haven’t found the value for which we are
searching, then the value doesn’t exist in the list. Return an error flag appropriately:
for( ; list!=NULL; list=list->next) {
if (list->data == value) return list;
}
return NULL;
Step 4: Our final search function is:
list_t *sequential_search(list_t *list, int value)
{
/* look at every node in the list */
for( ; list!=NULL; list=list->next) {
/* if this node contains the given value, return the node */
if (list->data == value) return list;
}

252 LOVELY PROFESSIONAL UNIVERSITY