Study Notes
Free high-yield revision notes for Introduction to Data Structures; Arrays — Static Data Structure
Introduction to Data Structures; Arrays — Static Data Structure
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
text
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.
c
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
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)
c
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):
text
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 memoryAdvantages 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 |