Programming and Data Structures
What is Programming and Data Structures?
A data structure that stores a fixed-size sequential collection of elements of the same type.
Key formula / rule: Element Address Calculation (1D)
Key points
- Understand the concept of contiguous memory allocation for arrays.
- Learn how to declare, initialize, and access elements in one-dimensional and multi-dimensional arrays.
- Analyze the time complexity of array operations (access, insertion, deletion).
- Recognize the advantages and disadvantages of using arrays compared to other data structures.
Common exam trap
Off-by-one errors when accessing elements (e.g., using `n` instead of `n-1` for the last element).
Definitions
- Term
Array
- Meaning
A data structure that stores a fixed-size sequential collection of elements of the same type.
- Term
Index
- Meaning
A non-negative integer used to identify the position of an element within an array, typically starting from 0.
- Term
Contiguous Memory
- Meaning
Memory locations that are adjacent to each other in sequence.
- Term
Base Address
- Meaning
The memory address of the first element of an array.
- Term
Static Array
- Meaning
An array whose size is fixed at compile time and cannot be changed during runtime.
- Term
Dynamic Array
- Meaning
An array whose size can be adjusted during runtime, often by allocating a new, larger array and copying elements.
Learning objectives
Understand the concept of contiguous memory allocation for arrays.
Learn how to declare, initialize, and access elements in one-dimensional and multi-dimensional arrays.
Analyze the time complexity of array operations (access, insertion, deletion).
Recognize the advantages and disadvantages of using arrays compared to other data structures.
Apply arrays in simple programming problems.
Formulae
- Name
Element Address Calculation (1D)
- Note
Assumes 0-based indexing.
- Expression
Address(A[i]) = BaseAddress(A) + i * SizeOf(Element)
- Name
Element Address Calculation (2D, Row-Major)
- Note
For an array with 'NumberOfColumns' columns.
- Expression
Address(A[i][j]) = BaseAddress(A) + (i * NumberOfColumns + j) * SizeOf(Element)
- Name
Element Address Calculation (2D, Column-Major)
- Note
For an array with 'NumberOfRows' rows.
- Expression
Address(A[i][j]) = BaseAddress(A) + (j * NumberOfRows + i) * SizeOf(Element)
Prerequisites
Basic programming concepts (variables, data types, loops, conditional statements)
Memory management concepts (addresses, contiguous allocation)
Common mistakes
Off-by-one errors when accessing elements (e.g., using `n` instead of `n-1` for the last element).
Assuming arrays are dynamic in size when they are static.
Incorrectly calculating memory addresses in multi-dimensional arrays, especially when dealing with row-major vs. column-major order.
Not handling array index out-of-bounds conditions, leading to crashes or security vulnerabilities.
Keywords
Array
Data Structure
Contiguous Memory
Index
Static Array
Dynamic Array
Multi-dimensional Array
Time Complexity
O(1)
O(n)
Practice preview
In a binary search tree, what is the worst-case time complexity for searching an element?…
medium
Which of the following sorting algorithms has an average time complexity of O(n log n)?…
medium
Which of the following data structures uses LIFO (Last-In, First-Out) principle?…
easy