Introduction to Data Structures TUTORIAL

A data structure is an arrangement of data in a computer's memory or even disk storage. It has a different way of storing and organizing data in a computer so that it can used efficiently. Different kind of Data structure is used in different application. For example, B-tree is widely used in implementation of databases.

Data Structure in C

A memory play a vital role in c because all variable you declare are at first stored in the memory. Some memory allocation is done at compile time and some at runtime. Memory which is allocated and de-allocated during the execution of the program is known as dynamic memory. Memory span and shrink as per application requirement and this is one of major advantage of pointer.

A memory can be categories in following segments

Text Segment

Data Segment

Free Space

Stack Segment

 Data Segment in sub-categories in two parts

Static Segment

Heap Segment

The Static Segment hold the global variables and the Heap Segment hold the dynamic variable. Dynamic memory allocation is done by using malloc() funtion in C.

In this tutorial you will learn about Pointer, Linked List, Stacks, Queues, Trees, and Graphs which are related with the data structures.

Pointer in C

Know what is data structure, dynamic memory allocation. Now in this tutorial you will see the how we declare a pointer variable. How it works with a very simple example.

Pointer and Structure in C

Structures in C defines the group of contiguous (adjacent) fields, such as records or control blocks. A structure is a collection of variables grouped together under a single name. It provides an elegant and powerful way for keeping related data together.

Linear and Non-Linear Data Structure in C

Know the difference between Linear and Non-Linear Data Structure in C.

Array Implementation in C

Learn how to implement an array in C. There are two function in this given example one for reading the array element and other for writing on console.

Sum of array element in C

Know how to get the sum of each element of an array. There are two function in this given example one for reading the array element and other for writing on console.

Addition of two arrays element in C

Know how to get the sum of each element of an array. There are three function in this given example one for reading the array element, second for writing on console and last for addition of both array's element.

Inverse of an array in C

Know how to inverse an array in c language. There are three function in this given example one for reading the array element, second for writing on console and last for inverse of an array.

Merge of two arrays in C

Know how to merge two array in c language. There are four function in this given example one for reading the array element, second for writing on console and third for sorting of both array and last for merge of two array into one.

Overview of Linked List

Know what is linked list and what are its types.

Singly Linked List

Demonstrate the implementation of singly linked list.

Doubly Linked List

Demonstrate how to implement doubly linked list.

Circular Linked List

Demonstrate how to implement circular linked list.

Count number of nodes

Demonstrate how to count the number of nodes present in the linked list.

Split a list into two equal size list

Demonstrate how to splits the list into two equal size list having same data inside.

Merge two list into a single list

Demonstrate the merging of two link list into one single.

Stack

The stack is one of the most important data structures in computer science. A stack is a last-in first-out data structure (LIFO).

Push and Pop operation of stack.

Demonstrate the push and pop operation of stack using array.

Push and Pop operation of stack using linked list.

The fundamental operation of stack is push and pop. The term push is use to place some data element into the stack and pop is use to remove some data element from the stack.

Queue implementation using array.

Demonstrate how to insert and delete element in the queue using array.

Queue implementation using linked list.

Demonstrate how to implement queue using linked list.

Circular queue implementation using array.

Demonstrate the circular queue implementation using array in c language.

Tree data structure

Define tree data structure and display how to make a tree.

Representing Graph using adjacency list & perform DFS & BFS

A graph is a collection of nodes and edges.

NEXT

Pointer in C

Representing Graph using adjacency list & perform DFS & BFS - DS TUTORIAL

A graph is a collection of nodes and edges.

Description:

This tutorial demonstrate how to create a graph using adjacency list and perform DFS and BFS.
Different kind of graph are listed below:

Directed Graph: A directed graph is one in which edges connect nodes in only one direction(unidirectional).

Undirected Graph: An undirected graph is one in which edges connect nodes bidirectionally (in both directions). Node: A node, usually drawn as a circle, represents an item that can be related to other items or nodes. Nodes are sometimes referred to as vertices.

Edge: An edge represents a connection between nodes. Edges can be either directed or undirected, depending on the type of graph. Edges can also have weights, which may corresponds distance between edges.

Connected: A graph is said to be connected if from any node you can reach any other node.

