Browse by Domains
Table of Contents

Data Structures using C | What are the Data Structure in C and How it works?

By Updated on Apr 6, 2022 95453
Table of contents
  1. What is C Programming Language?
  2. What are data structures using C?
  3. Array
  4. Linked List
  5. Stack 
  6. Queue
  7. Binary Tree
  8. Binary Search Tree
  9. Heap
  10. Hashing 
  11. Graph

What is C Programming Language?

  • Designed by Dennis Ritchie
  • First appearance- 1972
  • Uses extension .c or .h
  • Developed to make assembly language work much easier
  • Procedural Language
  • Much faster
  • Handles low-level activity much better
  • UNIX OS and RDBMS MYSQL is written in C

You can also take up the Free Data Structures for C Course on Great Learning Academy and upskill. Learn more about the Implementation of Data Structures using C programming language, Arrays, Linked Lists, Binary Tree, and so much more.

What are Data Structures using C?

  • Made up of 2 words
    • “DATA” + “STRUCTURES”
  • It is a way to arrange data in computers
  • Example: You might want to store data in
    • Linear fashion – Array/ Linked List
    • One on the other – Stacks
    • Hierarchical Fashion – Trees
    • Connect nodes – Graph

List of Data Structures using C

  • Array
  • Linked List
  • Stack 
  • Queue
  • Binary Tree
  • Binary Search Tree
  • Heap
  • Hashing 
  • Graph

Also Read: How to choose the right programming language for Data Science?

Array

  • Linear Data Structures using C
  • Elements are stored in contiguous memory locations
  • Can access elements randomly using index
  • Stores homogeneous elements i.e, similar elements
  • Syntax:
  • Array declaration
    • Datatype varname [size]  ;
  • Can also do declaration and initialization at once
    • Datatype varname [] = {ele1, ele2, ele3, ele4};

Advantages

  • Random access
  • Easy sorting and iteration
  • Replacement of multiple variables

Disadvantages

  • Size is fixed
  • Difficult to insert and delete
  • If capacity is more and occupancy less, most of the array gets wasted 
  • Needs contiguous memory to get allocated

Applications

  • For storing information in a linear fashion
  • Suitable for applications that require frequent searching

Array Examples

#include <stdio.h>
int main() {
	//array declaration
	int rollNo[10];
	
	//taking inputs
	for(int i=0;i<10;i++)
	    scanf("%d",&rollNo[i]);
	
	//printing
	for(int i=0;i<10;i++)
	    printf("%d ",rollNo[i]);
	return 0;
}

Input:
12 13 34 56 12 87 56 78 23 10

Output:
12 13 34 56 12 87 56 78 23 10


#include <stdio.h>

int main() 
{
  int marks[20], i, n, sum = 0, avg;

  printf("Enter the number of elements: ");
  scanf("%d", &n);

  for(i=0; i < n; ++i) 
{
    printf("Enter number%d: ",i+1);
    scanf("%d", &marks[i]);
    sum += marks[i];
  }

  avg = sum / n;
  printf("Avg = %d", avg);
  return 0;

}

Input and Output:

Linked List

  • Linear Data Structure
  • Elements can be stored as per memory availability
  • Can access elements on linear fashion only
  • Stores homogeneous elements i.e, similar elements
  • Dynamic in size
  • Easy insertion and deletion 
  • Starting element or node is the key which is generally termed as the head.

Advantages of Data Structure using C

  • Dynamic in size
  • No wastage as capacity and size is always equal
  • Easy insertion and deletion as 1 link manipulation is required
  • Efficient memory allocation

Disadvantages of Data Structure using C

  • If the head node is lost, the linked list is lost
  • No random access possible

Applications of Data Structure using C

  • Suitable where memory is limited 
  • Suitable for applications that require frequent insertion and deletion

Also Read: Introduction to Linear Programming

Examples Linked List

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct node
{int data;
 struct node *next;
}*p,*tmp,*tmp1;
void insert_end(int);
void insert_beg(int);
void ldelete(int);
void display();
void main()
{ 
  int val,n;
  p=NULL;
  do
	{printf("\n************************* MENU ************************");
	 printf("\n1.INSERT AT END");
	 printf("\n2.INSERT AT BEG");
	 printf("\n3.DELETE A PARTICULAR ELE");
	 printf("\n4.DELETE FROM BEG");
	 printf("\n5.DELETE FROM END");
	 printf("\n6.DISPLAY");
	 printf("\n7.EXIT");
	 printf("\nenter ur choice : ");
	 scanf("%d",&n);
	 switch(n)
		{case 1: printf("\nenter the value ");
			 scanf("%d",&val);
			 insert_end(val);
			 break;
		 case 2: printf("\nenter the value");
			 scanf("%d",&val);
			 insert_beg(val);
			 break;
		 case 3: printf("\nenter the value");
			 scanf("%d",&val);
			 l_delete(val);
			 break;
		 case 4: 
			 delete_beg();
			 break;
		 case 5: 
			 delete_end();
			 break;
		 case 6: display();
		 		 break;
		 case 7: exit(0);
		 		 break;
		 default: printf("\n Wrong Choice!");
		 		  break;
		}
	 printf("\n do u want to cont... ");
	}while('y'==getch());

 }

 void insert_end(int ele)
 {
	  tmp=p;
	  tmp1=(struct node*)malloc(sizeof(struct node));
	  tmp1->data=ele;
	  tmp1->next=NULL;
	  if(p==NULL)
		p=tmp1;
	  else
		{
			while(tmp->next!=NULL)
				tmp=tmp->next;
		 	tmp->next=tmp1;
		 }
 }

