Write a program which given a pointer to a linked list, returns the number of nodes in 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 number_of_nodes(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);

    // Display number of nodes
    printf("Number of nodes: %d", number_of_nodes(head));

    // 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");
}

// 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;
}

// 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:

List items:
421 649 492 386 335 793 915 777 886 383 
Number of nodes: 10
List deleted

Brief Explanation

  • A linked list is a collection of linearly connected structures.
  • A variable of type LINK is a pointer to a node on the linked list
  • The function number_of_nodes is used to compute the number of nodes in the list. Starting with the head of the list, the function checks to make sure is not NULL and keeps counting until it reaches the end of the list.

Add comment


Security code
Refresh