Developed in the 1970s, C is a powerful programming language. It is known for being efficient and having control. C is used widely in system programming, operating systems, and embedded systems. Its simplicity and performance have made it a major requirement in the software development industry.
Data structures in C are a way to organise and store data efficiently. They enable programmers to handle large amounts of data with ease. Anyone wishing to write effective code that runs quickly must have knowledge of data structures. Data structures are implemented in C using arrays, linked lists, and stacks, among other methods.
In this blog post, we shall look at different types of data structures in the C programming language. We will cover arrays, linked lists, stacks, as well as queue, binary trees, binary search trees, heaps, graphs, etc.
Types of Data Structures in C
Data structures in C can be divided into two main categories: primitive and non-primitive.
Primitive Data Structures
Primitive data structures are the basic data types provided by the C language. These include int, char, float, and double. They are used to store simple data values.
Example:
In this example, we declare and initialise variables of different primitive data types. The int type stores whole numbers, the char type stores characters or strings, the float type stores single-precision floating-point numbers, and the double type stores double-precision floating-point numbers. We then print these values using printf.
#include <stdio.h>
int main() {
int age = 25; // Integer data type
char name[] = "John Doe"; // Character array (string)
float height = 5.9; // Floating-point data type
double salary = 50000.50; // Double precision floating-point data type
printf("Name: %sn", name);
printf("Age: %dn", age);
printf("Height: %.1f feetn", height);
printf("Salary: %.2fn", salary);
return 0;
}
Output:
Name: John Doe
Age: 25
Height: 5.9 feet
Salary: 50000.50
Non-Primitive Data Structures
Non-primitive data structures are more complex and are derived from primitive data structures. They are used to store collections of data and can be divided into two categories: linear and nonlinear.
Linear Data Structures: Linear data structures store data in a sequential manner, where each element is connected to its previous and next elements.
Array
Linked List
Stack
Queue
Non-Linear Data Structures: Non-linear data structures, on the other hand, store data in a hierarchical manner, where elements may be connected to multiple elements.
Binary Tree
Binary Search Tree
Heap
Hashing
Graph
Get curriculum highlights, career paths, industry insights and accelerate your technology journey.
Download brochure
Array
Arrays are one of the easiest but most popular types of data structure in the C language. An array consists of several elements that are stored one after another, occupying a contiguous memory space. Storing multiple values into a single variable, which can be managed easily, makes manipulating loads of information easier than before.
There are two main classes:
Single-dimensional (or One-dimensional): A single-dimensional array, also known as a one-dimensional array, is like a list where elements are stored in a single row. These elements can be accessed by means of their indexes.
multi-dimensional arrays: A multidimensional array, on the other hand, can be thought of as an array of arrays. The most common form is the two-dimensional array, which is like a table with rows and columns.
Pros
Easy to use: Simple syntax and easy to understand.
Efficient memory access: Fast access to elements using indices.
Static memory allocation: Memory is allocated at compile time, reducing runtime overhead.
Cons
Fixed-size: The size of the array must be known at compile time and cannot be changed.
Memory wastage: If the array size is overestimated, it leads to wasted memory.
Lack of flexibility: Insertion and deletion of elements are not efficient.
Use Cases
Storing lists of elements: Useful for managing a collection of items like numbers, strings, or objects.
Implementing other data structures: Often used as the building blocks for more complex data structures like stacks and queues.
Matrix operations: Multi-dimensional arrays are used in mathematical computations and matrix operations.
Example: Single-Dimensional Array
In this example, we declare a single-dimensional array ‘numbers’ with five elements. We initialise the array with values and then use a loop to print each element along with its index.
#include <stdio.h>
int main() {
// Declare and initialise a single-dimensional array
int numbers[5] = {10, 20, 30, 40, 50};
// Access and print array elements
for (int i = 0; i < 5; i++) {
printf("Element at index %d: %dn", i, numbers[i]);
}
return 0;
}
Output:
Element at index 0: 10
Element at index 1: 20
Element at index 2: 30
Element at index 3: 40
Element at index 4: 50
Example: Multi-Dimensional Array
In this example, we declare a two-dimensional array matrix with three rows and three columns. We initialise the array with values and use nested loops to print each element along with its row and column indices.
#include <stdio.h>
int main() {
// Declare and initialise a two-dimensional array
int matrix[3][3] = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
// Access and print array elements
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
printf("Element at row %d, column %d: %dn", i, j, matrix[i][j]);
}
}
return 0;
}
Output:
Element at row 0, column 0: 1
Element at row 0, column 1: 2
Element at row 0, column 2: 3
Element at row 1, column 0: 4
Element at row 1, column 1: 5
Element at row 1, column 2: 6
Element at row 2, column 0: 7
Element at row 2, column 1: 8
Element at row 2, column 2: 9
Linked List
A linked list is a dynamic data structure that consists of a sequence of elements called nodes. Each node contains data and a reference (or link) to the next node in the sequence. Unlike arrays, linked lists do not store their elements in contiguous memory locations, which allows for efficient insertion and deletion operations. There are several types of linked lists, including singly linked lists, doubly linked lists, and circular linked lists.
While the address of each node in a singly linked list points to the following one in sequence, the last node consists of null as its pointed value showing that this is where all items terminate. Doubly Linked List contains links pointing both forward towards the next nodes as well as backward to preceding ones which makes it possible to go through them in any direction. A Circular Linked List is a variation with the last node connected back to the first forming a loop.
Pros
Dynamic size: The size of a linked list can grow or shrink as needed, making it flexible.
Efficient insertions/deletions: Adding or removing elements is efficient, especially at the beginning or end.
No memory wastage: Memory is allocated as needed, avoiding the wastage seen in arrays.
Cons
Memory overhead: Extra memory is needed to store references (pointers) to other nodes.
Slower access: Accessing elements requires traversal from the beginning, making it slower compared to arrays.
Complexity: More complex to implement and manage due to pointer manipulation.
Use Cases
Dynamic memory allocation: Useful when the size of the data structure is not known in advance.
Implementing other data structures: Basis for more complex structures like stacks, queues, and graphs.
Efficient insertions/deletions: Ideal for scenarios where frequent insertions and deletions are needed.
Example: Singly Linked List
In this example, we define a Node structure with two fields: data to store the value and next to store the reference to the next node. We create three nodes, assign values to them, and link them to form a singly linked list. The printList function traverses the list and prints each node’s data. Finally, we free the allocated memory to avoid memory leaks.
#include <stdio.h>
#include <stdlib.h>
// Define a node structure
struct Node {
int data;
struct Node* next;
};
// Function to print the linked list
void printList(struct Node* n) {
while (n != NULL) {
printf("%d -> ", n->data);
n = n->next;
}
printf("NULLn");
}
int main() {
// Allocate memory for nodes in the linked list
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
struct Node* second = (struct Node*)malloc(sizeof(struct Node));
struct Node* third = (struct Node*)malloc(sizeof(struct Node));
// Assign data to nodes and link them
head->data = 1; // Assign data to first node
head->next = second; // Link first node with second
second->data = 2; // Assign data to second node
second->next = third; // Link second node with third
third->data = 3; // Assign data to third node
third->next = NULL; // End of list
// Print the linked list
printList(head);
// Free allocated memory
free(head);
free(second);
free(third);
return 0;
}
Output:
1 -> 2 -> 3 -> NULL
Stack
A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. This means the last element added to the stack is the first one to be removed. Stacks are used in various applications, such as expression evaluation, backtracking algorithms, and managing function calls in recursive programming. A stack can be implemented using arrays or linked lists.
In a stack, there are primarily two operations:
push (adding an element to the top)
pop (removing the top element).
Other useful operations include peek (viewing the top element without removing it) and isEmpty (checking if the stack is empty).
Pros
Simple to use: Easy to understand and implement.
Efficient operations: Fast push and pop operations.
Memory management: Helps manage function calls and memory in recursive programming.
Cons
Fixed-size (array-based): The size of an array-based stack must be defined initially.
Limited flexibility (array-based): Difficult to resize an array-based stack dynamically.
Linear access time (linked list-based): Accessing elements in a linked list-based stack can be slower.
Use Cases
Expression evaluation: Used in compilers for evaluating mathematical expressions.
Backtracking algorithms: Helps in exploring different possibilities, such as in maze solving.
Function call management: Manages function calls and local variables in recursive programming.
Example: Stack using Array
In this example, we define an array-based stack with a maximum size of 5. We implement the basic stack operations: push, pop, peek, isEmpty, and isFull. The push function adds an element to the top of the stack, the pop function removes the top element, and the peek function returns the top element without removing it. The isEmpty and isFull functions check if the stack is empty or full, respectively. In the main function, we demonstrate pushing, peeking, and popping elements from the stack.
#include <stdio.h>
#include <stdlib.h>
#define MAX 5 // Define the maximum size of the stack
int stack[MAX];
int top = -1;
// Function to check if the stack is empty
int isEmpty() {
return top == -1;
}
// Function to check if the stack is full
int isFull() {
return top == MAX - 1;
}
// Function to push an element onto the stack
void push(int value) {
if (isFull()) {
printf("Stack overflown");
return;
}
stack[++top] = value;
printf("%d pushed onto stackn", value);
}
// Function to pop an element from the stack
int pop() {
if (isEmpty()) {
printf("Stack underflown");
return -1;
}
return stack[top--];
}
// Function to peek the top element of the stack
int peek() {
if (isEmpty()) {
printf("Stack is emptyn");
return -1;
}
return stack[top];
}
int main() {
push(10);
push(20);
push(30);
printf("Top element is %dn", peek());
printf("Popped element is %dn", pop());
printf("Top element after pop is %dn", peek());
return 0;
}
Output:
10 pushed onto stack
20 pushed onto stack
30 pushed onto stack
Top element is 30
Popped element is 30
Top element after pop is 20
Queue
A queue is a linear data structure that satisfies the First In, First Out (FIFO) property. This means when an element is added the first time, it will always be removed first. For example, queues could be used for task scheduling, in process management, handling requests from web servers, or before making any goal-oriented searches such as breadth-first search algorithms. A queue may be implemented using arrays or linked lists.
The essential operations on a queue are enqueue (adding an element to the end) and dequeue (removing an element from the front). Additionally, useful functions like peek allow you to see what’s stored at the front position without removing anything from there.
Pros
Orderly processing: Maintains the order of elements.
Efficient operations: Fast enqueue and dequeue operations.
Fixed-size (array-based): The size of an array-based queue must be defined initially.
Memory overhead (linked list-based): Extra memory is needed for pointers.
Use Cases
Task scheduling: Manages tasks in operating systems and printers.
Request handling: Manages requests in web servers.
Algorithm implementation: Used in breadth-first search and other algorithms.
Example: Queue using Array
In this example, we define an array-based queue with a maximum size of 5. We implement the basic queue operations: enqueue, dequeue, peek, isEmpty, and isFull. The enqueue function adds an element to the end of the queue, the dequeue function removes the front element, and the peek function returns the front element without removing it. The isEmpty and isFull functions check if the queue is empty or full, respectively. In the main function, we demonstrate enqueuing, peeking, and dequeuing elements from the queue.
#include <stdio.h>
#include <stdlib.h>
#define MAX 5 // Define the maximum size of the queue
int queue[MAX];
int front = -1, rear = -1;
// Function to check if the queue is empty
int isEmpty() {
return front == -1;
}
// Function to check if the queue is full
int isFull() {
return rear == MAX - 1;
}
// Function to add an element to the queue
void enqueue(int value) {
if (isFull()) {
printf("Queue overflown");
return;
}
if (front == -1) front = 0;
queue[++rear] = value;
printf("%d enqueued to queuen", value);
}
// Function to remove an element from the queue
int dequeue() {
if (isEmpty()) {
printf("Queue underflown");
return -1;
}
int dequeued = queue[front];
if (front >= rear) {
front = rear = -1;
} else {
front++;
}
return dequeued;
}
// Function to peek the front element of the queue
int peek() {
if (isEmpty()) {
printf("Queue is emptyn");
return -1;
}
return queue[front];
}
int main() {
enqueue(10);
enqueue(20);
enqueue(30);
printf("Front element is %dn", peek());
printf("Dequeued element is %dn", dequeue());
printf("Front element after dequeue is %dn", peek());
return 0;
}
Output:
10 enqueued to queue
20 enqueued to queue
30 enqueued to queue
Front element is 10
Dequeued element is 10
Front element after dequeue is 20
Binary Tree
A binary tree is a hierarchical data structure with each node having at most two children, referred to as the left child or the right child. Binary trees are used in various applications such as searching, sorting, and representing hierarchical data. They are the foundation of more advanced data structures, such as binary search trees and heaps.
At the top of a binary tree, there is the root node. Each node can have up to two children in the tree, allowing for it to be traversed differently such as in-order, pre-order, or post-order traversal, among others.
Pros
Hierarchical structure: Represents hierarchical data naturally.
Efficient searching: Supports fast searching, insertion, and deletion operations.
Flexible size: Can grow dynamically as needed.
Cons
Complexity: More complex to implement and manage compared to linear structures.
Memory overhead: Requires additional memory for storing pointers.
Imbalance: Poorly balanced trees can degrade performance.
Use Cases
Searching and sorting: Basis for binary search trees and heaps.
Hierarchical data: Useful for representing hierarchical structures like file systems.
Expression parsing: Used in compilers for parsing expressions.
Example: Binary Tree
In this example, we define a Node structure for a binary tree. The newNode function creates a new node with the given data and initialises its left and right children to NULL. We build a simple binary tree with the root node and its children. The inOrder function performs an in-order traversal of the binary tree, printing the data of each node. Finally, we free the allocated memory to avoid memory leaks.
#include <stdio.h>
#include <stdlib.h>
// Define a node structure for the binary tree
struct Node {
int data;
struct Node* left;
struct Node* right;
};
// Function to create a new node
struct Node* newNode(int data) {
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
// Function to print the in-order traversal of the binary tree
void inOrder(struct Node* node) {
if (node == NULL) return;
inOrder(node->left);
printf("%d ", node->data);
inOrder(node->right);
}
int main() {
// Create the root node
struct Node* root = newNode(1);
// Create the rest of the binary tree
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(6);
root->right->right = newNode(7);
printf("In-order traversal of the binary tree: ");
inOrder(root);
printf("n");
// Free the allocated memory
free(root->left->left);
free(root->left->right);
free(root->left);
free(root->right->left);
free(root->right->right);
free(root->right);
free(root);
return 0;
}
Output:
In-order traversal of the binary tree: 4 2 5 1 6 3 7
Heap
A heap is a special kind of data structure that is based on trees and satisfies one property – heap property. In a max-heap, for any given node, the value is greater than or equal to all its children’s values, thereby ensuring that the maximum value will always be at the root. For min-heaps, the value of a parent node is less than or equal to all its children’s values meaning that the minimum value will always be at the root position. They are widely used in implementing priority queues.
Heaps are commonly implemented using arrays because it makes calculating parent-child relationships easy using array indices. The left child of node i has an index 2i + 1 while its right child has an index 2i + 2.
Pros
Efficient priority management: Ideal for implementing priority queues.
Fast insertion and deletion: Provides efficient algorithms for inserting and deleting elements.
Automatic ordering: Maintains order, with the largest or smallest element always accessible.
Cons
Complex implementation: More complex to implement compared to simpler structures like arrays.
Use Cases
Priority queues: Managing tasks with different priorities.
Heap sort: An efficient comparison-based sorting algorithm.
Graph algorithms: Used in algorithms like Dijkstra’s shortest path.
Example: Max-Heap using Array
In this example, we define a max-heap using an array. We implement the basic heap operations: insert, heapifyDown, and extractMax. The insert function adds a new element to the heap and then performs heapify up to maintain the heap property. The heapifyDown function ensures the heap property is maintained after removing the root element. The extractMax function removes and returns the maximum element from the heap. In the main function, we demonstrate inserting elements into the heap and extracting the maximum elements.
#include <stdio.h>
#include <stdlib.h>
#define MAX 100 // Define the maximum size of the heap
int heap[MAX];
int size = 0;
// Function to swap two elements
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
// Function to insert an element into the heap
void insert(int value) {
if (size >= MAX) {
printf("Heap overflown");
return;
}
// Insert the new element at the end of the heap
heap[size] = value;
int i = size;
size++;
// Heapify up
while (i != 0 && heap[(i - 1) / 2] < heap[i]) {
swap(&heap[(i - 1) / 2], &heap[i]);
i = (i - 1) / 2;
}
printf("%d inserted into heapn", value);
}
// Function to heapify down
void heapifyDown(int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < size && heap[left] > heap[largest])
largest = left;
if (right < size && heap[right] > heap[largest])
largest = right;
if (largest != i) {
swap(&heap[i], &heap[largest]);
heapifyDown(largest);
}
}
// Function to remove and return the maximum element from the heap
int extractMax() {
if (size <= 0) {
printf("Heap underflown");
return -1;
}
if (size == 1) {
size--;
return heap[0];
}
int root = heap[0];
heap[0] = heap[size - 1];
size--;
heapifyDown(0);
return root;
}
int main() {
insert(10);
insert(20);
insert(30);
insert(5);
insert(15);
printf("Max element extracted: %dn", extractMax());
printf("Max element extracted: %dn", extractMax());
printf("Max element extracted: %dn", extractMax());
return 0;
}
Output:
10 inserted into heap
20 inserted into heap
30 inserted into heap
5 inserted into heap
15 inserted into heap
Max element extracted: 30
Max element extracted: 20
Max element extracted: 15
Graph
A graph is non-linear; it is made up of rows (vertices) and columns that link pairs of nodes together (edges). Graphs also represent relationships between different things, and they are heavily used in computer science, especially networking, social networks, and path-finding algorithms. Graphs can either be directed/undirected or weighted/unweighted.
In directed graphs, edges indicate a relationship from one vertex to another whereas they do not have direction in undirected ones and it’s a mutual relationship between them. Therefore edge weights can determine the cost or distance between vertices which makes them weighted graphs.
Pros
Versatile: Can represent various real-world structures.
Efficient representation of relationships: Models complex relationships effectively.
Support for various algorithms: Many algorithms can be applied to search and pathfinding.
Cons
Memory overhead: Requires additional memory for storing edges.
Scalability issues: Can become complex and inefficient for very large graphs.
Use Cases
Network representation: Models computer networks, social networks, and communication systems.
Pathfinding algorithms: Used in algorithms like Dijkstra’s and A* for finding the shortest path.
Dependency resolution: Helps in tasks like scheduling and resolving dependencies.
Example: Graph using Adjacency List
In this example, we define a graph using an adjacency list. The newAdjListNode function creates a new node for the adjacency list. The createGraph function initialises a graph with V vertices. The addEdge function adds an edge between two vertices in an undirected graph by updating the adjacency list. The printGraph function prints the adjacency list representation of the graph. In the main function, we demonstrate creating a graph with 5 vertices and adding edges between them. Finally, we free the allocated memory to avoid memory leaks.
#include <stdio.h>
#include <stdlib.h>
// Define a structure for the adjacency list node
struct AdjListNode {
int dest;
struct AdjListNode* next;
};
// Define a structure for the adjacency list
struct AdjList {
struct AdjListNode* head;
};
// Define a structure for the graph
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 to create a graph of V vertices
struct Graph* createGraph(int V) {
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->V = V;
graph->array = (struct AdjList*)malloc(V * sizeof(struct AdjList));
for (int i = 0; i < V; ++i) graph->array[i].head = NULL;
return graph;
}
// Function to add an edge to an undirected graph
void addEdge(struct Graph* graph, int src, int dest) {
// Add an edge from src to dest
struct AdjListNode* newNode = newAdjListNode(dest);
newNode->next = graph->array[src].head;
graph->array[src].head = newNode;
// Since the graph is undirected, add an edge from dest to src
newNode = newAdjListNode(src);
newNode->next = graph->array[dest].head;
graph->array[dest].head = newNode;
}
// Function to print the adjacency list representation of a graph
void printGraph(struct Graph* graph) {
for (int v = 0; v < graph->V; ++v) {
struct AdjListNode* pCrawl = graph->array[v].head;
printf("n Adjacency list of vertex %dn head ", v);
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);
printGraph(graph);
// Free the allocated memory
for (int i = 0; i < V; ++i) { struct AdjListNode* head = graph->array[i].head;
while (head) {
struct AdjListNode* temp = head;
head = head->next;
free(temp);
}
}
free(graph->array);
free(graph);
return 0;
}
Output:
Adjacency list of vertex 0
head -> 4-> 1
Adjacency list of vertex 1
head -> 4-> 3-> 2-> 0
Adjacency list of vertex 2
head -> 3-> 1
Adjacency list of vertex 3
head -> 4-> 2-> 1
Adjacency list of vertex 4
head -> 3-> 1-> 0
Conclusion
This blog covers various C data structures including the non-primitive types as well as primitive ones. Grasping the idea of these data structures is an important aspect for any programmer to solve problems adequately. Every piece of related information such as advantages, disadvantages, and uses of different data structures is crucial in a given programming scenario. By mastering arrays, linked lists, stacks, queues, binary trees, heaps, and graphs, you can enhance your ability to write optimised and effective code.
Choosing the right data structure for a given problem is a fundamental skill in computer science. Whether you are handling large datasets, implementing complex algorithms, or optimising performance, the knowledge of these data structures will empower you to make informed decisions. Keep practising and experimenting with these data structures to become proficient in their applications and to tackle more advanced topics in programming.
FAQs
What distinguishes a stack from a queue?
Stack adheres to the LIFO (Last In First Out) principle while Queue follows the FIFO (First In First Out) concept. The last element added to the stack would be the first removed whereas the first element inserted into the queue would be the first one deleted.
How do binary trees differ from binary search trees?
A binary tree is a hierarchical arrangement in which each node has no more than two children. A binary search tree(BST), on the other hand, is a binary tree in which the left child has values less than those of the parent node and the right child has values greater than those of the parent node, making it very efficient when searching.
What are some applications of heap data structure?
Priority queues, heap sort algorithms, and other graph algorithms, like Dijkstra’s shortest path, use Heaps. They can easily manage tasks with different priorities and sort things out.
In what circumstance should I prefer a linked list over an array?
The linked list offers dynamic memory allocation and insertions & deletions that come up often but require less time. Also, if you are unsure about the size of your data structure that changes frequently, then you can go with a Linked list. For quick access to elements and when the size is fixed, arrays are highly recommended.
What is an adjacency list in graph representation?
An adjacency list is a way of representing a graph such that each vertex has a linked list of all its adjacent vertices. This method is effective in storing sparse graphs and allows easy traversal throughout the graph.
Hero Vired is a leading LearnTech company dedicated to offering cutting-edge programs in collaboration with top-tier global institutions. As part of the esteemed Hero Group, we are committed to revolutionizing the skill development landscape in India. Our programs, delivered by industry experts, are designed to empower professionals and students with the skills they need to thrive in today’s competitive job market.