void insert_beg(int ele)
{
	 tmp=p;
	 tmp1=(struct node*)malloc(sizeof(struct node));
	 tmp1->data=ele;
	 tmp1->next=p;
	 p=tmp1;
}

void l_delete(int ele)
{
     tmp=p;
	 struct node *pre=tmp;
	 while(tmp!=NULL)
		{if(tmp->data==ele)
		    { if(tmp==p)
		       {p=tmp->next;
			free(tmp);
			return;
			}
		      else
			{pre->next=tmp->next;
			 free(tmp);
			 return;
			 }
		    }
		 else
		    { pre=tmp;
		      tmp=tmp->next;
		    }
		}
	  printf("\n no match found!! ");
 }
 
void delete_beg()
{	
	tmp=p;
	if(p==NULL)
		printf("\n no element to be deleted!! ");
	else
	{
		printf("\nelement deleted - %d", p->data);
		p=p->next;
	}

 }
 
void delete_end()
{	
	tmp=p;
	struct node* pre;
	if(p==NULL)
		printf("\n no element to be deleted!! ");
	else if(p->next==NULL)
	{
		printf("\nelement deleted - %d", p->data);
		p=NULL;

	}
		
	else
	{
		while(tmp->next!=NULL){
			pre=tmp;
			tmp=tmp->next;
		}
		pre->next=NULL;
		printf("\nelement deleted - %d", tmp->data);
		
	}

 }

void display()
{
	tmp=p;
 	while(tmp!=NULL)
		{printf("\n %d",tmp->data);
	 	tmp=tmp->next;
		}
}


Output:


************************* MENU ************************
1.INSERT AT END
2.INSERT AT BEG
3.DELETE A PARTICULAR ELE
4.DELETE FROM BEG
5.DELETE FROM END
6.DISPLAY
7.EXIT
enter your choice : 1

enter the value 23

do u want to cont...
************************* MENU ************************
1.INSERT AT END
2.INSERT AT BEG
3.DELETE A PARTICULAR ELE
4.DELETE FROM BEG
5.DELETE FROM END
6.DISPLAY
7.EXIT
enter ur choice :
1

enter the value 12

do u want to cont...
************************* MENU ************************
1.INSERT AT END
2.INSERT AT BEG
3.DELETE A PARTICULAR ELE
4.DELETE FROM BEG
5.DELETE FROM END
6.DISPLAY
7.EXIT
enter ur choice :
2

enter the value67

do u want to cont...
************************* MENU ************************
1.INSERT AT END
2.INSERT AT BEG
3.DELETE A PARTICULAR ELE
4.DELETE FROM BEG
5.DELETE FROM END
6.DISPLAY
7.EXIT
enter ur choice :
2

enter the value90

do u want to cont...
************************* MENU ************************
1.INSERT AT END
2.INSERT AT BEG
3.DELETE A PARTICULAR ELE
4.DELETE FROM BEG
5.DELETE FROM END
6.DISPLAY
7.EXIT
enter ur choice :
6

 90
 67
 23
 12
do u want to cont...
************************* MENU ************************
1.INSERT AT END
2.INSERT AT BEG
3.DELETE A PARTICULAR ELE
4.DELETE FROM BEG
5.DELETE FROM END
6.DISPLAY
7.EXIT
enter ur choice : 3

enter the value67

do u want to cont...
************************* MENU ************************
1.INSERT AT END
2.INSERT AT BEG
3.DELETE A PARTICULAR ELE
4.DELETE FROM BEG
5.DELETE FROM END
6.DISPLAY
7.EXIT
enter ur choice :
6

 90
 23
 12
do u want to cont...
************************* MENU ************************
1.INSERT AT END
2.INSERT AT BEG
3.DELETE A PARTICULAR ELE
4.DELETE FROM BEG
5.DELETE FROM END
6.DISPLAY
7.EXIT
enter ur choice :
4

element deleted - 90
do u want to cont...
************************* MENU ************************
1.INSERT AT END
2.INSERT AT BEG
3.DELETE A PARTICULAR ELE
4.DELETE FROM BEG
5.DELETE FROM END
6.DISPLAY
7.EXIT
enter ur choice : 5

element deleted - 12
do u want to cont...
************************* MENU ************************
1.INSERT AT END
2.INSERT AT BEG
3.DELETE A PARTICULAR ELE
4.DELETE FROM BEG
5.DELETE FROM END
6.DISPLAY
7.EXIT
enter ur choice : 6

 23
do u want to cont...


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

struct node 
{
    int num;                   
    struct node *nextptr;       
}*stnode;

void createNodeList(int n);    
void reverseDispList();         
void displayList();            
int main()
{
    int n;
    printf("\n\n Linked List : Create a singly linked list and print it in reverse order :\n");
    printf(" Input the number of nodes : ");
    scanf("%d", &n);
    createNodeList(n);
    printf("\n Data entered in the list are : \n");		
    displayList();
    reverseDispList();
    printf("\n The list in reverse are :  \n");
    displayList();
    return 0;
}

