Complete Notes on Data Structures in C

With Code Examples, Structures, and Detailed Explanations

Complete Notes on Data Structures in C

With Code Examples, Structures, and Detailed Explanations

Complete Notes on Data Structures in C

With Code Examples, Structures, and Detailed Explanations

1. Introduction

Basic Terminology

Data: Raw facts or values (e.g., numbers, characters).
Information: Processed and meaningful data.
Data Structure: A way to organize and store data in a computer so it can be used efficiently.
Algorithm: A step-by-step procedure to solve a problem.

Elementary Data Organization

Type	Description
Primitive	Basic types: `int`, `char`, `float`, `double`
Non-Primitive	Derived from primitive: Arrays, Structures, Pointers, etc.

Built-in Data Types in C

Type	Size (Typical)	Range
`char`	1 byte	-128 to 127
`int`	4 bytes	-2³¹ to 2³¹−1
`float`	4 bytes	±3.4E-38 to ±3.4E+38
`double`	8 bytes	±1.7E-308 to ±1.7E+308
`void`	—	Represents no value

2. Algorithm & Efficiency

Algorithm

A finite sequence of well-defined instructions to solve a problem.

Example: Linear Search

int linearSearch(int arr[], int n, int key) {
    for(int i = 0; i < n; i++) {
        if(arr[i] == key)
            return i;
    }
    return -1;
}

Efficiency of an Algorithm

Measured using:
- Time Complexity: How runtime grows with input size.
- Space Complexity: How memory usage grows with input size.

Asymptotic Notations

Notation	Meaning	Example
Big-O (O)	Upper bound (worst case)	`O(n)`
Big-Ω (Ω)	Lower bound (best case)	`Ω(1)`
Big-Θ (Θ)	Tight bound (average case)	`Θ(n²)`

Common Complexities

Complexity	Name
O(1)	Constant
O(log n)	Logarithmic
O(n)	Linear
O(n log n)	Linearithmic
O(n²)	Quadratic
O(2ⁿ)	Exponential

Time-Space Trade-off

Increase space usage to reduce time (or vice versa).

Example: Precompute factorial values in an array → O(1) lookup vs O(n) computation.

long long fact[100];
void precompute() {
    fact[0] = 1;
    for(int i = 1; i < 100; i++)
        fact[i] = fact[i-1] * i;
}

3. Abstract Data Types (ADT)

ADT = Mathematical model + Operations
Focus on what it does, not how it's implemented.

ADT	Operations
List	Insert, Delete, Search, Traverse
Stack	Push, Pop, Peek
Queue	Enqueue, Dequeue

4. Arrays

Definition

A collection of elements of the same type stored in contiguous memory.

Single Dimensional Array

int arr[5] = {10, 20, 30, 40, 50};

Structure

Index:     0    1    2    3    4
         +----+----+----+----+----+
Value:   | 10 | 20 | 30 | 40 | 50 |
         +----+----+----+----+----+
Address: 1000 1004 1008 1012 1016

Multidimensional Arrays

2D Array (Matrix)

int mat[3][4] = {
    {1, 2, 3, 4},
    {5, 6, 7, 8},
    {9, 10,11,12}
};

Memory Layout: Row-Major Order

Elements stored row by row.

Address Calculation:
For mat[i][j]:
Address = Base + (i * COLS + j) * size_of_element

Column-Major Order

Elements stored column by column (used in Fortran).

Address = Base + (j * ROWS + i) * size_of_element

Index Formula Derivation

1D Array

Address(a[i]) = Base + i * size

2D Array (Row-Major)

Let ROWS = m, COLS = n
Address(a[i][j]) = Base + (i * n + j) * size

3D Array (Row-Major)

Dimensions: [l][m][n]
Address(a[i][j][k]) = Base + ((i * m + j) * n + k) * size

nD Array (General Formula - Row-Major)

Address = Base + (i₁*c₂*...*cₙ + i₂*c₃*...*cₙ + ... + iₙ₋₁*cₙ + iₙ) * size

Applications of Arrays

Storing lists (marks, names)
Matrix operations
Polynomial representation
Lookup tables

Sparse Matrix

A matrix with most elements zero.

Example:

0 0 5 0
0 0 0 0
2 0 0 0

Compact Representation (Triplet Form)

Row	Col	Value
0	2	5
2	0	2

struct Sparse {
    int row, col, value;
};

struct Sparse matrix[100];
int total_non_zero = 2;

