Comprehensive Study Guide to C Structures, Functions, Pointers, and Data Structures

C Structures: Definition, Syntax, Operations, and Memory Alignment

A structure in C is a user-defined or derived data type that allows grouping elements of possibly different data types into a single composite type under a single identifier. It differs fundamentally from an array, which is a homogeneous collection of identical data types; a structure can store heterogeneous elements sequentially in memory, with each element identified by an individual member name. Structures are essential in software design for modeling real-world entities, such as records for students and faculty members in college management software, and serve as the structural backbone for building dynamic data structures including linked lists and trees.

A structure is defined using the struct keyword, followed by an optional tag identifier and a pair of braces enclosing the declarations of its members. The syntax is established as follows:

struct [structure tag] {
    member definition;
    member definition;
    ...
    member definition;
} [one or more structure variables];

To manipulate the members of a structure, a structure variable must be declared. A variable can be declared simultaneously with the definition or separately by using the struct keyword followed by the structure tag and the variable identifier. For example, declaring a book structure type with members for title, author, price, and page count appears as follows:

struct book {
    char title[50];
    char author[50];
    double price;
    int pages;
} book1;

Members within a structure variable are accessed primarily using the direct selection dot operator (.). For instance, if book1 is an instance of struct book, its four members are accessed via book1.title, book1.author, book1.price, and book1.pages. In contexts where a pointer refers to a structure, member access is achieved using the arrow operator (->, such as structure_ptr->member1) or through explicit indirection syntax ((*pointer).member1).

Structure members can be initialized using several distinct techniques. Default initialization zeroes out all members using {0}, as in struct book book1 = {0};. Initialization via assignment allows sequential member population at declaration time (struct book book1 = {value1, value2, ..., valuen};) or individual member assignment after declaration (book1.title = "Let us C";). The C99 standard introduced designated initialization, which permits members to be initialized in any arbitrary order using dot notation (struct structure_name str = {.member1 = value1, .member3 = value3, .member2 = value2};); this designated initialization feature is supported in C, but not in C++. Structure members can also be populated during program execution via runtime input functions such as scanf("%s%s%f%d", book1.title, book1.author, &book1.price, &book1.pages);.

The following complete program illustrates compile-time initialization alongside runtime input for a structure type:

#include <stdio.h>

struct book {
    char title[100];
    char author[100];
    float price;
    int pages;
};