void createNodeList(int n)
{
    struct node *fnNode, *tmp;
    int num, i;
    stnode = (struct node *)malloc(sizeof(struct node));
    if(stnode == NULL) 
    {
        printf(" Memory can’t  be allocated.");
    }
    else
    {
        printf(" Input data for node 1 : ");
        scanf("%d", &num);
        stnode-> num = num;      
        stnode-> nextptr = NULL;
        tmp = stnode;
        for(i=2; i<=n; i++)
        {
            fnNode = (struct node *)malloc(sizeof(struct node));
            if(fnNode == NULL) 
            {
                printf(" Memory can not be allocated.");
                break;
            }
            else
            {
                printf(" Input data for node %d : ", i);
                scanf(" %d", &num);
                fnNode->num = num;     
                fnNode->nextptr = NULL; 
                tmp->nextptr = fnNode; 
                tmp = tmp->nextptr;
            }
        }
    }
}

void reverseDispList()
{
    struct node *prevNode, *curNode;
 
    if(stnode != NULL)
    {
        prevNode = stnode;
        curNode = stnode->nextptr;
        stnode = stnode->nextptr;
 
        prevNode->nextptr = NULL;  
        while(stnode != NULL)
        {
            stnode = stnode->nextptr;
            curNode->nextptr = prevNode;
 
            prevNode = curNode;
            curNode = stnode;
        }
        stnode = prevNode; 
    }
}

void displayList()
{
    struct node *tmp;
    if(stnode == NULL)
    {
        printf(" No data found in the list.");
    }
    else
    {
        tmp = stnode;
        while(tmp != NULL)
        {
            printf(" Data = %d\n", tmp->num);   
            tmp = tmp->nextptr;                 
        }
    }
}

Stack

  • It is a type of Linear Data Structures using C
  • Follows LIFO: Last In First Out
  • Only the top elements are available to be accessed
  • Insertion and deletion takes place from the top
  • Eg: a stack of plates, chairs, etc
  • 4 major operations:
    • push(ele) – used to insert element at top
    • pop() – removes the top element from stack
    • isEmpty() – returns true is stack is empty
    • peek() – to get the top element of the stack
  • All operation works in constant time i.e, O(1)

Advantages

  • Maintains data in a LIFO manner
  • The last element is readily available for use
  • All operations are of O(1) complexity

Disadvantages

  • Manipulation is restricted to the top of the stack
  • Not much flexible

Applications

  • Recursion
  • Parsing
  • Browser
  • Editors

Demonstration of Stack – using Array

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

struct stackk { 
	int top; 
	unsigned size; 
	int* array; 
}; 



    
struct stackk* create(unsigned size) 
{ 
	struct stackk* stackk = (struct stackk*)malloc(sizeof(struct stackk)); 
	stackk->size = size; 
	stackk->top = -1; 
	stackk->array = (int*)malloc(stackk->size * sizeof(int)); 
	return stackk; 
} 

int isFull(struct stackk* stackk) 
{ 
	return stackk->top == stackk->size - 1; 
} 

int isEmpty(struct stackk* stackk) 
{ 
	return stackk->top == -1; 
} 

void push(struct stackk* stackk, int item) 
{ 
	if (isFull(stackk)) 
		return; 
	stackk->array[++stackk->top] = item; 
} 


int pop(struct stackk* stackk) 
{ 
	if (isEmpty(stackk)) 
		return -1; 
	return stackk->array[stackk->top--]; 
} 

int peek(struct stackk* stackk) 
{ 
	if (isEmpty(stackk)) 
		return INT_MIN; 
	return stackk->array[stackk->top]; 
} 


int main()
{ 
  int val,n;
  struct stackk* stackk = create(100); 
  do
	{printf("\n************************* MENU ************************");
	 printf("\n1.PUSH");
	 printf("\n2.POP");
	 printf("\n3.PEEK");
	 printf("\n4 IS EMPTY");
	 printf("\n5.EXIT");
	 printf("\n enter ur choice : ");
	 scanf("%d",&n);
	 switch(n)
		{
		 case 1: 
		     printf("\nenter the value ");
			 scanf("%d",&val);
			 push(stackk , val);
			 break;
		 case 2: 
			 printf("\n popped element : %d",pop(stackk));
			 break;
		 
		case 3: 
			printf("\n top element : %d",peek(stackk));
			 break;
		 case 4: printf("\n is empty : %d",isEmpty(stackk));
		 		 break;
		 case 5: exit(0);
		 		 break;
		 default: printf("\n Wrong Choice!");
		 		  break;
		}
	 printf("\n do u want to cont... ");
	}while('y'==getch());

 }




Output:

************************* MENU ************************
1.PUSH
2.POP
3.PEEK
4 IS EMPTY
5.EXIT
enter ur choice :
1

enter the value
45

do u want to cont...
************************* MENU ************************
1.PUSH
2.POP
3.PEEK
4 IS EMPTY
5.EXIT
enter ur choice :
1

enter the value
56

do u want to cont...
************************* MENU ************************
1.PUSH
2.POP
3.PEEK
4 IS EMPTY
5.EXIT
enter ur choice :
3

 top element : 56
