Number of occurrences of all elements in a linked list in C?

Algorithm
1. Maintain a separate link list (occurance list) and maintain a node for each unique value in the original linklist.
2. Traverse the link list and for each element.
2.a Create a node in the occur list if it is not there and initialize count by 1.
2.b If already there then increase the count by one.

Sample Code

struct node
{
    int data;
    struct node *next;
};

struct node_occur
{
    int data;
    int times;
    struct node_occur *next;
};

/* We can have additional structure which can have head and last node is node pointer and 
   additionally can have length variable which contains the length of the link list */
struct node *head = NULL, *last = NULL;
int length = 0;


struct node * create_node(int data)
{
    struct node *new;

    new = (struct node*)malloc(sizeof(struct node));
    new->next = null;
    new->data = data;

    length++;

    return new;
}

void insert_at_begining(int info)
{
    struct node *new;
    new = create_node(info);

    if (head == NULL && last == null)
    {   
        head = last = new;
        head->next = last->next = NULL;
    }
    else
    {
        new->next = head;
        head = new;
    }
}

void occur(struct node *head, struct node_occur **result)
{
    struct node *p;
    struct node_occur *temp, *prev;

    p = head;
    while (p != NULL)
    {
        temp = *result;
        while (temp != NULL && temp->data != p->data)
        {
            prev = temp;
            temp = temp->next;
        }

        if (temp == NULL)
        {
            temp = (struct node_occur *)malloc(sizeof(struct node_occur));
            temp->data = p->data;
            temp->times = 1;
            temp->next = NULL;
            if (*result != NULL)
            {
                prev->next = temp;
            }
            else
            {
                *result = temp;
            }
        }
        else
        {
            temp->times += 1;
        }
        p = p->next;
    }
}

void disp_occur(struct node_occur *head)
{
    while (head != NULL)
    {
        printf("    %d\t%d\n", head->data, head->times);
        head = head->next;
    }
}

void traverse()
{
    if (head == NULL)
        printf("\n List is empty");
    else
    {
        x = head;
        while (x->next !=  head)
        { 
            printf("%d->", x->data);
            x = x->next;
        }
        printf("%d", x->data);
    }
}

Generic Linked List Implementation in C

#include <stdio.h>
#include <malloc.h>
#include <string.h>

typedef int bool;
enum { false, true };

typedef enum {
   int_t =0,
   float_t =1,
   char_t =2 
} datatype;

struct node
{
   void *info;
   datatype d;
   struct node *next;
} *ptr1,*newnode,*start;

void insert_at_last(struct node **bt,void *data,int n)
{
   struct node *temp = *bt;
   ptr1=(*bt);
   switch(n)
   {
      case int_t:
        newnode= (struct node *)malloc(sizeof(struct node));
        newnode->d=int_t;
        newnode->info = malloc(sizeof(int));
        memcpy(newnode->info,data,sizeof(int));
        break;

      case float_t:
        newnode= (struct node *)malloc(sizeof(struct node));
        newnode->d=float_t;
        newnode->info = malloc(sizeof(float));
        memcpy(newnode->info,data,sizeof(float));
        break;

      case char_t:
        newnode= (struct node *)malloc(sizeof(struct node));
        newnode->d=char_t;
        newnode->info = malloc(sizeof(char));
        memcpy(newnode->info,data,sizeof(char));
        break;

      default:
        break;
   }

   newnode->next=NULL;

   if((*bt)==NULL)
      *bt=newnode;
   else
   {
      while(temp->next!=NULL)
           temp = temp->next;
      temp->next=newnode;
   }
}

void display(struct node *ptr)
{
   if(ptr==NULL)
      printf("List Empty\n");
   else
   {
     while(ptr!=NULL)
     {
      if(ptr->d==int_t)
        printf("%d :",*(int*)ptr->info);
      if(ptr->d==float_t)
        printf("%f :",*(float*)ptr->info);
      if(ptr->d==char_t)
        printf("%c :",*(char*)ptr->info);

      ptr=ptr->next;
     }
   }
   printf("\n");
}

int main()
{
   int toExit = 0;
   int i,j;
   datatype choice;
   char c;
   float f;
   start=NULL;
   for(j=0;j<5;j++)
   {
      printf("Enter which type u want to enter : 13 to exit\n");
      scanf("%d",&choice);

      switch(choice)
      {
         case int_t:
            printf("Enter int data\n");
            scanf("%d",&i);
            insert_at_last(&start,&i,int_t);
            break;

         case float_t:
          printf("Enter float data\n");
            scanf("%f",&f);
            insert_at_last(&start,&f,float_t);
            break;

         case char_t:
            printf("Enter char data\n");
            getchar();
            scanf("%c",&c);
            insert_at_last(&start,&c,char_t);
            break;

         default:
            toExit = 1;
            break;
      }

      if (toExit)
      {
         break;
      }
   }

   display(start);
}

Number of occurrences of all elements in a linked list in C?

Your comment on this post:

Related Articles