C Data Structures Basics

Data structures are fundamental to computer programming, offering organized ways to store and manipulate data efficiently. In C, understanding data structures is essential as they form the backbone of many algorithms and applications.

What Are Data Structures?

A data structure is a specialized format for organizing, processing, retrieving, and storing data. Different data structures are suited for different kinds of applications, and some are highly specialized for specific tasks.

c

// Example of a simple data structure - an array
int numbers[5] = {1, 2, 3, 4, 5};

Why Data Structures Matter

• Efficiency: The right data structure can drastically improve the performance of an algorithm
• Organization: They help organize data in memory
• Reusability: Well-implemented data structures can be reused across different programs
• Abstraction: They allow programmers to think at a higher level

Basic Data Structures in C

1. Arrays

Arrays are the simplest data structure, storing elements of the same type in contiguous memory locations.

c

// Declaration and initialization
int scores[5] = {95, 88, 76, 90, 85};

// Accessing elements
int firstScore = scores[0];  // 95
scores[2] = 80;              // Modifies the third element

Characteristics:

• Fixed size (in C)
• Constant-time access to elements
• Elements stored contiguously in memory

2. Structures

Structures allow grouping of related data items of different types under a single name.

c

// Definition
struct Student {
    char name[50];
    int id;
    float gpa;
};

// Usage
struct Student alice = {"Alice Smith", 12345, 3.8};
printf("ID: %d, GPA: %.1f\n", alice.id, alice.gpa);

3. Linked Lists

A linked list consists of nodes where each node contains data and a pointer to the next node.

c

// Node definition
struct Node {
    int data;
    struct Node* next;
};

// Creating nodes
struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

Types of Linked Lists:

• Singly Linked List: Each node points to the next node
• Doubly Linked List: Each node points to both the next and previous nodes
• Circular Linked List: The last node points back to the first node

4. Stacks

A stack follows the Last-In-First-Out (LIFO) principle.

c

// Array implementation of stack
#define MAX_SIZE 100

struct Stack {
    int items[MAX_SIZE];
    int top;
};

void initialize(struct Stack* stack) {
    stack->top = -1;
}

void push(struct Stack* stack, int value) {
    if (stack->top == MAX_SIZE - 1) {
        printf("Stack overflow!\n");
        return;
    }
    stack->items[++stack->top] = value;
}

int pop(struct Stack* stack) {
    if (stack->top == -1) {
        printf("Stack underflow!\n");
        return -1;
    }
    return stack->items[stack->top--];
}

5. Queues

A queue follows the First-In-First-Out (FIFO) principle.

c

// Array implementation of queue
struct Queue {
    int items[MAX_SIZE];
    int front;
    int rear;
};

void initialize(struct Queue* queue) {
    queue->front = -1;
    queue->rear = -1;
}

void enqueue(struct Queue* queue, int value) {
    if (queue->rear == MAX_SIZE - 1) {
        printf("Queue overflow!\n");
        return;
    }
    if (queue->front == -1) {
        queue->front = 0;
    }
    queue->items[++queue->rear] = value;
}

int dequeue(struct Queue* queue) {
    if (queue->front == -1 || queue->front > queue->rear) {
        printf("Queue underflow!\n");
        return -1;
    }
    return queue->items[queue->front++];
}

Abstract Data Types (ADTs)

An Abstract Data Type (ADT) is a mathematical model for data types where a data type is defined by its behavior from the point of view of a user of the data.

Common ADTs include:

• List
• Stack
• Queue
• Set
• Map
• Tree
• Graph

Time and Space Complexity

When working with data structures, it's important to understand their performance characteristics:

Operation	Array	Linked List	Stack	Queue
Access	O(1)	O(n)	O(1)*	O(1)*
Search	O(n)	O(n)	O(n)	O(n)
Insertion	O(n)	O(1)**	O(1)	O(1)
Deletion	O(n)	O(1)**	O(1)	O(1)

* For top/front element only
** When position is known

Choosing the Right Data Structure

Selecting the appropriate data structure depends on:

• The operations you need to perform
• The constraints of your problem
• Time and space complexity requirements
• Implementation complexity

Practice Exercise

c

// Implement a simple linked list with basic operations

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

struct Node {
    int data;
    struct Node* next;
};

// Create a new node
struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

// Insert at beginning
struct Node* insertAtBeginning(struct Node* head, int value) {
    struct Node* newNode = createNode(value);
    newNode->next = head;
    return newNode;
}

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

// Free the linked list
void freeList(struct Node* head) {
    struct Node* current = head;
    struct Node* next;
    
    while (current != NULL) {
        next = current->next;
        free(current);
        current = next;
    }
}

int main() {
    struct Node* head = NULL;
    
    // Create a linked list: 5 -> 10 -> 15 -> NULL
    head = insertAtBeginning(head, 15);
    head = insertAtBeginning(head, 10);
    head = insertAtBeginning(head, 5);
    
    printf("Linked List: ");
    printList(head);
    
    // Free memory
    freeList(head);
    
    return 0;
}

Summary

• Data structures are essential for organizing and manipulating data efficiently
• Basic data structures in C include arrays, structures, linked lists, stacks, and queues
• Each data structure has its own strengths and weaknesses
• The choice of data structure affects the efficiency of your program
• Understanding time and space complexity helps in selecting the appropriate data structure

In the next section, we'll dive deeper into linked lists and explore more complex data structures like trees and graphs.