do u want to cont...
************************* MENU ************************
1.PUSH
2.POP
3.PEEK
4 IS EMPTY
5.EXIT
enter ur choice :
4

 is empty : 0
do u want to cont...

Demonstration of Stack – using LinkedList

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct node
{int data;
 struct node *next;
}*p,*tmp,*tmp1,*end;
void insert_end(int);
void display();
void delete_end();
void isEmpty();
int main()
{ 
  int val,n;
  p=NULL;
  do
	{printf("\n************************* MENU ************************");
	 printf("\n1.PUSH");
	 printf("\n2.POP");
	 printf("\n3 IS EMPTY");
	 printf("\n4.DISPLAY");
	 printf("\n5.EXIT");
	 printf("\nenter ur choice : ");
	 scanf("%d",&n);
	 switch(n)
		{
		 case 1: 
		     printf("\nenter the value ");
			 scanf("%d",&val);
			 insert_end(val);
			 break;
		 case 2: 
			 delete_end();
			 break;
		 
		case 3: 
			 isEmpty();
			 break;
		 case 4: display();
		 		 break;
		 case 5: exit(0);
		 		 break;
		 default: printf("\n Wrong Choice!");
		 		  break;
		}
	 printf("\ndo u want to cont... ");
	}while('y'==getch());

 }

 void insert_end(int ele)
 {
	  tmp=p;
	  tmp1=(struct node*)malloc(sizeof(struct node));
	  tmp1->data=ele;
	  tmp1->next=NULL;
	  if(p==NULL)
		p=tmp1;
	  else
		{
			while(tmp->next!=NULL)
				tmp=tmp->next;
		 	tmp->next=tmp1;
		 }
	  end=tmp1;
 }


void delete_end()
{	
	tmp=p;
	struct node* pre;
	if(p==NULL)
		printf("\n no element to be deleted!! ");
	else if(p->next==NULL)
	{
		printf("\nelement deleted - %d", p->data);
		p=NULL;
		end=NULL;

	}
		
	else
	{
		while(tmp->next!=NULL){
			pre=tmp;
			tmp=tmp->next;
		}
		pre->next=NULL;
		end=pre;
		printf("\nelement deleted - %d", tmp->data);
		
	}

 }
 


void isEmpty(){
	
 	if(p==NULL)
 		printf("Stack is Empty");
 	else
 	{
 		printf("Stack is Not Empty");
	 }	
}
void display()
{
	tmp=p;
 	while(tmp!=NULL)
		{printf("\n %d",tmp->data);
	 	tmp=tmp->next;
		}
}



Output
 
************************* MENU ************************
1.PUSH
2.POP
3 IS EMPTY
4.DISPLAY
5.EXIT
enter ur choice : 1

enter the value 56

do u want to cont...
************************* MENU ************************
1.PUSH
2.POP
3 IS EMPTY
4.DISPLAY
5.EXIT
enter ur choice :
1

enter the value 67

do u want to cont...
************************* MENU ************************
1.PUSH
2.POP
3 IS EMPTY
4.DISPLAY
5.EXIT
enter ur choice :
3
Stack is Not Empty
do u want to cont...
************************* MENU ************************
1.PUSH
2.POP
3 IS EMPTY
4.DISPLAY
5.EXIT
enter ur choice :
4

 56
 67
do u want to cont...
************************* MENU ************************
1.PUSH
2.POP
3 IS EMPTY
4.DISPLAY
5.EXIT
enter ur choice : 2

element deleted - 67
do u want to cont...
************************* MENU ************************
1.PUSH
2.POP
3 IS EMPTY
4.DISPLAY
5.EXIT
enter ur choice : 4

 56
do u want to cont...

Queue

  • Linear Data Structures using C
  • Follows FIFO: First In First Out
  • Insertion can take place from the rear end.
  • Deletion can take place from the front end.
  • Eg: queue at ticket counters, bus station
  • 4 major operations:
    • enqueue(ele) – used to insert element at top
    • dequeue() – removes the top element from queue 
    • peekfirst() – to get the first element of the queue 
    • peeklast() – to get the last element of the queue 
  • All operation works in constant time i.e, O(1)

Advantages

  • Maintains data in FIFO manner
  • Insertion from beginning and deletion from end takes O(1) time

Applications

  • Scheduling
  • Maintaining playlist
  • Interrupt handling

Demonstration of Queue- using Array

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

struct que 
{ 
    int front, rear, size; 
    unsigned actualSize; 
    int* arr; 
}; 


struct que* createque(unsigned actualSize) 
{ 
    struct que* que = (struct que*) malloc(sizeof(struct que)); 
    que->actualSize = actualSize; 
    que->front = que->size = 0;  
    que->rear = actualSize - 1;
    que->arr = (int*) malloc(que->actualSize * sizeof(int)); 
    return que; 
} 

int isFull(struct que* que) 
{  return (que->size == que->actualSize);  } 
  

void enqueue(struct que* que, int item) 
{ 
    if (isFull(que)) 
        return; 
    que->rear = (que->rear + 1)%que->actualSize; 
    que->arr[que->rear] = item; 
    que->size = que->size + 1; 
    printf("%d enqueued to que\n", item); 
} 

