In computer science, a data structure is a way of organizing and storing data so that it can be accessed and modified efficiently. In C programming, data structures are used to store data in a way that allows various operations like insertion, deletion, updating, and searching to be performed efficiently. Understanding data structures is essential for writing optimized programs and solving complex problems.
There are two main types of data structures in C:
An array is a collection of elements that are stored in contiguous memory locations. Each element in an array is identified by an index or a key. Arrays are useful when you have a fixed number of elements of the same data type.
#include <stdio.h>
int main() {
int arr[5] = {1, 2, 3, 4, 5};
// Accessing array elements
for (int i = 0; i < 5; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
In this example, an array arr of integers is created and initialized with five values. The program then accesses each element and prints it.
A linked list is a linear data structure where each element (node) contains data and a reference (link) to the next node in the sequence. Unlike arrays, linked lists do not require contiguous memory locations.
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
// Function to print the linked list
void printList(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
int main() {
struct Node* head = NULL;
// Creating nodes
struct Node* first = (struct Node*)malloc(sizeof(struct Node));
first->data = 1;
first->next = NULL;
head = first;
struct Node* second = (struct Node*)malloc(sizeof(struct Node));
second->data = 2;
second->next = NULL;
first->next = second;
printList(head); // Output: 1 -> 2 -> NULL
return 0;
}
In this example, we create a simple linked list with two nodes. Each node contains data and a pointer to the next node in the list.
A stack is a linear data structure that follows the LIFO (Last In, First Out) principle. The last element added to the stack is the first one to be removed. Stacks are commonly used in recursion, expression evaluation, and backtracking algorithms.
#include <stdio.h>
#include <stdlib.h>
#define MAX 5
struct Stack {
int arr[MAX];
int top;
};
// Function to initialize the stack
void initStack(struct Stack* stack) {
stack->top = -1;
}
// Function to check if the stack is full
int isFull(struct Stack* stack) {
return stack->top == MAX - 1;
}
// Function to check if the stack is empty
int isEmpty(struct Stack* stack) {
return stack->top == -1;
}
// Function to push an element to the stack
void push(struct Stack* stack, int value) {
if (isFull(stack)) {
printf("Stack is full\n");
return;
}
stack->arr[++(stack->top)] = value;
printf("%d pushed to stack\n", value);
}
// Function to pop an element from the stack
int pop(struct Stack* stack) {
if (isEmpty(stack)) {
printf("Stack is empty\n");
return -1;
}
return stack->arr[(stack->top)--];
}
int main() {
struct Stack stack;
initStack(&stack);
push(&stack, 10);
push(&stack, 20);
push(&stack, 30);
printf("%d popped from stack\n", pop(&stack)); // Output: 30 popped from stack
return 0;
}
In this example, we define a stack using an array and perform operations like push and pop. The stack follows the LIFO principle.
A queue is a linear data structure that follows the FIFO (First In, First Out) principle. The first element added to the queue is the first one to be removed. Queues are used in scenarios like scheduling tasks or handling requests in a server.
#include <stdio.h>
#include <stdlib.h>
#define MAX 5
struct Queue {
int arr[MAX];
int front;
int rear;
};
// Function to initialize the queue
void initQueue(struct Queue* queue) {
queue->front = -1;
queue->rear = -1;
}
// Function to check if the queue is full
int isFull(struct Queue* queue) {
return queue->rear == MAX - 1;
}
// Function to check if the queue is empty
int isEmpty(struct Queue* queue) {
return queue->front == -1;
}
// Function to enqueue an element
void enqueue(struct Queue* queue, int value) {
if (isFull(queue)) {
printf("Queue is full\n");
return;
}
if (queue->front == -1) {
queue->front = 0;
}
queue->arr[++(queue->rear)] = value;
printf("%d enqueued to queue\n", value);
}
// Function to dequeue an element
int dequeue(struct Queue* queue) {
if (isEmpty(queue)) {
printf("Queue is empty\n");
return -1;
}
int value = queue->arr[queue->front];
if (queue->front == queue->rear) {
queue->front = queue->rear = -1;
} else {
queue->front++;
}
return value;
}
int main() {
struct Queue queue;
initQueue(&queue);
enqueue(&queue, 10);
enqueue(&queue, 20);
enqueue(&queue, 30);
printf("%d dequeued from queue\n", dequeue(&queue)); // Output: 10 dequeued from queue
return 0;
}
In this example, we define a queue using an array and perform operations like enqueue and dequeue. The queue follows the FIFO principle.
A tree is a hierarchical data structure consisting of nodes, where each node contains a value and references to its child nodes. A binary tree is a type of tree where each node has at most two children (left and right).
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* left;
struct Node* right;
};
// Function to create a new node
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
void inorder(struct Node* root) {
if (root != NULL) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
int main() {
struct Node* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
printf("Inorder traversal: ");
inorder(root); // Output: 4 2 5 1 3
return 0;
}
In this example, we create a binary tree and perform an inorder traversal, which prints the nodes in the left-right-root order.
Data structures play a vital role in organizing data efficiently and optimizing the performance of algorithms. Understanding the various data structures in C, such as arrays, linked lists, stacks, queues, and trees, is essential for solving complex problems. By using the appropriate data structure for a specific task, you can improve the efficiency of your programs significantly.