Introduction to Data Structures; Arrays — Static Data Structure — Data Structures and Algorithms

Introduction to Data Structures

What is a Data Structure?

A data structure is a way of organizing, storing and managing data in a computer so that it can be accessed and modified efficiently.

Formal Definition: A data structure is a collection of:

Data — the values stored

Relationships — how the data is related

Operations — what can be done with the data

Why Data Structures?

Efficiency — operations run faster with right data structure
Memory usage — optimal use of available memory
Code clarity — well-chosen structures make code easier to understand
Problem solving — many problems have natural DS solutions

Classification of Data Structures

DATA STRUCTURES
├── Primitive (Basic)
│   ├── Integer
│   ├── Float
│   ├── Character
│   └── Boolean
└── Non-Primitive (Abstract)
    ├── Linear (elements arranged in sequence)
    │   ├── Static: Arrays
    │   └── Dynamic: Linked List, Stack, Queue
    └── Non-Linear (hierarchical / network)
        ├── Trees (hierarchical)
        └── Graphs (network/mesh)

Linear vs Non-Linear

Feature	Linear	Non-Linear
Arrangement	Sequential	Hierarchical/Network
Memory	Contiguous (array) or scattered (linked)	Scattered
Traversal	Single pass	Multiple paths
Examples	Array, Stack, Queue	Tree, Graph

Abstract Data Type (ADT)

An ADT defines:

What the data structure does (operations and behavior)
NOT how it is implemented (implementation-independent)

Example — Stack ADT:

Operations: push, pop, peek, isEmpty, isFull
Implementation: can be array-based or linked-list-based

Arrays — Static Data Structure

What is an Array?

An array is a collection of elements of the same data type stored in contiguous memory locations.

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

Index:   [0] [1] [2] [3] [4]
Value:   10  20  30  40  50
Address: 100 104 108 112 116  (int = 4 bytes)

Properties of Arrays

Property	Description
Fixed size	Size declared at compile time; cannot change
Same type	All elements must be of same data type
Index access	Elements accessed via index (0-based)
Contiguous memory	Elements stored in adjacent memory locations
Random access	Access any element in O(1) time

Array Operations

Operation	Complexity	Description
Access	O(1)	arr[i] — direct by index
Search (unsorted)	O(n)	Linear search
Search (sorted)	O(log n)	Binary search
Insert (end)	O(1)	If space available
Insert (middle)	O(n)	Shift elements right
Delete (end)	O(1)	Just decrement count
Delete (middle)	O(n)	Shift elements left

Array in C

#include <stdio.h>

int main() {
    int arr[5] = {56, 4, 43, 33, 2};

    // Access element
    printf("Element at index 2: %d\n", arr[2]);  // 43

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

    // Find minimum
    int min = arr[0];
    for (int i = 1; i < 5; i++) {
        if
(arr[i] < min) min = arr[i];
    }
    printf("Minimum: %d\n", min);  // 2

    return 0;
}

2D Arrays (Matrix)

int matrix[3][4];   // 3 rows, 4 columns

// Access element at row 1, column 2
matrix[1][2] = 42;

// Traverse 2D array
for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 4; j++) {
        printf("%d ", matrix[i][j]);
    }
    printf("\n");
}

Memory layout (row-major order):

matrix[0][0] matrix[0][1] matrix[0][2] matrix[0][3]
matrix[1][0] matrix[1][1] matrix[1][2] matrix[1][3]
matrix[2][0] matrix[2][1] matrix[2][2] matrix[2][3]
All stored continuously in memory

Advantages and Disadvantages of Arrays

Advantages	Disadvantages
Simple and easy to use	Fixed size — cannot grow/shrink
O(1) random access	Insertion/deletion in middle is O(n)
Cache-friendly (contiguous memory)	Wasted memory if not fully used
Supports binary search (if sorted)	All elements same type

Introduction to Data Structures; Arrays — Static Data Structure