In some data structure like the stack, we may want to pop elements content always from the head of the linked list, or, as in the queue case, always from the tail. We may also face very easily a case where the list must be scanned, indexed or sorted in some way, to get to the element we wish to extract the data from. In a case like this, we must be able to search the data, by comparing each piece of it with some kind of query, like an index, a string, or whatever we can use as reference to what it's stored inside the structure. To stick to the style of this tutorial, we will take in to consideration the simplest case scenario, by writing a function that will allow us to check a linked list and determine if it contains a specific integer value. The following function expands on the code given in the previous post
int pop_val( list ** llist, int val )
{
list * curr = *llist;
list * prev = NULL;
while( curr != NULL )
{
if( curr->data == val )
{
if( prev == NULL )
{
*llist = curr->next;
}
else
{
prev->next = curr->next;
}
free( curr );
printf( "pop_val: %d\n", val );
return 0;
}
prev = curr;
curr = curr->next;
}
printf( "pop_val:value %d not found!\n", val );
return 1;
}
the function will return 0, if the value passed is found, 1 otherwise.
The most important thing to note is the introduction of the variable prev, which is needed to keep track of the previous element. We need to store an element in case we scan it without finding the value we are looking for. Once we encounter the element containing the right value
if( curr->data == val )
if pre is null, which means that we have found the value in the first element of the list, we simply fix the first element, by copying inside it the second one
*llist = curr->next;
and deleting the first through curr
free(curr);
else we copy the next list's element inside prev own next pointer
prev->next = curr->next;
reconnecting the list before the current element is deleted.
In each iteration we copy curr in prev, if we didn't find in it the value searched. This is done just before the pointer is advanced to the next element
prev = curr;
curr = curr->next;
to test the function pop_val(), we will use the code given in the previous post .
The following is the new main function of the test code
int main()
{
/* Initializes the linked list with 10. mylist = { 10 } */
list * mylist = create(10);
puts("created list with 10 at first node");
/* Appends 4 elements. mylist = { 10, 20, 30, 40, 50 } */
append(mylist, 20);
append(mylist, 30);
append(mylist, 40);
append(mylist, 50);
/* Pushes 2 elements. mylist = { 4, 2, 10, 20, 30, 40, 50 } */
push(&mylist, 2);
push(&mylist, 4);
print(mylist);
/* Pops 2 elements from tail. mylist = { 4, 2, 10, 20, 30 } */
int data = pop_tail(&mylist);
printf("pop_tail returned:%d\n", data);
data = pop_tail(&mylist);
printf("pop_tail returned:%d\n", data);
/* Pops 1 element from head. mylist = { 2, 10, 20, 30 } */
data = pop(&mylist);
printf("pop returned:%d\n", data);
/* Pops the element storing 10. mylist = { 2, 20, 30 } */
pop_val(&mylist, 20);
/* Pops the element storing 2. mylist = { 20, 30 } */
pop_val(&mylist, 2);
print(mylist);
return 0;
}
