Data Structures in C: When to Use Which?

Table of Contents

1. Arrays
2. Linked Lists
3. Stacks
4. Queues
5. Trees
6. Graphs
7. Conclusion
8. References

Arrays

Fundamental Concepts

An array is a collection of elements of the same data type stored in contiguous memory locations. It has a fixed size, which is determined at the time of declaration.

Usage Methods

#include <stdio.h>

int main() {
    // Declaration and initialization of an array
    int arr[5] = {1, 2, 3, 4, 5};

    // Accessing elements of the array
    for(int i = 0; i < 5; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

Common Practices

• Random Access: Arrays are great for random access. You can access any element in constant time O(1) if you know its index.
• Storing Homogeneous Data: Since all elements in an array must be of the same type, they are suitable for storing homogeneous data.

Best Practices

• Bounds Checking: Always ensure that you do not access elements outside the array bounds, as it can lead to undefined behavior.

Linked Lists

Fundamental Concepts

A linked list is a linear data structure where each element is a separate object called a node. Each node contains data and a pointer to the next node in the list.

Usage Methods

#include <stdio.h>
#include <stdlib.h>

// Define a node structure
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// Function to create a new node
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

int main() {
    Node* head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);

    // Traversing the linked list
    Node* current = head;
    while(current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");

    return 0;
}

Common Practices

• Dynamic Memory Allocation: Linked lists are useful when you need to allocate memory dynamically, as the size of the list can grow or shrink during runtime.
• Insertion and Deletion: Insertion and deletion of elements in a linked list can be done in constant time O(1) if you have a reference to the appropriate node.

Best Practices

• Memory Management: Always free the memory allocated for nodes when they are no longer needed to avoid memory leaks.

Stacks

Fundamental Concepts

A stack is a linear data structure that follows the Last - In - First - Out (LIFO) principle. Elements are added and removed from the top of the stack.

Usage Methods

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

// Define a stack structure
typedef struct Stack {
    int arr[MAX_SIZE];
    int top;
} Stack;

// Function to initialize the stack
void initStack(Stack* s) {
    s->top = -1;
}

// Function to check if the stack is full
int isFull(Stack* s) {
    return s->top == MAX_SIZE - 1;
}

// Function to check if the stack is empty
int isEmpty(Stack* s) {
    return s->top == -1;
}

// Function to push an element onto the stack
void push(Stack* s, int data) {
    if(isFull(s)) {
        printf("Stack is full!\n");
        return;
    }
    s->arr[++(s->top)] = data;
}

// Function to pop an element from the stack
int pop(Stack* s) {
    if(isEmpty(s)) {
        printf("Stack is empty!\n");
        return -1;
    }
    return s->arr[(s->top)--];
}

int main() {
    Stack s;
    initStack(&s);

    push(&s, 1);
    push(&s, 2);
    push(&s, 3);

    printf("%d\n", pop(&s));
    printf("%d\n", pop(&s));

    return 0;
}

Common Practices

• Function Call Management: Stacks are used in programming languages to manage function calls. Local variables and return addresses are stored on the stack.
• Expression Evaluation: Stacks can be used to evaluate expressions, such as postfix and prefix expressions.

Best Practices

• Overflow and Underflow Checks: Always check for stack overflow and underflow conditions before performing push and pop operations.

Queues

Fundamental Concepts

A queue is a linear data structure that follows the First - In - First - Out (FIFO) principle. Elements are added at the rear and removed from the front.

Usage Methods

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

// Define a queue structure
typedef struct Queue {
    int arr[MAX_SIZE];
    int front;
    int rear;
} Queue;

// Function to initialize the queue
void initQueue(Queue* q) {
    q->front = 0;
    q->rear = -1;
}

// Function to check if the queue is full
int isFull(Queue* q) {
    return q->rear == MAX_SIZE - 1;
}

// Function to check if the queue is empty
int isEmpty(Queue* q) {
    return q->rear < q->front;
}

// Function to enqueue an element
void enqueue(Queue* q, int data) {
    if(isFull(q)) {
        printf("Queue is full!\n");
        return;
    }
    q->arr[++(q->rear)] = data;
}

// Function to dequeue an element
int dequeue(Queue* q) {
    if(isEmpty(q)) {
        printf("Queue is empty!\n");
        return -1;
    }
    return q->arr[(q->front)++];
}

int main() {
    Queue q;
    initQueue(&q);

    enqueue(&q, 1);
    enqueue(&q, 2);
    enqueue(&q, 3);

    printf("%d\n", dequeue(&q));
    printf("%d\n", dequeue(&q));

    return 0;
}

Common Practices

• Job Scheduling: Queues are used in operating systems for job scheduling, where tasks are processed in the order they arrive.
• Buffering: Queues can be used as buffers to store data temporarily, such as in network programming.

Best Practices

• Circular Queues: To avoid wastage of space, circular queues can be used instead of simple linear queues.

Trees

Fundamental Concepts

A tree is a non - linear data structure consisting of nodes connected by edges. Each node can have zero or more child nodes, and there is a single root node.

Usage Methods

#include <stdio.h>
#include <stdlib.h>

// Define a tree node structure
typedef struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// Function to create a new tree node
TreeNode* createTreeNode(int data) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

int main() {
    TreeNode* root = createTreeNode(1);
    root->left = createTreeNode(2);
    root->right = createTreeNode(3);

    return 0;
}

Common Practices

• Hierarchical Data Representation: Trees are suitable for representing hierarchical data, such as file systems or organizational charts.
• Searching: Binary search trees can be used for efficient searching, with an average time complexity of O(log n).

Best Practices

• Balancing: For binary search trees, it is important to keep the tree balanced to ensure efficient operations.

Graphs

Fundamental Concepts

A graph is a non - linear data structure consisting of a set of vertices and a set of edges that connect pairs of vertices.

Usage Methods

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 100

// Define a graph structure
typedef struct Graph {
    int vertices;
    int adjMatrix[MAX_VERTICES][MAX_VERTICES];
} Graph;

// Function to create a graph
Graph* createGraph(int vertices) {
    Graph* g = (Graph*)malloc(sizeof(Graph));
    g->vertices = vertices;
    for(int i = 0; i < vertices; i++) {
        for(int j = 0; j < vertices; j++) {
            g->adjMatrix[i][j] = 0;
        }
    }
    return g;
}

// Function to add an edge to the graph
void addEdge(Graph* g, int src, int dest) {
    g->adjMatrix[src][dest] = 1;
    g->adjMatrix[dest][src] = 1;
}

int main() {
    Graph* g = createGraph(3);
    addEdge(g, 0, 1);
    addEdge(g, 1, 2);

    return 0;
}

Common Practices

• Network Representation: Graphs are used to represent networks, such as social networks or computer networks.
• Path Finding: Algorithms like Dijkstra’s algorithm or Breadth - First Search (BFS) can be used to find the shortest path between two vertices in a graph.

Best Practices

• Sparse Graph Representation: For sparse graphs, using an adjacency list instead of an adjacency matrix can save memory.

Conclusion

In conclusion, different data structures in C have their own unique characteristics and use cases. Arrays are great for random access and storing homogeneous data, while linked lists are useful for dynamic memory allocation. Stacks follow the LIFO principle, and queues follow the FIFO principle. Trees are suitable for hierarchical data, and graphs are used for representing networks. By understanding the fundamental concepts, usage methods, common practices, and best practices of each data structure, you can choose the most appropriate one for your programming needs and write more efficient and effective code.

References

• “The C Programming Language” by Brian W. Kernighan and Dennis M. Ritchie
• GeeksforGeeks - A computer science portal for geeks
• Stack Overflow - A community of programmers sharing knowledge and solving problems