int main() {
    struct book book1 = {
        "The C Programming Language",
        "Kernighan & Ritchie",
        499.50,
        275
    };

    struct book book2;
    printf("Enter details for book2:
");
    printf("Title (one word): ");
    scanf("%s", book2.title);
    printf("Author (one word): ");
    scanf("%s", book2.author);
    printf("Price: ");
    scanf("%f", &book2.price);
    printf("Pages: ");
    scanf("%d", &book2.pages);

    printf("
--- Book 1 (Compile-time Initialized) ---
");
    printf("Title : %s
", book1.title);
    printf("Author: %s
", book1.author);
    printf("Price : ₹%.2f
", book1.price);
    printf("Pages : %d
", book1.pages);

    printf("
--- Book 2 (Runtime Initialized) ---
");
    printf("Title : %s
", book2.title);
    printf("Author: %s
", book2.author);
    printf("Price : ₹%.2f
", book2.price);
    printf("Pages : %d
", book2.pages);

    return 0;
}

Copying the contents of one structure to another of identical type is accomplished directly via the assignment operator (s2 = s1;). This assignment performs a shallow copy: all immediate bitwise member contents are duplicated into the destination variable. If the structure contains pointers referring to memory dynamically allocated via malloc(), only the pointer memory address is copied, not the underlying dynamic memory block. To duplicate the underlying dynamically allocated memory, a deep copy must be executed manually by allocating separate heap memory and copying the referenced elements.

Type aliases for structure definitions can be created using the typedef keyword to simplify syntax and eliminate the need to repeatedly write struct StructName. There are three standard methods for creating a structure typedef: defining the structure and creating the alias simultaneously (typedef struct StructName { ... } TypedefName;), defining the structure first and subsequently creating the alias (struct StructName { ... }; typedef struct StructName TypedefName;), or declaring an anonymous structure directly paired with an alias name (typedef struct { ... } TypedefName;). Variables can then be declared using TypedefName directly. The following code demonstrates a structure alias using typedef:

#include <stdio.h>

struct Student {
    char name[50];
    int age;
    float gpa;
};

typedef struct Student St;

int main() {
    St student1;
    printf("Enter student's name: ");
    fgets(student1.name, sizeof(student1.name), stdin);
    printf("Enter student's age: ");
    scanf("%d", &student1.age);
    printf("Enter student's GPA: ");
    scanf("%f", &student1.gpa);

    printf("Student Information:
");
    printf("Name: %s", student1.name);
    printf("Age: %d
", student1.age);
    printf("GPA: %.2f
", student1.gpa);

    return 0;
}

When memory is allocated for a structure, contiguous blocks of storage are assigned to hold its members. However, the total memory consumed by a structure is often greater than the mathematical sum of the sizes of its individual members due to structure padding. Microprocessors do not read memory one byte at a time; they read a whole memory word per cycle. In 32-bit architectures, a word is 4 bytes; in 64-bit architectures, a word is 8 bytes. If a multi-byte data type like a 4-byte integer is misaligned across word boundaries, the processor must execute two separate memory read cycles to assemble a single variable, unnecessarily wasting CPU cycles. To optimize hardware access, the compiler aligns members along boundary multiples matching their data size by inserting unused padding bytes.

Structure memory padding showing aligned word access

Consider a structure defined as struct abc { char a; char b; int c; };, assuming a 4-byte integer and 1-byte character. Variables a and b consume 1 byte each, occupying the first two bytes of a 4-byte word. To prevent integer c from crossing word boundaries, the compiler inserts 2 padding bytes immediately after b. Variable c is then allocated across the next 4 bytes. The total size is 1+1+2+4=8 bytes1 + 1 + 2 + 4 = 8\,\text{bytes}. However, reordering the members produces a different layout: in struct abc { char a; int b; char c; };, variable a takes 1 byte, followed by 3 padding bytes so that b starts at byte offset 4; integer b occupies bytes 4 through 7; variable c takes byte 8, and 3 trailing padding bytes are appended to make the total structure size an even multiple of the 4-byte alignment constraint, resulting in a total size of 12 bytes12\,\text{bytes}.

While structure padding accelerates processing speed, it results in wasted memory. When memory efficiency is paramount, padding can be suppressed using the preprocessor directive #pragma pack(1). This directive forces the compiler to pack structure members on 1-byte boundaries without any alignment padding. Applying #pragma pack(1) to struct abc { char a; int b; char c; } var; reduces sizeof(var) from 12 bytes12\,\text{bytes} down to exactly 6 bytes6\,\text{bytes} (1+4+11 + 4 + 1).

Advanced Structure Patterns and Organizations

A nested structure is a structure declared inside another structure. Nested structures can be constructed either through separate structure definitions or through embedded definitions. In the separate definition approach, the dependent inner structure is defined externally and an instance is subsequently embedded as a member within the outer main structure:

#include <stdio.h>
#include <string.h>

struct Employee {
    int employee_id;
    char name[20];
    int salary;
};

struct Organisation {
    char organisation_name[20];
    char org_number[20];
    struct Employee emp;
};

int main() {
    struct Organisation org;
    org.emp.employee_id = 101;
    strcpy(org.emp.name, "Robert");
    org.emp.salary = 400000;
    strcpy(org.organisation_name, "GeeksforGeeks");
    strcpy(org.org_number, "GFG123768");

    printf("Organisation Name : %s
", org.organisation_name);
    printf("Organisation Number : %s
", org.org_number);
    printf("Employee id : %d
", org.emp.employee_id);
    printf("Employee name : %s
", org.emp.name);
    printf("Employee Salary : %d
", org.emp.salary);
    return 0;
}

In the embedded approach, the inner structure type and its instance variable are declared directly inside the enclosing structure block. This consolidates declarations and requires fewer lines of code:

struct Organisation {
    char organisation_name[20];
    char org_number[20];
    struct Employee {
        int employee_id;
        char name[20];
        int salary;
    } emp;
};

Arrays can be declared inside structures whenever multiple data elements of the same type must be associated with a single record. For instance, rather than declaring seven discrete variables (day1, day2, ..., day7) to store the daily attendance of an employee, an array member can be defined within the structure (int WeekAttendance[7];). Defining the array as the last member in the structure declaration is standard practice to safeguard preceding members from corruption in the event of an array buffer overflow.

An array of structures represents a collection where every element in the array is an entire structure of the same type. It enables storing collections of structured records cleanly. The syntax follows standard array declaration: struct struct_name arr_name[size];. The following code illustrates an array of structures:

#include <stdio.h>

struct A {
    int var;
};

int main() {
    struct A arr[2];
    arr[0].var = 10;
    arr[1].var = 20;
    for (int i = 0; i < 2; i++) {
        printf("%d
", arr[i].var);
    }
    return 0;
}

A clear architectural distinction exists between an array within a structure and an array of structures. An array within a structure contains an array as an internal member variable, declared using syntax such as struct class { int ar[10]; } a1, a2, a3;. Its elements are accessed using the dot operator followed by an array subscript: structure.array[index]. Its internal array is stored contiguously in memory, and overall structure padding is independent of the internal array's dimension. Conversely, an array of structures represents an array where every individual element is a structure instance, declared as struct class { int a, b, c; } students[10];. Elements are accessed by array indexing followed by the member dot operator: array[index].member. In memory, alignment padding can introduce unused gaps between successive structure elements throughout the array.

A self-referential structure contains one or more pointer members that point to an instance of the exact same structure type. A canonical example is a linked list node definition:

struct node {
    int val;
    struct node *next;
};

Self-referential structures form the foundational mechanism for implementing dynamic data structures in C, including singly linked lists, doubly linked lists, trees, and graphs, because they permit nodes dynamically allocated on the heap to link together through pointer chaining.

User-Defined Functions in C

A function is a named block of code engineered to perform a specific task, promoting code cleanliness, modularity, and organizational clarity. Modular programming utilizes a top-down approach, decomposing large, complex algorithmic logic into smaller, independent, and reusable blocks. In various paradigms, these blocks are referred to as modules, subroutines, methods, or functions. Every C program contains at least one function, main(), which serves as the entry point.

Functions in C are categorized into standard library functions and user-defined functions. Standard library functions are built-in utilities provided by compiler header files. Examples include printf(), declared in <stdio.h> for sending formatted output to the display screen, and sqrt(), defined in <math.h> for computing square roots. In contrast, user-defined functions are written by developers to address specific application needs. Utilizing user-defined functions provides several practical advantages: programs become easier to understand, maintain, and debug; code modules can be reused across different programs; and large development projects can be partitioned effectively among programming teams.

A user-defined function incorporates three distinct elements: function definition, function call, and function declaration (prototype). A function definition encompasses the complete implementation and consists of a function header and a function body. The function header includes the function return type, the function identifier name, and the formal parameter list. Semicolons are not used at the end of a function header. The function body, enclosed within curly braces, contains local variable declarations, executable program statements, and a return statement.

function_type function_name(parameter list) {
    local variable declaration;
    executable statement1;
    executable statement2;
    ...
    return statement;
}

The return type indicates the data type of the value returned to the caller. If no value is returned, the return type must be explicitly declared as void. By default, C functions that do not specify a return type default to returning int. Function names must adhere to standard C identifier naming rules. Formal parameters represent input variables that receive data passed from the calling program; they are declared within parentheses and separated by commas. If a function accepts no input parameters, it is declared with an empty parameter list or with the keyword (void).

When an executed function encounters a return; or return expression; statement, execution terminates immediately, and program control shifts back to the calling function. While any number of arguments can be passed into a function, a function can return at most one value per call. Multiple return statements can be placed inside conditional branches within the same function.

A function is invoked by using its identifier followed by a comma-separated list of actual parameters enclosed in parentheses. The actual parameters represent the real data values, constants, variables, or expressions passed to the function. When a call occurs, execution control transfers to the called function until a return statement is reached, whereupon control returns to the point of invocation with the evaluated result.

Execution flow and control transfer during a function call

Functions can be invoked in diverse contexts: as standalone statements (mul(10, 5);), with variable arguments (mul(m, 5); or mul(m, n);), with expression arguments (mul(m + 5, 10);), nested inside another function call (mul(10, mul(m, n));), or embedded directly within expressions (y = mul(p, q) / (p + q);). They can also be evaluated within conditional tests (if (mul(m, n) > total) printf("large");). However, a function call cannot appear on the left side of an assignment statement; syntax like mul(a, b) = 15; is illegal.

A function prototype (declaration) informs the compiler about the function's name, return type, and expected parameter list before its invocation, enabling static type checking. A prototype consists of four parts: function return type, function name, parameter list, and a terminating semicolon (for example, int mul(int m, int n);). Prototypes placed outside all functions (in the global declaration section) are global prototypes, accessible throughout the entire file. Prototypes declared inside a specific function body are local prototypes, scoped strictly to that function block.

Eight core rules govern function prototypes and parameter lists: parameter lists must be comma-separated; parameter names in prototypes do not need to match those in function definitions and are optional; parameter data types must match those in the function definition in both count and order; parameterless functions specify (void); return types are optional only when returning int; functions that return nothing must declare a void return type; and any mismatch between declared prototype types and definition types triggers a compilation error.

User-defined functions are classified into five functional categories based on argument passing and return values:

Category 1 represents functions with no arguments and no return values. Control flows from caller to callee and returns upon completion without any data exchange:

#include <stdio.h>

void display_message(void);

int main() {
    printf("Inside main function.
");
    display_message();
    printf("Back in main function.
");
    return 0;
}

void display_message(void) {
    printf("Hello from display_message function!
");
}

Category 2 represents functions with arguments but no return values. Data flows unidirectionally from the calling function to the called function via argument values, but no result is transmitted back:

#include <stdio.h>

void printSum(int num1, int num2);

int main() {
    int a = 10, b = 20;
    printSum(a, b);
    return 0;
}

void printSum(int num1, int num2) {
    int sum = num1 + num2;
    printf("The sum is: %d
", sum);
}

Category 3 represents functions with arguments and one return value. Two-way data communication occurs: the caller passes arguments, and the callee returns a processed result:

#include <stdio.h>

int addNumbers(int num1, int num2);

int main() {
    int number1 = 10, number2 = 25, sum;
    sum = addNumbers(number1, number2);
    printf("The sum of %d and %d is: %d
", number1, number2, sum);
    return 0;
}

int addNumbers(int num1, int num2) {
    return num1 + num2;
}

Category 4 represents functions with no arguments that return a single value. Control transfers to the function, which generates or reads data internally and transmits it back to the caller:

#include <stdio.h>

int get_user_input(void);

int main() {
    int user_number = get_user_input();
    printf("You entered: %d
", user_number);
    return 0;
}

int get_user_input(void) {
    int num;
    printf("Please enter an integer: ");
    scanf("%d", &num);
    return num;
}

Category 5 represents functions that return multiple values. In C, direct multiple returns are emulated by passing pointer arguments or returning structures, as illustrated by chained evaluation functions:

#include <stdio.h>

float ratio(int x, int y, int z);
int difference(int x, int y);

int main() {
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    printf("%f 
", ratio(a, b, c));
    return 0;
}

float ratio(int x, int y, int z) {
    if (difference(y, z)) {
        return ((float)x / (y - z));
    } else {
        return 0.0;
    }
}

int difference(int p, int q) {
    if (p != q) {
        return 1;
    } else {
        return 0;
    }
}

Recursion is a programming technique where a function invokes itself, either directly or indirectly, establishing a execution chain. Every recursive function must define a base termination condition; otherwise, it will recurse indefinitely, consuming stack memory until execution crashes. A typical example is computing the factorial of an integer nn, defined as the product series n!=n(n−1)(n−2)…1n! = n(n-1)(n-2) \dots 1. For instance, 4!=4×3×2×1=244! = 4 \times 3 \times 2 \times 1 = 24. The recursive factorial function evaluates this logic cleanly:

int factorial(int n) {
    int fact;
    if (n == 1) {
        return 1;
    } else {
        fact = n * factorial(n - 1);
        return fact;
    }
}

Passing one-dimensional arrays to functions requires passing only the array name (without subscripts) alongside its size as arguments. In the receiving function definition, the formal parameter is declared with empty brackets (float a[]), without needing to declare an explicit dimension size. The following code finds the largest element in an array:

#include <stdio.h>

float largest(float a[], int n);

int main() {
    float value[4] = {2.5, -4.75, 1.2, 3.67};
    printf("%f
", largest(value, 4));
    return 0;
}

float largest(float a[], int n) {
    int i;
    float max = a[0];
    for (i = 1; i < n; i++) {
        if (max < a[i]) {
            max = a[i];
        }
    }
    return max;
}

Passing two-dimensional arrays requires specifying the array name in the call, but the receiving function parameter must include two sets of brackets, with the second dimension (column size) explicitly defined, such as double average(int x[][N], int M, int N);. Specifying the column size allows the compiler to calculate memory offsets for row indexing.

Structures can also be passed to functions in three distinct ways: passing individual structure members as scalar arguments (e.g., display(p1.x, p1.y);), passing an entire structure by value (where a full local copy is pushed onto the stack, as in display(p1);), or passing the memory address of the structure using a pointer (display(&p1);). Passing by address optimizes memory and execution speed by avoiding the overhead of duplicating large structures on the stack.

Pointer Fundamentals, Arithmetic, and Data Indirection

A pointer is a derived data type built upon fundamental C types that holds memory addresses as its values. Pointers allow programmers to directly access and manipulate computer memory locations where instructions and data reside. Pointers provide several key benefits in C: returning multiple values from functions via reference parameters, passing functions as arguments to other functions, saving storage space when handling character strings, enabling dynamic memory allocation, and manipulating dynamic data structures such as linked lists, stacks, queues, and trees.

Computer memory is organized as an ordered sequence of storage cells called bytes, each assigned a unique numerical address. Addresses are numbered consecutively starting from 0 up to memory size minus one. In a computer system with 64K of memory, the addresses range sequentially from 0 up to 65,53565{,}535.

Sequential memory cells and byte addresses up to 65535

Whenever a variable is declared, the operating system allocates a specific memory location corresponding to that variable's type size. Hardware memory addresses are termed pointer constants. A programmer cannot modify hardware addresses directly; instead, their values are accessed through the address-of operator (&). The retrieved numerical address is known as a pointer value, and a variable allocated to store a pointer value is called a pointer variable.

The address-of operator (&) precedes a variable to return its memory address (for example, p = &quantity;). The indirection or dereference operator (*) operates on a pointer variable to access the value stored at the referenced address. Consequently, if p = &quantity; and n = *p;, then n = *&quantity;, which evaluates directly to n = quantity;. The address-of operator cannot be applied to numeric constants (&125 is illegal), bare array names (&x is illegal), or complex expressions (&(x + y) is illegal). However, applying the address operator to specific indexed array elements, such as &x[0] or &x[i + 3], is valid.

The following program traces pointer access, variable addresses, and indirection mutations:

#include <stdio.h>

int main() {
    int x, y;
    int *ptr;
    x = 10;
    ptr = &x;
    y = *ptr;
    printf("Value of x is %d

", x);
    printf("%d is stored at addr %u
", x, &x);
    printf("%d is stored at addr %u
", *&x, &x);
    printf("%d is stored at addr %u
", *ptr, ptr);
    printf("%d is stored at addr %u
", ptr, &ptr);
    printf("%d is stored at addr %u
", y, &y);
    *ptr = 25;
    printf("
Now x = %d
", x);
    return 0;
}

Tracing this execution reveals how pointer values update across memory cells. When x, y, and ptr are declared, they receive arbitrary memory cells: address 4104 for x, address 4108 for y, and address 4106 for ptr. Assigning x = 10 writes 10 into address 4104. Executing ptr = &x writes the address 4104 into ptr's storage cell at 4106. Assigning y = *ptr dereferences ptr (fetching 10 from 4104) and writes 10 into y at address 4108. Finally, assigning *ptr = 25 overwrites the contents of memory address 4104 with 25, directly changing x to 25 without modifying ptr or y.

Step-by-step memory updates across pointer assignment stages

Pointer variables can participate in mathematical expressions and relational comparisons. Integer values can be added to or subtracted from pointers. When an integer is added to a pointer, the address increments by the integer multiplied by the byte size of the underlying data type. Two pointers of the same type can be compared using relational operators (p1 > p2, p1 == p2, p1 != p2). Operator precedence rules dictate that postfix increment (++) and decrement (--) operators possess higher precedence than the dereference operator (*). Therefore, the expression *ptr++ is parsed as *(ptr++): it accesses the value currently pointed to, and then advances ptr to the next contiguous memory location. To increment the value stored at the referenced address instead, parentheses must be explicitly applied: (*ptr)++.

Ten definitive rules govern pointer operations in C:

  1. A pointer variable can be assigned the address of another variable.

  2. A pointer variable can be assigned the value of another pointer variable of identical type.

  3. A pointer variable can be initialized with NULL or 0.

  4. A pointer variable can be prefixed or postfixed with increment or decrement operators.

  5. An integer value may be added to or subtracted from a pointer variable.

  6. When two pointers point to elements within the same array, one pointer can be subtracted from the other to determine the index distance between them.

  7. When two pointers point to objects of the same data type, they can be compared using relational operators.

  8. A pointer variable cannot be multiplied by a constant.

  9. Two pointer variables cannot be added together.

  10. A value cannot be assigned to an arbitrary address directly (&x = 10; is illegal).

A null pointer is a designated pointer value that does not point to any valid memory address. It is declared using the constant NULL, defined in <stdio.h>, <stdlib.h>, and <string.h>, or by assigning 0 (int *ptr = NULL; or ptr = 0;). A generic pointer, declared with the void type specifier (void *gp;), can store the address of any variable regardless of data type. However, because generic pointers lack an intrinsic data type size, they cannot be directly dereferenced; they must be explicitly cast to a specific type beforehand (e.g., *(int*)gp or *(char*)gp). Void pointers should be used cautiously as they bypass compile-time type verification.

A double pointer (pointer to a pointer) implements multiple indirection: it stores the memory address of another pointer variable. Its declaration syntax is type **name;. In memory, if var = 10 resides at address 2008, a single pointer int *ptr1 = &var; resides at address 4020 storing 2008, and a double pointer int **ptr2 = &ptr1; resides at address 3096 storing 4020. Dereferencing *ptr2 evaluates to 2008 (the address of var), while **ptr2 evaluates to 10 (the value of var). On 64-bit platforms, double pointers occupy 8 bytes (sizeof(d_ptr) is 8). Double pointers are used to allocate multidimensional arrays dynamically on the heap, represent hierarchical structures such as document paragraphs and sentences, manipulate node linkage in data structures without copying values, and alter local pointer addresses within calling scopes.

Double pointer indirection chain pointing to variable

Despite their power, pointers introduce distinct engineering challenges: syntax complexity can make programs harder to maintain; dangling pointers (pointers referencing memory that has already been deallocated) produce unpredictable behavior; memory leaks occur when dynamically allocated memory is never released; buffer overflows create severe security vulnerabilities; platform differences across architectures can impair portability; debugging logic errors is difficult; and dereferencing an invalid or null pointer triggers a segmentation fault, abruptly terminating program execution.

Dynamic Memory Allocation and Array-Pointer Relationships

Dynamic memory allocation gives programmers runtime control over heap memory, allowing memory blocks to be allocated, resized, and freed as data requirements fluctuate. Unlike local stack allocations, which are bound to function scopes and automatically deallocated upon function return, memory allocated on the heap persists until explicitly freed. Consequently, a function can allocate heap memory and safely return its pointer to a calling scope.

Dynamic memory management in C is provided by four functions declared in the <stdlib.h> standard library:

  1. malloc(): Memory Allocation allocates a single contiguous block of raw memory of specified byte size on the heap. Its memory is uninitialized, containing arbitrary garbage values. Its syntax is ptr = (castType*) malloc(size);. For example, int *ptr = (int*) malloc(5 * sizeof(int)); allocates a single block of 20 bytes20\,\text{bytes}.

  2. calloc(): Contiguous Allocation allocates multiple contiguous blocks of memory of specified size and initializes every bit to zero. Its syntax is ptr = (castType*) calloc(n, size);. For example, int *ptr = (int*) calloc(5, sizeof(int)); allocates 5 distinct contiguous blocks of 4 bytes4\,\text{bytes} each, totaling 20 bytes20\,\text{bytes}.

  3. realloc(): Reallocation dynamically alters the size of an existing heap memory block without losing its current contents. Its syntax is ptr = realloc(ptr, new_size);. For example, ptr = realloc(ptr, 10 * sizeof(int)); expands the previously allocated 20 byte20\,\text{byte} buffer to 40 bytes40\,\text{bytes}.

  4. free(): Releases dynamically allocated heap memory back to the operating system. Its syntax is free(ptr);. Dynamically allocated blocks do not free themselves automatically; omitting free() results in progressive memory leaks.

A comparison between malloc() and calloc() summarizes their key architectural and performance characteristics:

Parameter

malloc()

calloc()

Memory Block Count

Allocates a single block of user-specified size

Allocates multiple blocks of memory for a variable

Initial Values

Retains arbitrary garbage values

Always initializes allocated bits to zero

Argument Count

Takes 1 argument (size)

Takes 2 arguments (n, size)

Execution Speed

Faster execution speed

Slower due to initialization overhead

Security Level

Less secure (exposes lingering memory contents)

More secure (zeroes out memory contents)

Time Efficiency

Higher time efficiency

Lower time efficiency

Address Handling

Returns base address without clearing

Clears and zeroes memory before returning base address

Initialization Step

Does not perform initialization

Performs explicit zero-initialization

An array's identifier acts as a constant pointer representing its base address—the memory address of its initial element (arr[0]). If int arr[] = {1, 2, 3, 4, 5};, then assigning int *ptr = &arr[0]; makes ptr point to the first element. Executing ptr++ shifts the pointer forward by sizeof(int) (4 bytes4\,\text{bytes}), causing *ptr to reference the second element (2). Consequently, array subscript notation and pointer offset notation are mathematically equivalent: the expressions arr[i], i[arr], *(arr + i), and *(i + arr) evaluate to the same value.

Two distinct constructs arise when combining pointers with arrays: an array pointer and an array of pointers. An array pointer points to an entire array as a single unit, declared using parentheses: data_type (*var_name)[size]; (such as int (*p)[5];). An array of pointers is an indexed collection of separate pointer variables, declared without parentheses: data_type *arr_name[size]; (such as int *ptr[10];). The following program illustrates an array of pointers:

#include <stdio.h>

int main() {
    int arr1[] = {1, 2, 3, 4, 5};
    int arr2[] = {0, 2, 4, 6, 8};
    int arr3[] = {1, 3, 5, 7, 9};
    int *parr[3] = {arr1, arr2, arr3};
    for (int i = 0; i < 3; i++) {
        printf("%d
", *parr[i]);
    }
    return 0;
}

Two-dimensional arrays are declared using row and column dimensions: data_type array_name[row_size][column_size];. Although envisioned conceptually as a rectangular grid of rows and columns, physical computer memory is strictly linear. Systems map 2D grids into continuous 1D storage using one of two ordering schemes: row-major order (elements are stored sequentially row-by-row) or column-major order (elements are stored sequentially column-by-column).

Sequential storage of 2D array in row-major orderSequential storage of 2D array in column-major order

Because systems track only the array's base address, element addresses must be calculated using mathematical offsets. For an array AA with row dimension MM, column dimension NN, base address Base_Address\text{Base\_Address}, element byte size ww, and 1-based indices (I,J)(I, J), the address mapping formulas are:

Address(A[I][J])=Base_Address+w×{N×(I−1)+(J−1)}(Row-Major Order)\text{Address}(A[I][J]) = \text{Base\_Address} + w \times \{N \times (I - 1) + (J - 1)\} \quad \text{(Row-Major Order)}

Address(A[I][J])=Base_Address+w×{M×(J−1)+(I−1)}(Column-Major Order)\text{Address}(A[I][J]) = \text{Base\_Address} + w \times \{M \times (J - 1) + (I - 1)\} \quad \text{(Column-Major Order)}

As a concrete numerical example, consider a 20×520 \times 5 two-dimensional array marks stored in row-major order with Base_Address=1000\text{Base\_Address} = 1000, element byte size w=2w = 2, and total columns N=5N = 5. Computing the physical address of element marks[18][4] proceeds as follows:

Address(marks[18][4])=1000+2×{5×(18−1)+(4−1)}\text{Address}(\text{marks}[18][4]) = 1000 + 2 \times \{5 \times (18 - 1) + (4 - 1)\}

Address(marks[18][4])=1000+2×{5×17+3}\text{Address}(\text{marks}[18][4]) = 1000 + 2 \times \{5 \times 17 + 3\}

Address(marks[18][4])=1000+2×{85+3}=1000+2×88=1000+176=1176\text{Address}(\text{marks}[18][4]) = 1000 + 2 \times \{85 + 3\} = 1000 + 2 \times 88 = 1000 + 176 = 1176

In pointer notation, a 2D array element is referenced via double indirection as *(*(arr + i) + j). The base name arr points to the first row (row 0); the offset arr + i points to the ii-th row; dereferencing *(arr + i) yields the address of the first element in the ii-th row; adding the index *(arr + i) + j gives the address of the jj-th element in that row; and the final indirection *(*(arr + i) + j) retrieves the scalar value stored at coordinates (i,j)(i, j).

Fundamentals of Data Structures and Abstract Data Types

A well-designed computer program must satisfy four core operational criteria: it must execute correctly, be easy to read and comprehend, be straightforward to debug, and be simple to modify as requirements evolve. A data structure provides a systematic scheme for organizing, storing, and manipulating data efficiently inside computer memory. Data structures are used across computer science disciplines, including compiler design, operating systems, DBMS engines, numerical analysis software, statistical packages, simulations, artificial intelligence, and graphics rendering.

Selecting an optimal data structure requires a three-step engineering evaluation: first, analyze the problem to identify all necessary basic operations (such as insertion, deletion, and searching); second, quantify the resource constraints and performance requirements for each operation; and third, select the data structure that best satisfies these constraints.

Elementary data organization spans four hierarchical levels: data represents an individual raw value or constant (such as a student's grade or an employee's name); a record is a logical collection of related data fields (such as a student's combined name, address, course, and marks); a file is an aggregated collection of related records (such as the records of all 60 students in a class); and a primary key is a unique record field that distinguishes each individual record from all others (such as a student's roll number). Non-key fields, like names or scores, cannot serve as primary keys because multiple records may share identical values.

Data structures are divided into primitive and non-primitive categories. Primitive data structures represent fundamental, machine-level data types supported natively by programming languages, including integers, characters, booleans, floating-point numbers, and pointers. Non-primitive data structures are composite arrangements derived from primitive types, divided into linear and non-linear categories.

Taxonomy and classification of data structures

Linear data structures maintain their elements in a sequential order. They encompass static structures, such as arrays (fixed-size, contiguous sequential memory collections), and dynamic structures, which grow and shrink at runtime. Dynamic linear structures include linked lists (chains of nodes composed of data and reference pointers), stacks (last-in, first-out structures supporting push and pop operations), and queues (first-in, first-out structures supporting enqueue and dequeue operations).

Stack push and pop operationsQueue enqueue and dequeue data structure operations

Non-linear data structures arrange data elements hierarchically or interconnectedly rather than sequentially. Trees store data in multi-level hierarchies, organizing nodes into parent, child, sibling, sub-tree, and leaf relationships originating from a top-level root node. Graphs model arbitrary networks, consisting of vertices (nodes) interconnected by directional or non-directional edges.

Tree terminology showing root, nodes, leaves, and levelsGraph data structure showing vertices and connecting edges

Six standard algorithmic operations are performed across data structures:

  1. Traversing: Accessing and processing every element in the structure exactly once (e.g., printing all student names in a roster).

  2. Searching: Locating the memory position of an element that satisfies a specific condition (e.g., finding the records of all students scoring 100 marks in mathematics).

  3. Inserting: Adding new elements into an existing collection (e.g., adding a newly enrolled student's record).

  4. Deleting: Removing an element from a collection (e.g., deleting the record of a student who has dropped out).

  5. Sorting: Arranging elements into an ordered sequence, either ascending or descending (e.g., alphabetical sorting or extracting top performers).

  6. Merging: Combining two distinct sorted collections into a single, unified sorted collection.

An Abstract Data Type (ADT) is a conceptual specification that defines a data structure solely by its external behavior and supported operations, completely decoupled from its underlying implementation details. For example, stacks and queues represent classic ADTs: a stack is defined by LIFO behavior through push and pop operations, regardless of whether it is implemented under the hood using a static array or a dynamic linked list.

Separating an ADT's interface from its implementation provides a crucial software engineering benefit: programs can evolve without requiring breaking rewrites. If expanding requirements demand changing a student record structure from an array to a linked list, decoupling the data structure from its implementation ensures that calling procedures remain unchanged. Encapsulating operations within an ADT protects client code from implementation shifts, preserving stability and maintainability.