Write a C program that generates 10 random numbers, store them in a linked list, display the content of the list and search for an item on the list using the binary search algorithm. Once the search is done, delete the list.

Source Code

Brief explanation is provided after the source code.

#include <stdio.h>
#include <stdlib.h>

typedef struct node *LINK;
struct node {
    int item;
    LINK next;
};

void list_add(LINK *head, int item);
void list_prn(LINK head);
int binary_search(int key, LINK head);
void list_delete(LINK head);

int main(int argc, char ** argv) {
    int i;
    LINK head;
    head = NULL; /* empty list */
    // Generate 10 random numbers and store them in a linked list
    for (i = 1; i <= 10; i++) {
        list_add(&head, rand() % 1000);
    }
    // Display content of list
    list_prn(head);

    // Search for key on the list
    int key = 386;

    if(binary_search(key, head))
        printf("%d was found on the list\n", key);
    else
        printf("%d not found\n", key);
    // Delete list
    list_delete(head);
    printf("\nList deleted\n");

    return 0;
}

// Add items to the front or beginning of the list
void list_add(LINK *head, int item) {
    LINK tmp;
    /*allocate space for new node*/
    if ((tmp = malloc(sizeof(*tmp))) == NULL) {
        printf("\nNot enough memory");
        exit(1);
    }
    tmp -> item = item;
    tmp -> next = *head;
    *head = tmp;
}

// Print list beginning with the head
void list_prn(LINK head) {
    LINK tmp = head;
    printf("List items:\n");
    while(tmp != NULL) {
        printf("%d ", tmp->item);
        tmp = tmp->next;
    }
    printf("\n");
}

void list_sort(LINK head) {
    LINK tmp, track_node;
    int min;
    // Find node with smallest value in list
    while (head->next != NULL){
        tmp = head;
        min = tmp->item;
        while(tmp->next != NULL) {
            if(tmp->next->item < min) {
                min = tmp->next->item;
                track_node = tmp->next;
            }
            tmp = tmp -> next;
        }
        // Interchange its data with that at the top of the list
        track_node->item = head->item;
        head->item = min;
        // Assign Node next to the top as new top
        head = head -> next;
        track_node = head;
    }
}

// Return number of nodes in list
int number_of_nodes(LINK head){
    LINK tmp = head;
    int node_counter = 0;
    while(tmp != NULL) {
        node_counter++;
        tmp = tmp -> next;
    }
    return node_counter;
}

/*
    Function to perform binary search on the sorted list
    More efficient and widely used algorithm
*/
int binary_search(int key, LINK head){
    int low, high, mid, i, found = 0;
    low = 0;
    list_sort(head);  // First sort list to make search meaningful
    high = number_of_nodes(head);
    LINK tmp = head;

    while (low <= high) {

        mid = i = (low + high)/2;

        while (i > 1){
            tmp = tmp -> next;
            i--;
        }

        if (key < tmp->item)
            high = mid - 1;
        else if (key > tmp->item)
            low = mid + 1;
        else {
            /* found match */
            found = 1;
            break;
        }
        tmp = head;
    }
    return found;

}

// Loop through each node and free up the space used by that node
void list_delete(LINK head) {
    LINK tmp;
    while (head != NULL) {
       tmp = head -> next;
       free(head);
       head = tmp;
    }
}

When you compile and execute the above program it produces the following result on Linux:

Case 1: Search Key = 386

List items:
421 649 492 386 335 793 915 777 886 383 
386 was found on the list

List deleted

Case 2: Search Key = 500

List items:
421 649 492 386 335 793 915 777 886 383 
500 not found

List deleted

Brief Explanation

  • A linked list is a collection of linearly connected structures.
  • The program starts by setting the head of the list to NULL (empty list).The function list_prn, takes the head of the list as parameter and display the content of the list.
  • The function list_add which takes two parameters (list head and random number) is used to add a random number to the list. Items in this example are added to the front of the list.
  • The function list_prn, takes the head of the list as parameter and display the content of the list beginning with the head.
  • The integer variable key is used as a search parameter. Here, we are interested to find out whether the key exist on the list. You could as well modify the program so that the user enters the value he/she wants to search on the list.
  • A binary search algorithm is a fundamental algorithm in computer science. It is used to quickly find a value in a sorted sequence (for example a sorted array, linked list etc). Binary search maintains a contiguous subsequence of the starting sequence where the target value is surely located. This is called the search space. The search space is initially the entire sequence. At each step, the algorithm compares the median value in the search space to the target value. Based on the comparison and because the sequence is sorted, it can then eliminate half of the search space. By doing this repeatedly, it will eventually be left with a search space consisting of a single element, the target value (For more detailed explanation, checkout topcoder).
  • A binary search algorithm is a more efficient and widely used algorithm. The function binary_search takes the key (what we are looking for) and the head of the list as parameter and perform the search. It returns 1 if the key is found and 0 otherwise. The binary_search function calls another function list_sort which sorts the linked list to make the search meaningful.
  • Once the search is done, the function list_delete deletes the linked list by looping through each node and freeing up the space used by the node.

Wow, that's for linked list today. If you enjoyed this post, just click the share button below. Have fun coding.

Add comment


Security code
Refresh