4.1 Definition of an Array and Its Properties
An array is a data structure that is an ordered collection of elements of the same type, stored in contiguous memory cells. Each element in an array has a unique index used to access it.
Below is a simple array of size 4 containing the elements (1, 2, 3, and 4).
Array Properties:
- Fixed Size: An array's size is set when it's created and cannot be changed during program execution.
- Homogeneity of Elements: All elements in an array must be of the same type (e.g., integers, strings).
- Sequential Memory Location: Array elements are stored in contiguous memory cells, allowing quick index-based access.
- Fast Index-Based Access: Access to any element in an array occurs in constant time
O(1).
4.2 Examples of Using Arrays
Here are examples of how arrays are used that you might already know:
Storing Fixed-Length Data
Days of the week, months of the year:
# Creating an array with days of the week
days_of_week = ["Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"]
print(days_of_week[2]) # Output: Wednesday
Matrices and Multidimensional Arrays
A 3x3 matrix:
# Creating a 3x3 matrix
matrix = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
print(matrix[1][1]) # Output: 5
Use in Sorting Algorithms
Sorting an array of numbers:
# Sorting an array of numbers
numbers = [5, 2, 9, 1, 5, 6]
numbers.sort() # Sorting the array
print(numbers) # Output: [1, 2, 5, 5, 6, 9]
Buffer for Storing Temporary Data
Buffer for reading data from a file:
# Creating a buffer of size 1024 bytes
buffer = [0] * 1024
print(len(buffer)) # Output: 1024
4.3 Basic Operations with Arrays
Note! The list class in Python is a dynamic array, meaning it can change its size during execution. You’ll learn more about dynamic arrays in upcoming lectures.
Main operations: index-based access, insertion, deletion
Index-Based Access
Accessing an array element is done using an index, which points to its position.
# Accessing array elements by index
arr = [10, 20, 30, 40, 50]
print(arr[2]) # Output: 30
print(arr[-1]) # Output: 50 (last element)
Insertion
Inserting an element into an array may require shifting subsequent elements to make space for the new one.
Example (inserting an element in the middle of an array):
# Inserting an element into an array
arr = [10, 20, 30, 40, 50]
arr.insert(2, 25) # Inserting 25 at position 2
print(arr) # Output: [10, 20, 25, 30, 40, 50]
Deletion
Removing an element from an array may require shifting subsequent elements to fill the gap.
Example (removing an element):
# Removing an element from an array
arr = [10, 20, 30, 40, 50]
arr.pop(2) # Removing element at position 2
print(arr) # Output: [10, 20, 40, 50]
4.4 Advantages and Disadvantages of Using Arrays
Let's look at the pros and cons of using arrays:
Advantages:
- Fast Index-Based Access: Access to any element in an array is in constant time
O(1), making arrays very efficient for data retrieval. - Simplicity of Implementation: Arrays are simple to understand and use; they are easy to implement and apply in various tasks.
- Low Overhead: Arrays require less memory compared to more complex data structures like linked lists.
Disadvantages:
- Fixed Size: An array's size is set during creation and cannot be changed. This means you need to know the required size in advance or use dynamic arrays that can grow as needed.
- Costs of Insertion and Deletion: Inserting and deleting elements can be time-consuming as they require shifting elements. In the worst case, inserting or deleting an element in the middle of an array takes
O(n)time. - Inefficient Memory Usage: If an array is not fully utilized, the remaining memory cells are left unused, leading to inefficient memory usage.
GO TO FULL VERSION