In the programming world, there are certain types of containers that are used to store data. These containers are nothing but data structures. These containers have different properties associated with them, which are used to store, organize, and manipulate the data stored in them.
In this article, we will be going to introduce you to the different types of data structures in C along with their implementation.
Types of Data Structures in C
The data structures in C can be classified into two categories:
-
Primitive Data Structures
The primitive data structures in C are those basic data structures that are already defined in the C language. These data structures can be used to store only a single value. They are the foundation of data manipulation. The primitive data structures in C (also known as primitive data types) include int, char, float, double, and pointers.
-
Non-Primitive Data Structures
The non-primitive data structures in C are also known as the derived data structures as they are derived from primitive ones. A large number of values can be stored using the non-primitive data structures. The data stored can also be manipulated using various operations like insertion, deletion, searching, sorting, etc. The data structures like arrays, trees, stacks, and many more come under this category.
The non-primitive data structures in C can further be divided into two categories:
1. Linear Data Structures
Linear data structures in C store the data in a sequential or linear fashion. The memory location of each element stored can be accessed sequentially. The elements may not be present adjacently in the memory, however, each element is attached to the next element in some way. Example - arrays, linked lists, stacks, etc.
2. Non-Linear Data Structures
Non-linear data structures in C store the data in a non-sequential manner. The data is stored in multiple levels. The implementation of non-linear data structures is more complex than linear data structures. Example - graphs, trees.
On the basis of size, the data structures in C can also be classified as:
-
Static Data Structures
The static nature of data structures is exhibited in the memory allocated to them. The size of such data structures is fixed as the memory is allocated to them during the compile time. However, the values of the elements stored are not static and can be modified at any time. Example - Array.
-
Dynamic Data Structures
The dynamic data structures in C are capable of resizing themselves during the run time of the program. The memory space allocated to such data structures can be modified (increased or decreased), thus providing more flexibility to manipulate the data stored in them. Example - Linked List.
Array Data Structure in C
The array data structure in C is a linear data structure that can be described as a group of multiple entities of similar type into a larger group. These entities or elements can be of int, float, char, or double data type or can be of user-defined data types too like structures. The array is one of the most used data structures in C as it has many practical as well as real-life significance.
Let us take a real-life example. Let’s say you want to print 1-100 digits. Now, to store them, you can do two things. The first one is to make 100 variables and store the numbers from 1-100 in those variables separately. The second method is to create an array of size 100 and store the numbers in that array in O(1) time. It is clear that the second method is more optimized and practical than the first one as it is more convenient to store these values in a single array rather than creating 100 variables.
Single dimensional array or 1-D array is the most common and most used form of arrays that can be found in C. 1-D array consists of elements of similar types and these elements can be accessed through their indices.
Also Read: Arrays in Data Structure: A Guide With Examples
// declaring a 1-D array
dataType arrayName [size];
The following example illustrates the array data structure in C.
#include <stdio.h>
int main()
{
int i;
// initialize an array.
int my_array[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
// input index where the element is to be inserted.
int pos;
printf("Enter the position: ");
scanf("%d", &pos);
// input the element to be inserted.
int element;
printf("Enter the element: ");
scanf("%d", &element);
if (pos > 10)
{
printf("Input is invalid !");
}
else
{
// right shifting array elements.
for (i = 9; i >= pos - 1; i--)
my_array[i + 1] = my_array[i];
// insert the element at "pos".
my_array[pos - 1] = element;
printf("Array after insertion is:\n");
// print array elements.
for (i = 0; i <= 10; i++)
printf("% d ", my_array[i]);
}
return 0;
}
Also Read: What is C Programming?
Stack Data Structure in C
A stack is a data structure that stores the elements in a linear or a sequential manner. The last inserted element in the stack is the one to be removed first. This is also called the last in first out (LIFO) approach. To keep a track of the element inserted in the last, its index is named as the top. This top is updated as soon as a new value is inserted in the stack.
Also Read: Stack Implementation Using Array in Data Structures
Syntax
struct stack
{
int myStack[capacity];
int top;
};
Basic Stack Operations
The following are basic operations that are performed to manipulate the data stored in a stack.
- Push (Insertion): The push operation inserts a new element at the top of the stack. The top is updated and points to the newly added element.
- Pop (Deletion): The pop operation deletes the element present at the top of the stack. The deleted element is returned by the pop() function.
- isEmpty: This operation checks if the stack is empty or not. The value of the top is generally -1 in the case of an empty stack.
- Peek: The peek operation simply returns the element present at the top of the stack.
Stack Implementation Using Arrays
The following program implements a stack using the arrays.
#include <stdio.h>
#include <stdlib.h>
#define capacity 15
int count = 0;
// Stack definition using a structure.
struct STACK
{
int myStack[capacity];
int top;
};
// function to create a stack.
void buildStack(struct STACK *stack)
{
stack->top = -1;
}
// function to check if the stack is full or not.
// stack full -> overflow condition.
int isStackFull(struct STACK *stack)
{
if (stack->top == capacity - 1)
return 1;
else
return 0;
}
// function to check if the stack is empty or not.
// stack empty -> underflow condition.
int isEmpty(struct STACK *stack)
{
if (stack->top == -1)
return 1;
else
return 0;
}
// function to perform the push operation in the stack.
void push(struct STACK *stack, int dataValue)
{
if (isStackFull(stack))
{
printf("Overflow! The stack is full.");
}
else
{
stack->top++;
stack->myStack[stack->top] = dataValue;
}
count++;
}
// function to perform the pop operation in the stack
// and return the deleted value.
void pop(struct STACK *stack)
{
if (isEmpty(stack))
{
printf("\nUnderflow! The stack is empty. \n");
}
else
{
printf("The deleted value is: %d\n", stack->myStack[stack->top]);
stack->top--;
}
count--;
}
// function to print the elements of the stack.
void printValues(struct STACK *stack)
{
printf("The elements of the stack are:\n");
for (int i = 0; i < count; i++)
{
printf("%d \n", stack->myStack[i]);
}
}
int main()
{
struct STACK *stack = (struct STACK *)malloc(sizeof(struct STACK));
// create a stack.
buildStack(stack);
// insert data values into the stack.
push(stack, 10);
push(stack, 20);
push(stack, 30);
push(stack, 40);
// print the stack elements.
printValues(stack);
// delete an item at the top.
pop(stack);
// print the stack elements after performing the pop operation.
printf("\nThe stack elements after the pop operation: \n");
printValues(stack);
printf("\n\n");
}
Queue Data Structure in C
A queue is another data structure that stores the elements in a linear or a sequential manner. The first inserted element in the queue is the one to be removed first. This is also called the first in first out (FIFO) rule. Since the elements are inserted at one end and removed from the other end, a track of the first and last indices has to be kept. These are called the front and rear of the queue.
There are many examples in real life that resemble the queue data structure in C. Imagine a queue of people waiting to visit the dentist. The patients will be served on a first come first serve basis. The queue in C is implemented in the same way.
Syntax
struct Queue {
int myQueue[capacity];
int front, rear;
};
Basic Queue Operations
The following are basic operations that are performed to manipulate the data stored in a queue.
- Enqueue: This operation inserts a new element at the end of the queue. The rear pointer is updated when a new element is inserted into the queue.
- Dequeue: This operation removes an existing element present at the front of the queue. The front pointer is updated when an element is removed from the queue.
- isEmpty: The isEmpty operation is to check if the current queue is empty or not.
- isFull: This function is used to determine whether the queue has reached its capacity or not.
- Peek: This operation simply returns the element present at the front of the queue.
Queue Implementation Using Arrays.
The following program implements a queue using the arrays.
#include <stdio.h>
#include <limits.h>
#include <stdlib.h>
#define capacity 15
// queue definition using a structure.
struct QUEUE
{
int front, rear, size;
//int capacity;
int myQueue[capacity];
};
// function to create a queue.
void buildQueue(struct QUEUE *queue)
{
queue->front = -1;
queue->rear = -1;
}
// function to check if the queue is full or not.
int isFull(struct QUEUE *queue)
{
if (queue->front == 0 && queue->rear == capacity - 1)
return 1;
else
return 0;
}
// function to check if the queue is empty or not.
int isEmpty(struct QUEUE *queue)
{
if (queue->front == -1)
return 1;
else
return 0;
}
// function to perform the enqueue operation in the queue.
void enqueue(struct QUEUE *queue, int item)
{
if (isFull(queue))
return;
else
{
if (queue->front == -1)
queue->front = 0;
queue->rear++;
queue->myQueue[queue->rear] = item;
}
}
// function to perform the dequeue operation in the queue
// and return the deleted value.
void dequeue(struct QUEUE *queue)
{
if (isEmpty(queue))
{
printf("The queue is empty.\n");
return;
}
else
{
int deletedValue = queue->myQueue[queue->front];
if (queue->front >= queue->rear)
{
queue->front = -1;
queue->rear = -1;
}
else
{
queue->front++;
}
printf("The deleted value is: %d\n", deletedValue);
}
}
void printValues(struct QUEUE *queue)
{
printf("The elements of the queue are:\n");
for (int i = queue->front; i <= queue->rear; i++)
{
printf("%d \n", queue->myQueue[i]);
}
}
int main()
{
struct QUEUE *queue = (struct QUEUE *)malloc(sizeof(struct QUEUE));
// create a queue.
buildQueue(queue);
enqueue(queue, 100);
enqueue(queue, 200);
enqueue(queue, 300);
enqueue(queue, 400);
// print the queue elements.
printValues(queue);
// delete an item from the queue.
dequeue(queue);
// print the queue elements after performing the dequeue operation.
printf("\nThe queue elements after the queue operation: \n");
printValues(queue);
printf("\n\n");
}
Linked List Data Structure in C
The fourth and last linear data structure in this article is the linked list. Unlike arrays, elements of a linked list are stored non-contiguously. They can be stored anywhere in the memory and are not connected adjacently. We have to use a pointer to link the elements together.
A linked list is headed by the pointer to the first node that is known as the head node. The head node or head does not contain any value but it stores the address of the first element of the list.
Also Read: Top 7 Practical Applications of C++ and the Way to Build a Career in the Field
The head will be NULL if the linked list is empty.
A node of a linked list consists of two parts:
- Data: Data is the value represented by the node. For example 1, 2, 0, and so on.
- Pointer to the next node: This part of the node contains the address of the next node.
Syntax
// A linked list node
struct Node {
int data; // data of the node
struct Node* next;
};
Singly Linked List
The usual linked list is also known as the singly linked list. Everything that we have discussed so far about a linked list is applicable for a singly linked list. Like the node has two parts, data and the pointer where the pointer holds the address of the next element and so on. The following example illustrates the singly linked list in C.
#include <stdio.h>
#include <stdlib.h>
struct Node
{
int data;
struct Node *next;
};
// function to print the values
// stored in the nodes of the linked list.
void print(struct Node *n)
{
while (n != NULL)
{
printf(" %d ", n->data);
n = n->next;
}
}
int main()
{
struct Node *head = NULL;
struct Node *second = NULL;
struct Node *third = NULL;
// allocate 3 nodes in the memory.
head = (struct Node *)malloc(sizeof(struct Node));
second = (struct Node *)malloc(sizeof(struct Node));
third = (struct Node *)malloc(sizeof(struct Node));
head->data = 1; // assign data in the first node
head->next = second; // store the address of the second node
second->data = 2; // assign data to the second node
second->next = third; // store the the address of the third node
third->data = 3; // assign data to the third node
third->next = NULL; // end the list
// print the linked list.
printf("The Singly Linked List is: ");
print(head);
return 0;
}
Tree Data Structure in C
A tree is a dynamic data structure in C that represents the hierarchical connection of nodes.
Let's discuss some of the most popular and important trees.
-
Binary Tree
A tree in which each node can have 2 children at maximum is known as a Binary Tree. The child node on the left side of the parent node is known as the left child whereas the child node on the right side of the parent node is known as the right child of the node.
A node in a Binary Tree mainly consists of three parts: data of the node, a pointer to the left child, and a pointer to the right child. In C, a structure is used to represent the nodes of a Binary tree. Consider the following snippet.
struct node
{
int data; // data of the node
struct node* left; // pointer to the left child
struct node* right; // pointer to the right child
};
Here, data is the value of the node whereas left and right are the pointers to the left child and right child respectively.
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data; // data of the node
struct node *left; // pointer to the left
struct node *right; // pointer to the right
};
// Inorder traversal
// 1. left child
// 2. root node
// 3. right child
void inorderTraversal(struct node *root)
{
if (root == NULL)
return;
inorderTraversal(root->left);
printf("%d ->", root->data);
inorderTraversal(root->right);
}
// Preorder traversal
// 1. root node
// 2. left child
// 3. right child
void preorderTraversal(struct node *root)
{
if (root == NULL)
return;
printf("%d ->", root->data);
preorderTraversal(root->left);
preorderTraversal(root->right);
}
// Postorder traversal
// 1. left child
// 2. right child
// 3. root node
void postorderTraversal(struct node *root)
{
if (root == NULL)
return;
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%d ->", root->data);
}
// Create a new Node.
struct node *createNode(value)
{
struct node *newNode = malloc(sizeof(struct node));
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// Insert on the left of the node.
struct node *insertLeft(struct node *root, int value)
{
root->left = createNode(value);
return root->left;
}
// Insert on the right of the node.
struct node *insertRight(struct node *root, int value)
{
root->right = createNode(value);
return root->right;
}
int main()
{
// create a root node
struct node *root = createNode(1);
// insert new nodes to the tree
insertLeft(root, 2);
insertRight(root, 3);
insertLeft(root->left, 4);
printf("Inorder traversal \n");
inorderTraversal(root);
printf("\nPreorder traversal \n");
preorderTraversal(root);
printf("\Postorder traversal \n");
postorderTraversal(root);
}
-
Binary Search Tree (BST)
A Binary Search Tree or BST is an optimized version of a Binary Tree. Like a binary tree, a node of a BST can also have 2 children at most. The major difference between a Binary tree and a BST is the order in which the nodes are arranged. The nodes of a Binary tree do not follow any order while the following order is followed by the nodes of a BST.
The value of the left child of a parent node should have less value than the parent node.
The value of the right child of a parent node should have a higher value than the parent node.
The left and the right subtree of a node must also be binary search trees.
Also Read: An Introduction to Tree in Data Structure
Graph Data Structure in C
The graph data structure in C is a dynamic and non-linear data structure that consists of vertices and some edges that connect those vertices. These vertices are nothing but the nodes. Two nodes are said to be neighboring nodes if there is an edge that connects both the nodes with each other.
Also Read: Your One-Stop Solution For Graphs In Data Structures
The two following graph representations are most commonly used.
Adjacency Matrix
An adjacency matrix is a 2-D square matrix i.e., of size V x V where V is the number of vertices of the graph. An adjacency matrix is represented just as a normal 2-D matrix and is also used for weighted graphs. If you see adj[i][j] = 1 where adj is the name of the matrix, then it means that there is one edge between vertex “i” and vertex “j”.
Adjacency List
An adjacency list is the same as an array. The size of the array represents the total number of vertices of the graph. It is also used to represent the weighted graphs where a list of pairs represents the weights of the edges.
The following example illustrates the Graph data structure in C.
#include <stdio.h>
#include <stdlib.h>
// structure to represent an adjacency list node.
struct AdjListNode
{
int dest; // data of the node
struct AdjListNode *next; // pointer to the next node
};
// structure to represent an adjacency list.
struct AdjList
{
struct AdjListNode *head;
};
struct Graph
{
int V;
struct AdjList *array;
};
// function to create a new adjacency list node.
struct AdjListNode *newAdjListNode(int dest)
{
struct AdjListNode *newNode =
(struct AdjListNode *)malloc(sizeof(struct AdjListNode));
newNode->dest = dest;
newNode->next = NULL;
return newNode;
}
// function that creates a graph having V vertices.
struct Graph *createGraph(int V)
{
struct Graph *graph =
(struct Graph *)malloc(sizeof(struct Graph));
graph->V = V;
// Create an array of
// adjacency lists of size V.
graph->array =
(struct AdjList *)malloc(V * sizeof(struct AdjList));
// initialize each adjacency list
// as empty by making head as NULL
int i;
for (i = 0; i < V; ++i)
graph->array[i].head = NULL;
return graph;
}
// adds an edge to an undirected graph.
void addEdge(struct Graph *graph, int src, int dest)
{
// add an edge from source to destination.
struct AdjListNode *newNode = newAdjListNode(dest);
newNode->next = graph->array[src].head;
graph->array[src].head = newNode;
// add an edge from destination to source.
newNode = newAdjListNode(src);
newNode->next = graph->array[dest].head;
graph->array[dest].head = newNode;
}
// function to print the adjacency list.
void printGraph(struct Graph *graph)
{
int i;
for (i = 0; i < graph->V; ++i)
{
struct AdjListNode *pCrawl = graph->array[i].head;
printf("\n Adjacency list of vertex %d\n head ", i);
while (pCrawl)
{
printf("-> %d", pCrawl->dest);
pCrawl = pCrawl->next;
}
printf("\n");
}
}
int main()
{
int V = 5;
struct Graph *graph = createGraph(V);
addEdge(graph, 0, 1);
addEdge(graph, 0, 4);
addEdge(graph, 1, 2);
addEdge(graph, 1, 3);
addEdge(graph, 1, 4);
addEdge(graph, 2, 3);
addEdge(graph, 3, 4);
// print the adjacency list.
printGraph(graph);
return 0;
}
Wrapping Up!
To sum up, in this comprehensive guide on data structures in C, you learned the variety of data structures that you can create using the C programming language. You started with a brief introduction to data structures in C and discussed the types of data structures and operations that can be performed on them.
Why stop here? You can learn more such interesting software development concepts in Simplilearn’s 9-month certification training on Full Stack Web Development. You will learn important tools and technologies such as Agile methodologies, DevOps culture, Java and its frameworks such as Hibernate, Spring, JPA, etc.
If you are a keen learner and want to keep yourself updated with new technologies, check out Simplilearn’s complete list of free online courses.
If you have any queries in this “Data Structures in C” article or suggestions for us, please mention them in the comment box and our experts answer them for you as soon as possible.
Happy Learning!