int isEmpty(struct que* que) 
{  return (que->size == 0); } 
  
int dequeue(struct que* que) 
{ 
    if (isEmpty(que)) 
        return INT_MIN; 
    int item = que->arr[que->front]; 
    que->front = (que->front + 1)%que->actualSize; 
    que->size = que->size - 1; 
    return item; 
} 

int front(struct que* que) 
{ 
    if (isEmpty(que)) 
        return INT_MIN; 
    return que->arr[que->front]; 
} 

int rear(struct que* que) 
{ 
    if (isEmpty(que)) 
        return INT_MIN; 
    return que->arr[que->rear]; 
} 

int main()
{ 
  int val,n;
  struct que* que = createque(1000); 

  do
	{printf("\n************************* MENU ************************");
	 printf("\n1.ENQUEUE");
	 printf("\n2.DEQUEUE");
	 printf("\n3.IS EMPTY");
	 printf("\n4.IS FULL");
	 printf("\n5.FIRST ELE");
	 printf("\n6.LAST ELE");
	 printf("\n7.EXIT");
	 printf("\nenter ur choice : ");
	 scanf("%d",&n);
	 switch(n)
		{case 1: printf("\nenter the value ");
			 scanf("%d",&val);
			 enqueue(que,val);
			 break;
		 case 2:
			 dequeue(que);
			 break;
		 case 3: 
			 printf("\nIsEmpty : %d",isEmpty(que));
			 break;
		 case 4: 
			 printf("\nIsFull : %d",isFull(que));
		 	 break;

		 case 5: 
			 printf("\nFront element: %d",front(que));
			  break;	  
		 case 6: 
			 printf("\nLast element : %d",  rear(que));
			  break;
		case 7: exit(0);
		 		 break;
		 default: printf("\n Wrong Choice!");
		 		  break;
		}
	 printf("\ndo u want to cont... ");
	}while('y'==getch());

 }



Output:


************************* MENU ************************
1.ENQUEUE
2.DEQUEUE
3.IS EMPTY
4.IS FULL
5.FIRST ELE
6.LAST ELE
7.EXIT
enter ur choice : 1

enter the value 23
23 enqueued to que

do u want to cont...
************************* MENU ************************
1.ENQUEUE
2.DEQUEUE
3.IS EMPTY
4.IS FULL
5.FIRST ELE
6.LAST ELE
7.EXIT
enter ur choice :
1

enter the value 45
45 enqueued to que

do u want to cont...
************************* MENU ************************
1.ENQUEUE
2.DEQUEUE
3.IS EMPTY
4.IS FULL
5.FIRST ELE
6.LAST ELE
7.EXIT
enter ur choice : 3

IsEmpty : 0
do u want to cont...
************************* MENU ************************
1.ENQUEUE
2.DEQUEUE
3.IS EMPTY
4.IS FULL
5.FIRST ELE
6.LAST ELE
7.EXIT
enter ur choice :
4

IsFull : 0
do u want to cont...
************************* MENU ************************
1.ENQUEUE
2.DEQUEUE
3.IS EMPTY
4.IS FULL
5.FIRST ELE
6.LAST ELE
7.EXIT
enter ur choice : 5

Front element: 23
do u want to cont...
************************* MENU ************************
1.ENQUEUE
2.DEQUEUE
3.IS EMPTY
4.IS FULL
5.FIRST ELE
6.LAST ELE
7.EXIT
enter ur choice : 6

Last element : 45
do u want to cont...

Demonstration of Queue- using LinkedList

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct node
{int data;
 struct node *next;
}*p,*tmp,*tmp1;
void insert_end(int);
void delete_beg();
void display();
void isEmpty();
int main()
{ 
  int val,n;
  p=NULL;
  do
	{printf("\n************************* MENU ************************");
	 printf("\n1.ENQUEUE");
	 printf("\n2.DEQUE");
	 printf("\n3.IS EMPTY");
	 printf("\n4.DISPLAY");
	 printf("\n5.EXIT");
	 printf("\nenter ur choice : ");
	 scanf("%d",&n);
	 switch(n)
		{case 1: printf("\nenter the value ");
			 scanf("%d",&val);
			 insert_end(val);
			 break;
		 case 2:
			 delete_beg();
			 break;
		 case 3: 
			 isEmpty();
			 break;
		 case 4: display();
		 		 break;
		 case 5: exit(0);
		 		 break;
		 default: printf("\n Wrong Choice!");
		 		  break;
		}
	 printf("\ndo u want to cont... ");
	}while('y'==getch());

 }

 void insert_end(int ele)
 {
	  tmp=p;
	  tmp1=(struct node*)malloc(sizeof(struct node));
	  tmp1->data=ele;
	  tmp1->next=NULL;
	  if(p==NULL)
		p=tmp1;
	  else
		{
			while(tmp->next!=NULL)
				tmp=tmp->next;
		 	tmp->next=tmp1;
		 }
 }

void insert_beg(int ele)
{
	 tmp=p;
	 tmp1=(struct node*)malloc(sizeof(struct node));
	 tmp1->data=ele;
	 tmp1->next=p;
	 p=tmp1;
}

void isEmpty(){
	
 	if(p==NULL)
 		printf("Queue is Empty");
 	else
 	{
 		printf("Queue is Not Empty");
	 }	
}