Disconnected: A graph is said to be disconnected if certain groups of nodes from an island that has no connection to the rest of the graph.

Code:

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

 #define max 10

 struct node
 {
   int vertex;
   struct node *next;
 };
 typedef struct node* nodeptr;
 typedef struct queue
 {
  int front,rear;
  int arr[max];
 };
 typedef struct stack
 {
  int top;
  int arr[max];
 };
 nodeptr getnode()
 {
  nodeptr p;
  p=(nodeptr)malloc(sizeof(struct node));
  p->next=NULL;
  return p;
 }

  int empty(struct stack *s)
  {
   if(s->top==-1)
   {
   return 1;
   }
   else
   return 0;
  }
  void push(struct stack *s,int x)
  {
  if(s->top==max-1)
  printf("\n Queue Overflow");
  else
  {
 s->top++;
 s->arr[s->top]=x;
  }
  }
  int pop(struct stack *s)
  {
  int x;
  if(empty(s))
   printf("\n Queue Overflow..!");
  else
  {
   x=s->arr[s->top];
   s->top--;
  }
  return x;
  }

  int qempty(struct queue *q)
  {
  if(q->front > q->rear)
  return 1;
  else
  return 0;
  }
  void insertq(struct queue *q,int x)
  {
  if(q->rear==max-1)
   printf("\n Queue Overflow..1");
  else
  {
  q->rear++;
  q->arr[q->rear]=x;
  }
  }
  int removeq(struct queue *q)
  {
   int x;
   if(qempty(q))
 printf("\n Queue Overflow..!");
   else
   {
   x=q->arr[q->front];
   q->front++;
   }
   return x;
  }

  void init(nodeptr head[],int n)
  {
  int v;
  for(v=1;v<=n;v++)
  head[v]=NULL;
  }
  void initialise_visit(int visited[],int n)
  {
  int i;
  for(i=1;i<=n;i++)
   visited[i]=0;
  }

    void create(nodeptr head[])
  {
  nodeptr adj;
  char ch='y';
  int i,v1,v2,v,c;
  nodeptr new1,p;
  printf("\n <0>Directed");
  printf("\n <1>UnDirected");
  printf("\n Enter Your Choice:\t");
  scanf("%d",&c);

  do
  {
  printf("\n Enter The Edge Between Two Vertices:\t");
  scanf("%d%d",&v1,&v2);
  new1=getnode();
  new1->vertex=v2;
  p=head[v1];
  if(p==NULL)
  head[v1]=new1;
  else
  {
  while(p->next!=NULL)
   p=p->next;
   p->next=new1;
  }
  if(c==1)  
  {
 new1=getnode();
 new1->vertex=v1;
 p=head[v2];
 if(p==NULL)
  head[v2]=new1;
 else
 {
   while(p->next!=NULL)
    p=p->next;
    p->next=new1;
 }
  }
  printf("\n Do You Want To Add More Edges In Graph(y/n):\t");
  ch=getche();
  }while(ch=='y'||ch=='Y');
  }

  void display(nodeptr head[],int n)
  {
  int v;
  nodeptr adj;
  printf("\n Adjancency List Is:\n");
  for(v=1;v<=n;v++)
  {
   printf("\n Head[%d]->",v);
   adj=head[v];
   while(adj!=NULL)
   {
  printf("%d  ",adj->vertex);
  adj=adj->next;
   }
   printf("\n");
  }
  }

  void DFSR(nodeptr head[],int start,int visited[])
  {
  nodeptr adj;
  visited[start]=1;
  printf("\t %d",start);
  adj=head[start];
  while(adj!=NULL)
  {
   if(visited[adj->vertex]==0)
   {
  DFSR(head,adj->vertex,visited);
   }
   adj=adj->next;
  }
  }

  void DFSN(nodeptr head[],int start,int visited[])
  {
  nodeptr adj;
  struct stack s;
  int v;
  s.top=-1;
  push(&s,99);
  visited[start]=1;
  printf("\n %d",start);
  push(&s,start);
  do
  {
   adj=head[start];
   while(adj!=NULL)
   {
   if(visited[adj->vertex]==0)
   {
  visited[adj->vertex]=1;
  printf("\t%d",adj->vertex);
  push(&s,adj->vertex);
  start=adj->vertex;
  break;
   }
   else
  adj=adj->next;
   }
   if(adj==NULL)
   {
   start=pop(&s);
   }

  }while(!empty(&s));

  }
  void BFS(nodeptr head[],int start,int visited[])
  {
  nodeptr adj;
  struct queue q;
  int v;
  q.front=0;
  q.rear=-1;
  visited[start]=1;
  printf("\n %d",start);
  insertq(&q,start);
  while(!qempty(&q))
  {
  v=removeq(&q);
  adj=head[v];
  while(adj!=NULL)
  {
 if(visited[adj->vertex]==0)
 {
   visited[adj->vertex]=1;
   printf("\t %d",adj->vertex);
 }
 adj=adj->next;
  }
  }
  }
  void main()
  {
  char c='y';
  int ch,start,n,visited[10];
  nodeptr head[10];
  clrscr();
  do
  {
 clrscr();
 printf("\n========Graph========");
 printf("\n 1. Create");
 printf("\n 2. Display Adjancency List");
 printf("\n 3. Depth First Search(Rec)");
 printf("\n 4. Depth First Search(Non-Rec)");
 printf("\n 5. Breadth First Search");
 printf("\n 6. Exit");
 printf("\n=====================");
 printf("\n Enter Your Choice:\t");
 scanf("%d",&ch);
 switch(ch)
 {
 case 1:
 printf("\n Enter The No. of Vertices In Graph:\t");
 scanf("%d",&n);
 init(head,n);
 create(head);
 break;

 case 2:
 display(head,n);
 break;

 case 3:
 printf("\n Enter The Vertex From Which You Want To Start Traversal");
 scanf("%d",&start);
 initialise_visit(visited,n);
 printf("\n Recursive Depth First Search Is\n");
 DFSR(head,start,visited);
 break;

 case 4:
 printf("\n Enter The Vertex From Which You Want To Start Traversal");
 scanf("%d",&start);
 initialise_visit(visited,n);
 printf("\n Non-Recursive Depth First Search Is\n");
 DFSN(head,start,visited);
 break;

 case 5:
 printf("\n Enter The Vertex From Which You Want To Start Traversal");
 scanf("%d",&start);
 initialise_visit(visited,n);
 BFS(head,start,visited);
 break;

 case 6:
 break;
 }
 printf("\n Do You Want To Continue(y/n):\t");
 c=getche();
 }while(c=='Y'||c=='y');
  getch();
  }

