Data Structures in C are used to store data in an organised and efficient manner. The C Programming language has many data structures like an array, stack, queue, linked list, tree, etc. A programmer selects an appropriate data structure and uses it according to their convenience.
Let us look into some of these data structures:
ARRAY
An Array is a sequential collection of elements, of the same data type. They are stored sequentially in memory. An Array is a data structure that holds a similar type of elements. The array elements are not treated as objects in c like they are in java.
Imagine you are at a musical instrument store and I tell you to arrange all the keyboards under the brand Casio at one place one above the other. This sequential collection of records is called an Array. An array is a sequential collection of elements of the same data type. In our example above, Casio is the data type and all the keyboards you collected are of the brand Casio. All the elements in an array are addressed by a common name.
There are two types of arrays:
- Single dimensional array
- Multidimensional array
The syntax for one-dimensional Arrays:
data_type array_name[array_size];
//Employee IDs example
#include<stdio.h>
int main()
{
int i=0;
int empID[5];
empID[0]=10280;
empID[1]=10260;
empID[2]=10270;
empID[3]=10285;
for(i=0;i<4;i++)
{
printf("%d n,empID[i]);
}
return 0;
}//Output:
10280
10260
10270
10285
10275The syntax for two-dimensional Arrays:
data_type array_name[rows][columns];
#include<stdio.h>
int main()
{
int disp[2][3];
int i, j;
for(i=0; i<2; i++)
{
for(j=0;j<3;j++)
{
printf("Enter value for disp[%d][%d]:", i, j);
scanf("%d", &disp[i][j]);
}
}
printf("Two Dimensional array elements:n");
for(i=0; i<2; i++)
{
for(j=0;j<3;j++)
{
printf("%d ", disp[i][j]);
if(j==2)
{
printf("n");
}
}
}
return 0;
}//Output:
Enter value for disp[0][0]:1
Enter value for disp[0][1]:2
Enter value for disp[0][2]:3
Enter value for disp[1][0]:4
Enter value for disp[1][1]:5
Enter value for disp[1][2]:6
Two Dimensional array elements:
1 2 3
4 5 6 Let’s move on to the next topic.
STACK
A stack is a linear data structure. It follows the last in first out approach. A new item is added at the top of a stack. Both insert and deletion operation is performed from one end of the stack.
There are two functions associated with stacks. Push function to add elements to the stack and pop function to remove elements from the stack.
Consider the Example:
Imagine you have a cookie jar, and in this jar, you can add one cookie at the time. The process where you enter one cookie at a time inside the jar is called push. Similarly, you can remove one cookie at a time. This process of cookie removal from the topmost position is called a pop function.
The last entered cookie is the first to be removed from the jar, hence a stack follows a last in first out approach.
//Stack Example
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
struct Stack {
int top;
unsigned capacity;
int* array;
};
struct Stack* createStack(unsigned capacity)
{
struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
stack->capacity = capacity;
stack->top = -1;
stack->array = (int*)malloc(stack->capacity * sizeof(int));
return stack;
}
int isFull(struct Stack* stack)
{
return stack->top == stack->capacity - 1;
}
int isEmpty(struct Stack* stack)
{
return stack->top == -1;
}
void push(struct Stack* stack, int item)
{
if (isFull(stack))
return;
stack->array[++stack->top] = item;
printf("%d pushed to stackn", item);
}
int pop(struct Stack* stack)
{
if (isEmpty(stack))
return INT_MIN;
return stack->array[stack->top--];
}
int peek(struct Stack* stack)
{
if (isEmpty(stack))
return INT_MIN;
return stack->array[stack->top];
}
int main()
{
struct Stack* stack = createStack(100);
push(stack, 11);
push(stack, 12);
push(stack, 33);
printf("%d popped from stackn", pop(stack));
return 0;
}
//Output
11 pushed into stack
12 pushed into stack
33 pushed into stack
33 popped from stackSimilar to Stack, we have another data structure called Queue.
QUEUE
A Queue is a linear data structure that stores a collection of elements. The queue operates on first in first out (FIFO) algorithm.
Consider an example,
You are visiting a doctor for a check-up. There are many people at the clinic. A lady is entering the names of all the people in a file. The person who comes first gets places first. When the doctor is free, he calls the first patient inside. This is a queue and follows a first in first out method as the first person to enter his name in the list gets treated first.
The people who are treated their names are removed from the list. This is how a queue works.
There are 2 pointers, the front is at the front of the queue and rear is at the back of the queue. We add elements from the back of the queue and remove them from the front of the queue.
//Queue Example
#include<stdio.h>
#define SIZE 5
void enQueue(int);
void deQueue();
void display();
int items[SIZE], front = -1, rear = -1;
int main()
{
deQueue();
enQueue(1);
enQueue(2);
enQueue(3);
enQueue(4);
enQueue(5);
enQueue(6);
display();
deQueue();
display();
return 0;
}
void enQueue(int value)
{
if(rear == SIZE-1)
printf("nQueue is Full!!");
else
{
if(front == -1)
front = 0;
rear++;
items[rear] = value;
printf("nInserted -> %d", value);
}
}
void deQueue()
{
if(front == -1)
printf("nQueue is Empty!!");
else
{
printf("nDeleted : %d", items[front]);
front++;
if(front > rear)
front = rear = -1;
}
}
void display(){
if(rear == -1)
printf("nQueue is Empty!!!");
else
{
int i;
printf("nQueue elements are:n");
for(i=front; i<=rear; i++)
printf("%dt",items[i]);
}
}//Output:
Queue is Empty!!
Inserted -> 1
Inserted -> 2
Inserted -> 3
Inserted -> 4
Inserted -> 5
Queue is Full!!
Queue elements are:
1 2 3 4 5
Deleted : 1
Queue elements are:
2 3 4 5
LINKED LIST
A Linked List is a data structure. It is linear. The Linked List is like an array but, the Linked List is not stored sequentially in the memory. Every linked list has 2 parts, the data section and the address section that holds the address of the next element in the list, which is called a node.
The size of the linked list is not fixed, and data items can be added at any locations in the list. The disadvantage is that to get to a node, we must traverse to from the first node to the node that we require.
There are three types of link lists:
Singly link list
Doubly Link List
Circular link list
Example:
Format:[data,address]
Head->[3,1000]->[43,1001]->[21,1002]
In the example, the number 43 is present at location 1000 and the address is present at in the previous node. This is how a linked list is represented.
There are multiple functions in the linked list
First, we create a list, display it, insert at any location, delete a location. The following code will show you how to perform operations on the list.
//Example for Singly Linked List
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node *head = NULL;
struct node *current = NULL;
void printList()
{
struct node *ptr = head;
printf("n[head] =>");
while(ptr != NULL)
{
printf(" %d =>",ptr->data);
ptr = ptr->next;
}
printf(" [null]n");
}
void insert(int data)
{
struct node *link = (struct node*) malloc(sizeof(struct node));
link->data = data;
link->next = head;
head = link;
}
int main()
{
insert(600);
insert(500);
insert(400);
insert(300);
insert(200);
insert(100);
printList();
return 0;
}
//Output
[head] => 100 => 200 => 300 => 400 => 500 => 600 => [null]
//Example for Circular Linked List
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node *head = NULL;
struct node *current = NULL;
void insert(int data)
{
struct node *link = (struct node*) malloc(sizeof(struct node));
link->data = data;
link->next = NULL;
if(head==NULL)
{
head = link;
head->next = link;
return;
}
current = head;
while(current->next != head)
current = current->next;
current->next = link;
link->next = head;
}
void printList()
{
struct node *ptr = head;
printf("n[head] =>");
while(ptr->next != head)
{
printf(" %d =>",ptr->data);
ptr = ptr->next;
}
printf(" %d =>",ptr->data);
printf(" [head]n");
}
int main()
{
insert(10);
insert(20);
insert(30);
insert(40);
insert(50);
insert(60);
printList();
return 0;
}
//Output
[head] => 10 => 20 => 30 => 40 => 50 => 60 => [head]
//Example for Doubly Linked List
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node *prev;
struct node *next;
};
struct node *head = NULL;
struct node *last = NULL;
struct node *current = NULL;
void insert(int data)
{
struct node *link = (struct node*) malloc(sizeof(struct node));
link->data = data;
link->prev = NULL;
link->next = NULL;
if(head==NULL)
{
head = link;
return;
}
current = head;
while(current->next!=NULL)
current = current->next;
current->next = link;
last = link;
link->prev = current;
}
void printList()
{
struct node *ptr = head;
printf("n[head] <=>");
while(ptr->next != NULL)
{
printf(" %d <=>",ptr->data);
ptr = ptr->next;
}
printf(" %d <=>",ptr->data);
printf(" [head]n");
}
int main()
{
insert(10);
insert(20);
insert(30);
insert(40);
insert(50);
insert(60);
printList();
return 0;
}
//Output
[head] <=> 10 <=> 20 <=> 30 <=> 40 <=> 50 <=> 60 <=> [head]
Followed by Linked Lists, We shall Learn Trees.
TREES
A tree is a data structure that has one root node and many sub-nodes. It is another one of the data structures which are designed on top of a linked list.
Let’s understand the Hashing Algorithm.
HASHING
Hash table is another data structure. It is used to implement an associative array, a structure that can map keys to values. Hash table uses a hash function to compute an index into an array of buckets. Hash tables are very useful data structures.
More data structures exist, some user-defined some inbuilt that are used by the programmers to organize the data and use it efficiently.
With this, we come to an end of this article. I hope you have understood the importance of Data Structures, Syntax, functionality, and operations performed using them.
Now that you have understood the basics of Data Structures in C, check out the training provided by Edureka on many technologies like Java, Spring and many more, a trusted online learning company with a network of more than 250,000 satisfied learners spread across the globe
Got a question for us? Mention it in the comments section of this “Data Structures in C” blog and we will get back to you as soon as possible.