void ldelete(int ele)
{
     tmp=p;
	 struct node *pre=tmp;
	 while(tmp!=NULL)
		{if(tmp->data==ele)
		    { if(tmp==p)
		       {p=tmp->next;
			free(tmp);
			return;
			}
		      else
			{pre->next=tmp->next;
			 free(tmp);
			 return;
			 }
		    }
		 else
		    { pre=tmp;
		      tmp=tmp->next;
		    }
		}
	  printf("\n no match found!! ");
 }
 
void delete_beg()
{	
	tmp=p;
	if(p==NULL)
		printf("\n no element to be deleted!! ");
	else
	{
		printf("\nelement deleted - %d", p->data);
		p=p->next;
	}

 }
 
void delete_end()
{	
	tmp=p;
	struct node* pre;
	if(p==NULL)
		printf("\n no element to be deleted!! ");
	else if(p->next==NULL)
	{
		printf("\nelement deleted - %d", p->data);
		p=NULL;

	}
		
	else
	{
		while(tmp->next!=NULL){
			pre=tmp;
			tmp=tmp->next;
		}
		pre->next=NULL;
		printf("\nelement deleted - %d", tmp->data);
		
	}

 }

void display()
{
	tmp=p;
 	while(tmp!=NULL)
		{printf("\n %d",tmp->data);
	 	tmp=tmp->next;
		}
}


Output
		
************************* MENU ************************
1.ENQUEUE
2.DEQUE
3.IS EMPTY
4.DISPLAY
5.EXIT
enter ur choice : 1

enter the value 45

do u want to cont...
************************* MENU ************************
1.ENQUEUE
2.DEQUE
3.IS EMPTY
4.DISPLAY
5.EXIT
enter ur choice :
1

enter the value 67

do u want to cont...
************************* MENU ************************
1.ENQUEUE
2.DEQUE
3.IS EMPTY
4.DISPLAY
5.EXIT
enter ur choice : 4

 45
 67
do u want to cont...
************************* MENU ************************
1.ENQUEUE
2.DEQUE
3.IS EMPTY
4.DISPLAY
5.EXIT
enter ur choice : 3
Queue is Not Empty
do u want to cont...
************************* MENU ************************
1.ENQUEUE
2.DEQUE
3.IS EMPTY
4.DISPLAY
5.EXIT
enter ur choice : 2

element deleted - 45
do u want to cont...
************************* MENU ************************
1.ENQUEUE
2.DEQUE
3.IS EMPTY
4.DISPLAY
5.EXIT
enter ur choice : 4

 67
do u want to cont...

Binary Tree

  • Hierarchical  Data Structures using C
  • Topmost element is known as the root of the tree
  • Every node can have at most 2 children in the binary tree
  • Can access elements randomly using index
  • Eg: File system hierarchy
  • Common traversal methods:
    • preorder(root) : print-left-right
    • postorder(root) : left-right-print 
    • inorder(root) : left-print-right

Advantages

  • Can represent data with some relationship
  • Insertion and search are much efficient

Disadvantages

  • Sorting is difficult
  • Not much flexible

Applications

  • File system hierarchy
  • Multiple variations of the binary tree have a wide variety of applications

Demonstration of Binary Tree

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

struct bst
 {
 	int data;
 	struct bst *left;
 	struct bst *right;
 };
 
 struct bst * insert(struct bst *,int);
 void inorder(struct bst *);
 void preorder(struct bst *);
 void postorder(struct bst *);
 
 int main ()
  {
  	struct bst *r=NULL;
  	  r=insert(r,30);
  	  r=insert(r,15);
  	  r=insert(r,10);
  	  r=insert(r,20);
  	  r=insert(r,40);
  	  r=insert(r,5);
  	  r=insert(r,45);
  	  r=insert(r,35);
  	  printf("\n display element in inorder:-");
  	  inorder(r);
  	  printf("\n display element in preorder:-");
  	  preorder(r);
  	  printf("\n display element in postorder:-");
  	  postorder(r);
  	 return 1;
  	 
   } 
   
   struct bst * insert(struct bst *q,int val)
    {
      struct bst *tmp;
      tmp=(struct bst *)malloc(sizeof(struct bst));
      
    	if(q==NULL)
    	 { 
    	 	 tmp->data=val;
    	 	 tmp->left=tmp->right=NULL;
    	 	 return tmp;
		 }
		 else
		  {
		  	 if(val<(tmp->data))
		  	   {
		  	   	  q->left=insert(q->left,val);
			   }
		  	 else
		  	  {
		  	  	 q->right=insert(q->right,val);
		      }
		  }
		 return q; 
	}
	
	
	 void inorder(struct bst *q)
	 {
	  	
	 	if(q==NULL)
	 	 {
	 	 	return;
	     }
	      
	 	   inorder(q->left);
	 	   printf(" %d ",q->data);
		   inorder(q->right);	
	 }
	
	
	void preorder(struct bst *q)
	 {
	  	
	 	if(q!=NULL)
	 	 {
		  printf(" %d ",q->data);
		  preorder(q->left);
		  preorder(q->right);
	     }
	     
	 }
	 
	 void postorder(struct bst *q)
	 {
	  	
	 	if(q!=NULL)
	 	 {
	 	   postorder(q->left);
		   postorder(q->right);	
		   printf(" %d ",q->data);
		  
		  
	     }
	     
	 }
	 