Output:

Circular queue implementation using array - DS TUTORIAL

demonstrate the circular queue implementation using array in c language.

Code:

#include <stdio.h>
#define MAX 5
#include <stdlib.h>

void insert(int queue[], int *rear, int front, int value)
{
  *rear= (*rear +1) % MAX;
  if(*rear == front)
  {
 printf("The queue is full\n");
 exit(0);
  }
 queue[*rear] = value;
}

void deleteQ(int queue[], int *front, int rear, int * value)
{
 if(*front == rear)
 {
  printf("The queue is empty\n");
         exit(0);
        }
        *front = (*front + 1) % MAX;
        *value = queue[*front];
}

void main()
{
        int queue[MAX];
        int front,rear;
        int n,value;
        front=0; rear=0;
      do
      {

        do
        {
          printf("Enter the element to be inserted\n");
          scanf("%d",&value);
          insert(queue,&rear,front,value);
          printf("Enter 1 to continue\n");
          scanf("%d",&n);
        } while(n == 1);
        
        printf("Enter 1 to delete an element\n");
        scanf("%d",&n);
          while( n == 1)
          {
   deleteQ(queue,&front,rear,&value);
          printf("The value deleted is %d\n",value);
          printf("Enter 1 to delete an element\n");
          scanf("%d",&n);
          }
        printf("Enter 1 to continue\n");
        scanf("%d",&n);
      } while(n == 1);
 }

Output:

Tree data structure - DS TUTORIAL

define tree data structure and display how to make a tree.

Description:

A tree data structure that are based on hierarchical tree structure with sets of nodes. A tree is a acyclic connected graph with zero or more children nodes and at most one parent nodes.

Code:

#include <stdio.h>
#include <stdlib.h>
struct node
{
  int data;
  struct node *lchild, *rchild;
};

