Chapter 1 – Introduction to Data Structures

Comprehensive Interactive Guide to Data Structures

What is a Data Structure?

A data structure is a specialized format for organizing, processing, retrieving, and storing data. It's a collection of data values, the relationships among them, and the functions or operations that can be applied to the data.

Classification of Data Structures

Data structures are broadly classified. Click on each type to learn more. A key distinction is also made between Static (fixed size, e.g., Array) and Dynamic (variable size, e.g., Linked List) data structures.

Data Structure

A set of domains D, a set of functions F, and a set of axioms A.

Primitive

Fundamental, built-in types. Ex: `int`, `char`, `float`.

Non-Primitive

User-defined, derived from primitive types. Ex: `struct`, arrays.

Linear

Data is arranged sequentially. Ex: Arrays, Stacks, Queues.

Non-Linear

Data is arranged hierarchically. Ex: Trees, Graphs.

Core Data Structure Operations

Controls

Visual Array

Deep Dive: Structures in C

A `struct` is a user-defined type that groups related data of different types. A `union` is similar, but all members share the same memory location.

Structure

Each member gets its own memory. Total size is the sum of member sizes.

char a[2]; (2 bytes)

int i; (4 bytes)

float j; (4 bytes)

Union

All members share the same memory. Size is that of the largest member.

char a[2];

int i;

float j;

Array of Structures

To store records for multiple entities (e.g., students), you use an array of structures.

Number of Students (1-5):

typedef struct student {
    int roll_no;
    char name[20];
    int marks;
} stud;

int main() {
    stud s[3]; // Array of 3 students
    s[0].roll_no = 1;
    strcpy(s[0].name, "Alice");
    s[0].marks = 88;
    // ... and so on for s[1], s[2]
    return 0;
}

A structure can be a member of another structure. This is called nesting.

struct Date { int day, month, year; };
struct Employee {
    char name[50];
    int id;
    struct Date join_date; // Nested structure
};

int main() {
    struct Employee emp1;
    // Accessing nested members
    emp1.join_date.day = 14;
    emp1.join_date.month = 10;
    emp1.join_date.year = 2025;
}

You can pass individual members or the entire structure to a function.

1. Passing Members

void print_rec(int r, char n[]) {
    printf("%d, %s", r, n);
}
// Call: print_rec(st.roll_no, st.name);

2. Passing Entire Structure

void print_rec(stud s) {
    printf("%d, %s", s.roll_no, s.name);
}
// Call: print_rec(st);

Pointers in C

A pointer is a variable whose value is the memory address of another variable. They enable direct memory manipulation and are crucial for dynamic data structures.

Interactive Pointer Diagram

Click on the items below to see their relationships, values, and addresses.

Click an element to see its details.

int a = 10;
int *ptr1;    // Pointer to int
int **ptr2;   // Pointer to pointer to int

ptr1 = &a;    // ptr1 holds address of a
ptr2 = &ptr1; // ptr2 holds address of ptr1

// Dereferencing
printf("%d", a);    // Prints 10
printf("%d", *ptr1);  // Prints 10
printf("%d", **ptr2); // Prints 10

Dynamic Memory Management

Allocate and free memory at runtime using functions from ``. Use the controls to see how these functions work on a visual 'heap'.

Memory Controls

Block Size (bytes)

Re-allocate Selected To (bytes)

Visual Memory Heap

The heap is empty.