Output
	
 display element in inorder:- 35  45  5  40  20  10  15  30
 display element in preorder:- 30  15  10  20  40  5  45  35
 display element in postorder:- 35  45  5  40  20  10  15  30
--------------------------------
Process exited after 0.04906 seconds with return value 1
Press any key to continue . . .

Binary Search Tree

  • A binary tree with the additional restriction
  • Restriction:
    • The left child must always be less than the root node
    • The right child must always be greater than the root node
  • Insertion, Deletion, Search is much more efficient than a binary tree

Advantages

  • Maintains order in elements
  • Can easily find the min and max nodes in the tree
  • In order traversal gives sorted elements

Disadvantages

  • Random access not possible
  • Ordering adds complexity

Applications

  • Suitable for sorted hierarchical data

Demonstration of Binary Search Tree

#include<stdio.h>
#include<stdlib.h>
struct bst
{
       int data;
       struct bst *left;
       struct bst *right;
};

struct bst * insert(struct bst *q,int val)
{
     struct bst * temp;
     if(q==NULL)
     {
     temp=(struct bst *)malloc(sizeof(struct bst));
     temp->data=val;
     temp->left=NULL;
     temp->right=NULL;
     q=temp;
     }
     else
     {
         if(val<q->data)
         {
            q->left=insert(q->left,val);            
         }
         else
         {
            q->right=insert(q->right,val);
         }
     }
     return q;  
} 

  void   inorder(struct bst *q)
     {
                    
		 if(q==NULL)
          {                             
             return;
          }
         inorder(q->left);
         printf("%d\t" , q->data);
         inorder(q->right);
     }
	 
struct bst *search(struct bst *p, int key, struct bst **y)
{
  struct bst *temp;
     if( p == NULL)
       return(NULL);
     temp=p;
     *y = NULL;
      while( temp != NULL)
       {
         if(temp->data == key)
             return(temp);
         else
           {
             *y = temp; /*store this pointer as root */
             if(temp->data > key)
              temp = temp->left;
             else
              temp = temp->right;
           }
       }
      return(NULL);
}

/* A function to delete the node whose data value is given */
struct bst * del(struct bst *p,int val)
  {
    struct bst *x, *y, *temp;
    x = search(p,val,&y);
    if( x==NULL)
    {
      printf("The node does not exists\n");
      return(p);
    }
    else
    {
/* this code is for deleting root node*/
    if(x==p)
      {
        temp = x->left;
        y = x->right;
        p = temp;
        while(temp->right != NULL)
           temp = temp->right;
        temp->right=y;
        free(x);
        return(p);
      }
/* this code is for deleting node having both children */
  if( x->left!=NULL && x->right!=NULL)
     {

       if(y->left==x)
       {
         temp=x->left;
         y->left=x->left;
         while(temp->right != NULL)
            temp = temp->right;
         temp->right=x->right;
         x->left=NULL;
         x->right=NULL;
       }
       else
        {
          temp = x->right;
          y->right = x->right;
          while(temp->left!= NULL)
             temp = temp->left;
           temp->left=x->left;
           x->left=NULL;
           x->right=NULL;
         }

       free(x);
      return(p);
    }
/* this code is for deleting a node with one child*/
   if(x->left== NULL && x->right!= NULL)
     {
       if(y->left== x)
        y->left=x->right;
        else
        y->right= x->right;
          x->right= NULL;
          free(x);
          return(p);
     }
       
	if( x->left!= NULL && x->right== NULL)
      {
           if(y->left == x)
              y->left= x->left ;
           else
              y->right= x->left;
           x->left= NULL;
           free(x);
           return(p);
      }
/* this code is for deleting a node with no child*/
    if(x->left==NULL && x->right== NULL)
       {
           if(y->left== x)
              y->left= NULL ;
           else
              y->right= NULL;
           free(x);
           return(p);
        }
    }
}
	                 
                                     
   int main()
     {
         struct bst *root;
         root=NULL; int n,val,num;
         printf("\n enter no. of term:-  ");
         scanf("%d",&n);
         while(n!=0)
          {
          	printf("\n enter element:- ");
          	scanf("%d",&val);
            root=insert(root,val);
            n--;
          }
         printf("\n display element:-.......");
         inorder(root);
         printf("\n enter element to be deleted:-   ");
         scanf("%d",&num);
         del(root,num);
         printf("\n display element after deleted:-.......");
         inorder(root);
         return 1;
     
     }   
     
       
  Output:
  
 enter no. of term:- 5

 enter element:- 12

 enter element:- 34

 enter element:- 56

 enter element:- 10

 enter element:- 23

 display element:-.......10     12      23      34      56
 enter element to be deleted:-   23

 display element after deleted:-.......10       12      34      56

Heap

  • Binary Heap can be visualized array as a complete binary tree
  • Arr[0] element will be treated as root
  • length(A) – size of array
  • heapSize(A) – size of heap
  • Generally used when we are dealing with minimum and maximum elements
  • For ith node
(i-1)/2Parent
(2*i)+1Left child
(2*i)+2Right Child