struct node *insertN(struct node *p,int val)
{
   struct node *temp1,*temp2;
 if(p == NULL)
 {
  p = (struct node *) malloc(sizeof(struct node));
  if(p == NULL)
    {
 printf("Cannot allocate memory\n");
 exit(0);
        }
   p->data = val;
   p->lchild=p->rchild=NULL;
 }
else
{
 temp1 = p;

while(temp1 != NULL)
{
  temp2 = temp1;
  if( temp1 ->data > val)
   temp1 = temp1->lchild;
  else
   temp1 = temp1->rchild;
}
if( temp2->data > val)
{
temp2->lchild = (struct node*)malloc(sizeof(struct node));
 temp2 = temp2->lchild;
   if(temp2 == NULL)
        {
 printf("Cannot allocate memory\n");
 exit(0);
        }
   temp2->data = val;
   temp2->lchild=temp2->rchild = NULL;
}
else
{
 temp2->rchild = (struct node*)malloc(sizeof(struct node));
 temp2 = temp2->rchild;
 if(temp2 == NULL)
        {
 printf("Cannot allocate memory\n");
 exit(0);
        }
 temp2->data = val;
 temp2->lchild=temp2->rchild = NULL;
}
}
return(p);
}

void display(struct node *p)
    {
   if(p != NULL)
         {
     display(p->lchild);
     printf("%d\t",p->data);
     display(p->rchild);
          }
  }
void main()
{
  struct node *root = NULL;
  int n,x;
  printf("Enter the number of nodes for tree\n");
  scanf("%d",&n);
  while( n -- > 0)
    {
   printf("Enter the data value\n");
   scanf("%d",&x);
   root = insertN(root,x);
   }
  display(root);
  }

Output:

Queue implementation using linked list - DS TUTORIAL

demonstrate how to implement queue using linked list.

Description:

The advantage of using linked list is that there is no size limit. The size of queue grow and shrink as per insertion and deletion takes place.

Code:

# include <stdio.h>
# include <stdlib.h>
struct node
{
int data;
struct node *link;
};
void insert(struct node **front, struct node **rear , int value)
{
struct node *temp;
temp=(struct node *)malloc(sizeof(struct node));
 if(temp==NULL)
 {
 printf("No Memory available\n");
 exit(0);
 }
 temp->data = value;
 temp->link=NULL;
 if(*rear == NULL)
 {
 *rear = temp;
 *front = *rear;
 }
 else
 {
 (*rear)->link = temp;
 *rear = temp;
 }
 }

void deleteQ(struct node **front, struct node **rear , int *value)
{
struct node *temp;
if((*front == *rear)  && (*rear == NULL))
{
printf(" The queue is empty can not delete Error\n");
exit(0);
}
 *value = (*front)->data;
 temp = *front;
 *front = (*front)->link;
 if(*rear == temp)
 *rear = (*rear)->link;
 free(temp);
 }

void main()
{
struct node *front=NULL,*rear = NULL;
int n,value;
do
{
  do
  {
   printf("Enter the element to be inserted\n");
   scanf("%d",&value);
   insert(&front,&rear,value);
   printf("Enter 1 to continue\n");
   scanf("%d",&n);
  } while(n == 1);
  printf("Enter 1 to delete an element\n");
  scanf("%d",&n);
  while( n == 1)
 {
  deleteQ(&front,&rear,&value);
  printf("The value deleted is %d\n",value);
  printf("Enter 1 to delete an element\n");
  scanf("%d",&n);
 }
   printf("Enter 1 to continue\n");
   scanf("%d",&n);
 } while(n == 1);
}

Output

Queue implementation using array - DS TUTORIAL

how to insert and delete element in the queue using array.

Description:

In this tutorial you will see how to implement queue using array and queue insert & delete operations.

Code:

#include <stdio.h>
#define MAX 5
#include <stdlib.h>

void insert(int queue[], int *rear, int value)
{
 if(*rear < MAX-1)
  {
  *rear= *rear +1;
  queue[*rear] = value;
  }
  else
  {
   printf("The queue is full \n");
   exit(1);
  }
}

void deleteQ(int queue[], int *front, int rear, int *value)
{
 if(*front == rear)
 {
 printf("The queue is empty \n");
 exit(1);
 }
        *front = *front + 1;
 *value = queue[*front];
}