5. Linked Lists

Dynamic data structure where elements are connected via pointers.

Types of Linked Lists

Type	Description
Singly	One direction (next)
Doubly	Two directions (prev, next)
Circular	Last → First

Singly Linked List

Node Structure

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

Diagram

HEAD → [10 | →] → [20 | →] → [30 | NULL]

Code: Insertion at Beginning

struct Node* insertFront(struct Node* head, int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = head;
    return newNode;
}

Traversal

void printList(struct Node* head) {
    struct Node* temp = head;
    while(temp != NULL) {
        printf("%d → ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

Deletion (by value)

struct Node* deleteNode(struct Node* head, int key) {
    struct Node *temp = head, *prev = NULL;

    if(temp != NULL && temp->data == key) {
        head = temp->next;
        free(temp);
        return head;
    }

    while(temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }

    if(temp == NULL) return head;

    prev->next = temp->next;
    free(temp);
    return head;
}

Doubly Linked List

Node

struct DNode {
    int data;
    struct DNode *prev, *next;
};

Diagram

NULL ← [10|↔] ↔ [20|↔] ↔ [30|→] NULL

Insertion at End

void insertEnd(struct DNode** head, int data) {
    struct DNode* newNode = (struct DNode*)malloc(sizeof(struct DNode));
    newNode->data = data;
    newNode->next = NULL;

    if(*head == NULL) {
        newNode->prev = NULL;
        *head = newNode;
        return;
    }

    struct DNode* temp = *head;
    while(temp->next != NULL)
        temp = temp->next;

    temp->next = newNode;
    newNode->prev = temp;
}

Circular Linked List

Singly Circular

[10|→] → [20|→] → [30|→]
  ↑_____________________|

void printCircular(struct Node* head) {
    if(head == NULL) return;
    struct Node* temp = head;
    do {
        printf("%d ", temp->data);
        temp = temp->next;
    } while(temp != head);
}

6. Polynomial Representation Using Linked List

Single Variable Polynomial

e.g., 3x⁴ + 2x² + 5

Node

struct Term {
    int coeff;
    int exp;
    struct Term* next;
};

Create Term

struct Term* createTerm(int c, int e) {
    struct Term* t = (struct Term*)malloc(sizeof(struct Term));
    t->coeff = c;
    t->exp = e;
    t->next = NULL;
    return t;
}

Add Two Polynomials

struct Term* addPoly(struct Term* p1, struct Term* p2) {
    struct Term *result = NULL, *temp, *last = NULL;

    while(p1 && p2) {
        if(p1->exp > p2->exp) {
            temp = createTerm(p1->coeff, p1->exp);
            p1 = p1->next;
        }
        else if(p2->exp > p1->exp) {
            temp = createTerm(p2->coeff, p2->exp);
            p2 = p2->next;
        }
        else {
            int sum = p1->coeff + p2->coeff;
            if(sum != 0) {
                temp = createTerm(sum, p1->exp);
            } else {
                temp = NULL;
            }
            p1 = p1->next;
            p2 = p2->next;
        }

        if(temp) {
            if(!result) result = temp;
            else last->next = temp;
            last = temp;
        }
    }

    // Append remaining terms
    struct Term* remaining = p1 ? p1 : p2;
    while(remaining) {
        temp = createTerm(remaining->coeff, remaining->exp);
        if(!result) result = temp;
        else last->next = temp;
        last = temp;
        remaining = remaining->next;
    }

    return result;
}

Two Variable Polynomial

e.g., 3x²y + 2xy² + 5x + 7

Node

struct Term2D {
    int coeff;
    int expX, expY;
    struct Term2D* next;
};

Summary Table

Feature	Array	Linked List
Memory	Contiguous	Non-contiguous
Access	O(1)	O(n)
Insertion/Deletion	O(n)	O(1) at known position
Size	Fixed	Dynamic

Key Takeaways

Arrays → Fast access, fixed size, good for matrices.
Linked Lists → Dynamic size, efficient insert/delete.
Sparse Matrix → Save space using triplet form.
Polynomials → Use linked list for variable degree.
Complexity → Always analyze time and space.

Practice Tip: Implement all operations for singly, doubly, and circular linked lists. Solve polynomial addition/subtraction using linked lists.

End of Notes

Last updated: Nov 12, 2025

Complete Notes on Data Structures in C

With Code Examples, Structures, and Detailed Explanations