Advantages

  • Can be of 2 types: min heap and max heap
  • Min heap keeps smallest and element and top and max keeps the largest 
  • O(1) for dealing with min or max elements

Disadvantages

  • Random access not possible
  • Only min or max element is available for accessibility

Applications

  • Suitable for applications dealing with priority
  • Scheduling algorithm
  • caching

Heap Examples

  Heap data structure program in C

#include <stdio.h>
int size = 0;
void swap(int *p, int *q)
{
  int temp = *q;
  *q = *p;
  *p = temp;
}
void heapify(int array[], int size, int i)
{
  if (size == 1)
  {
    printf("Single element in the heap");
  }
  else
  {
    int largest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;
    if (l < size && array[l] > array[largest])
      largest = l;
    if (r < size && array[r] > array[largest])
      largest = r;
    if (largest != i)
    {
      swap(&array[i], &array[largest]);
      heapify(array, size, largest);
    }
  }
}
void insert(int array[], int newNumber)
{
  if (size == 0)
  {
    array[0] = newNumber;
    size += 1;
  }
  else
  {
    array[size] = newNumber;
    size += 1;
    for (int i = size / 2 - 1; i >= 0; i--)
    {
      heapify(array, size, i);
    }
  }
}
void deleteRoot(int array[], int num)
{
  int i;
  for (i = 0; i < size; i++)
  {
    if (num == array[i])
      break;
  }

  swap(&array[i], &array[size - 1]);
  size -= 1;
  for (int i = size / 2 - 1; i >= 0; i--)
  {
    heapify(array, size, i);
  }
}
void printArray(int array[], int size)
{
  for (int i = 0; i < size; ++i)
    printf("%d ", array[i]);
  printf("\n");
}
int main()
{
  int array[10];

  insert(array, 4);
  insert(array, 2);
  insert(array, 8);
  insert(array, 1);
  insert(array, 3);
  insert(array, 6);
  printf("Max Heap array: ");
  printArray(array, size);

  deleteRoot(array, 4);

  printf("After deleting an element: ");

  printArray(array, size);
}

Input and Output:

Hashing

  • Uses special Hash function
  • A hash function maps element to an address for storage
  • This provides constant-time access
  • Collision is handled by collision resolution techniques
  • Collision resolution technique
    • Chaining
    • Open Addressing

Advantages

  • The hash function helps in fetching element in constant time
  • An efficient way to store elements

Disadvantages

  • Collision resolution increases complexity

Applications

  • Suitable for the application needs constant time fetching

Graph

  • Basically it is a group of edges and vertices
  • Graph representation
    • G(V, E): where V(G) represents a set of vertices and E(G) represents a set of edges
  • A graph can be directed or undirected
  • A graph can be connected or disjoint

Advantages

  • finding connectivity
  • Shortest path
  • min cost to reach from 1 pt to other
  • Min spanning tree

Disadvantages

  • Storing graph(Adjacency list and Adjacency matrix) can lead to complexities

Applications

  • Suitable for a circuit network
  • Suitable for applications like Facebook, LinkedIn, etc
  • Medical science

Graph Examples

Adjacency list representation in C

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

struct node {
  int vertex;
  struct node* next;
};
struct node* createNode(int);

struct Graph {
  int numVertices;
  struct node** adjacentLists;
};

struct node* createNode(int v) {
  struct node* newNode = malloc(sizeof(struct node));
  newNode->vertex = v;
  newNode->next = NULL;
  return newNode;
}

struct Graph* createAGraph(int vertices) {
  struct Graph* graph = malloc(sizeof(struct Graph));
  graph->numVertices = vertices;

  graph->adjacentLists = malloc(vertices * sizeof(struct node*));

  int i;
  for (i = 0; i < vertices; i++)
    graph->adjacentLists[i] = NULL;

  return graph;
}

void addEdge(struct Graph* graph, int a, int b) {
  struct node* newNode = createNode(b);
  newNode->next = graph->adjacentLists[a];
  graph->adjacentLists[a] = newNode;

  
  newNode = createNode(a);
  newNode->next = graph->adjacentLists[b];
  graph->adjacentLists[b] = newNode;
}

void printGraph(struct Graph* graph) {
  int v;
  for (v = 0; v < graph->numVertices; v++) {
    struct node* temp = graph->adjacentLists[v];
    printf("\n Vertex %d\n: ", v);
    while (temp) {
      printf("%d -> ", temp->vertex);
      temp = temp->next;
    }
    printf("\n");
  }
}

int main() {
  struct Graph* graph = createAGraph(4);
  addEdge(graph, 0, 1);
  addEdge(graph, 0, 3);
  addEdge(graph, 0, 2);
  addEdge(graph, 1, 3);

  printGraph(graph);

  return 0;
}

Input and Output:

We hope you enjoyed this tutorial about Data Structures using C!

Faizan Parvez
Faizan has been working as an Instructor of Data Structure and Algorithm for the last 1 year. He has expertise in languages such as Java, JavaScript, etc. He is a Subject Matter Expert in the field of Computer Science and a Competitive programmer. He has been working in technical content development and is a Research Analyst.
Recommended for you

Leave a Comment

Your email address will not be published. Required fields are marked *

Great Learning Free Online Courses
Scroll to Top