Introduction, Data Structures & Arrays

1.2Data and Information

1.3Organising Information: Field, Record, File

Information is organised hierarchically:

1.4What is a Data Structure?

Files can be very large, and we need to perform many operations on them efficiently:

• Insertion
• Deletion
• Updation
• Searching
• Viewing (traversing)
• Queries such as finding the employee with the maximum salary
• Many more…

Doing these efficiently requires organising the data in computer memory in a deliberate way — that organisation is the data structure.

Where does a data structure live?

In this definition, computer memory normally means main memory (RAM) while a program is running. For example, when Python executes A = [10, 20, 30, 40], the list and the information needed to manage it exist in the program's memory, backed primarily by RAM.

Classification

1.5Why Data Structures Matter

The choice of data structure decides how fast each operation can be. The same four operations cost very differently across structures:

No single structure wins everywhere — each trades speed in one operation for speed in another, which is why we study many of them.

1.6Arrays

The array is the simplest linear data structure. It is:

• Stored in a contiguous block of memory,
• Made of elements of the same data type, and
• Supports random access — any element can be reached directly by its index.

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

1.7Array Indexing (Offset or Position)

For int arr[5] = {10, 20, 30, 40, 50}; there are two indexing conventions:

0-based indexing — most common in programming languages

1-based indexing — used only in theory

1.8Array Operations

Traversal — iterating through elements

for (int i = 0; i < n; i++) {
    printf("%d ", A[i]);
}

Insertion — adding an element at a specific index

A[index] = 5;

Deletion — removing an element at a specific index (requires shifting)

for (int i = index; i < n - 1; i++) {
    A[i] = A[i + 1];
}
n--;

Before:            [10, 20, 30, 40, 50]        n = 5
Shift right from the end:
  A[5] = A[4] →    [10, 20, 30, 40, 50, 50]
  A[4] = A[3] →    [10, 20, 30, 40, 40, 50]
  A[3] = A[2] →    [10, 20, 30, 30, 40, 50]
Place:  A[2] = 25 →[10, 20, 25, 30, 40, 50]    n = 6

Before:            [10, 20, 30, 40, 50]        n = 5
  A[1] = A[2] →    [10, 30, 30, 40, 50]
  A[2] = A[3] →    [10, 30, 40, 40, 50]
  A[3] = A[4] →    [10, 30, 40, 50, 50]
Shrink: n-- →      [10, 30, 40, 50]             n = 4

Search — finding an element

Linear search or binary search (binary search needs the array to be sorted).

Update — modifying an element

Assign a new value at the given index, e.g. A[index] = new_value;

1.9Strengths and Limitations

1.10Array Addressing

Because arrays are contiguous, the memory address of any element can be computed directly from its index.

#include <stdio.h>

int main(void) {
    int arr[5] = {10, 20, 30, 40, 50};

    for (int i = 0; i < 5; i++) {
        printf("&arr[%d] = %p\n", i, (void *)&arr[i]);
    }
    return 0;
}

1.112-Dimensional (2D) Arrays

A 2D array is an array of arrays, representing data in rows and columns (matrix format). Elements are accessed using two indices — a row index and a column index, e.g. A[i][j].

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

1.122D Arrays: Memory Representation

Memory is one-dimensional, so a 3 × 4 matrix must be flattened into a line. Two conventions exist:

1.132D Array Addressing (0-based)

Example: for the 3 × 4 array above, the element arr[i=2][j=2] in row-major order sits at Base_address + ((2 × 4) + 2) × size.

1.14Worked Question

1.15Observations: Why "Same Data Type"?

Section 1.6 said an array holds elements of the same data type. What actually happens if we cheat? Two experiments from the lecture:

Experiment 1 — a char and a float in an int array

int arr[5] = {1, 2, 3, 'A', 5.5};
printf("arr[3] is %d, and arr[4] is %d \n", arr[3], arr[4]);
printf("Char in arr[3] is %c", arr[3]);

#include <stdio.h>

int main(void) {
    int arr[5] = {1, 2, 3, 'A', 5.5};

    printf("arr[3] as int  = %d\n", arr[3]);
    printf("arr[3] as char = %c\n", arr[3]);
    printf("arr[4]         = %d\n", arr[4]);
    return 0;
}

Experiment 2 — a string in an int array

int arr[5] = {1, 2, 3, "hello", 5.5};   // ERROR?!

#include <stdio.h>

int main(void) {
    int arr[5] = {1, 2, 3, "hello", 5.5};
    printf("%d\n", arr[3]);
    return 0;
}