void main()
{
  int queue[MAX];
  int front,rear;
  int n,value;
  front=rear=(-1);
  do
 {
        do
   {
         printf("Enter the element to be inserted in queue\n");
  scanf("%d",&value);
  insert(queue,&rear,value);
  printf("Enter 1 to continue\n");
  scanf("%d",&n);
  } while(n == 1);
  printf("Enter 1 to delete an element from queue\n");
  scanf("%d",&n);
   while( n == 1)
  {
 deleteQ(queue,&front,rear,&value);
 printf("The value deleted is %d\n",value);
 printf("Enter 1 to delete an element from queue\n");
 scanf("%d",&n);
 }
  printf("Enter 1 to continue\n");
  scanf("%d",&n);
 } while(n == 1);
}

Output:

Push and Pop operation of stack - DS TUTORIAL

demonstrate the push and pop operation of stack using array.

Description:

In this tutorial of data-structure you will see push and pop operation of stack. In the previous tutorial is clearly explained the push pop operation. The drawback of implementing stack is that the size of stack is fixed it cannot grow or shrink.

Code:

#include <stdio.h>
#include <stdlib.h>
void push(int stack[], int *top, int value)
{
 if(*top < 4 )
  {
 *top = *top + 1;
 stack[*top] = value;
 printf("\nStack element should be less than four\n");
 }
 else
 {
 printf("\nThe stack is full can not push a  value\n");
 exit(0);
 }
}
void pop(int stack[], int *top, int * value)
{
 if(*top >= 0 )
 {
  *value = stack[*top];
  *top = *top - 1;
 }
 else
 {
 printf("\nThe stack is empty can not pop a  value\n");
 exit(0);
 }
}
 void main()
 {
 int stack[4];
 int top = 0;
 int n,value;
 do
 {
   do
   {
  printf("\nEnter the element to be pushed\n");
  scanf("%d",&value);
  push(stack,&top,value);
  printf("\nEnter 1 to continue and other key to pop\n");
  scanf("%d",&n);
  printf("");
   }    while(n == 1);
    printf("\nEnter 1 to pop an element\n");
    scanf("%d",&n);
    while( n == 1)
   {
   pop(stack,&top,&value);
   printf("\nThe value poped is %d",value);
   printf("\nEnter 1 to pop an element\n");
   scanf("%d",&n);
   }
   printf("\nEnter 1 to continue and other key to push\n");
   scanf("%d",&n);
 } while(n == 1);
}

Output:

Push and Pop operation of stack using linked list - DS TUTORIAL

The fundamental operation of stack is push and pop. The term push is use to place some data element into the stack and pop is use to remove some data element from the stack.

Description:

In this tutorial of data-structure you will see push and pop operation of stack using linked list. In the previous tutorial the stack operation in done using array.

Code:

# include <stdio.h>
# include <stdlib.h>
struct node
{
int data;
struct node *link;
};
struct node *push(struct node *p , int value)
{
 struct node *temp;
 temp=(struct node *)malloc(sizeof(struct node));
 if(temp==NULL)
 {
  printf("No Memory available\n");
  exit(0);
 }
  temp->data = value;
  temp->link = p;
  p = temp;
  return(p);
 }

struct node *pop(struct node *p , int *value)
{
 struct node *temp;
 if(p==NULL)
 {
 printf(" The stack is empty and cannot pop element\n");
        exit(0);
 }
  *value = p->data;
 temp = p;
 p = p->link;
 free(temp);
 return(p);
 }

void main()
{
struct node *top = NULL;
int n,value;
do
{
  do
  {
 printf("Enter the element to be pushed in stack\n");
 scanf("%d",&value);
 top = push(top,value);
 printf("Enter 1 to continue\n");
 scanf("%d",&n);
 } while(n == 1);

  printf("Enter 1 to pop an element from stack\n");
  scanf("%d",&n);
  while( n == 1)
 {
 top = pop(top,&value);
 printf("The value poped is %d\n",value);
 printf("Enter 1 to pop an element and other to push\n");
 scanf("%d",&n);
 }
  printf("Enter 1 to continue\n");
  scanf("%d",&n);
} while(n == 1);
}

Output: