Arrays
An array is a fundamental data structure that stores elements in contiguous memory locations, enabling constant-time access by index and forming the backbone of most other data structures and algorithms.
What is an Array?
An array is a collection of elements stored at contiguous (adjacent) memory locations. Because the elements are packed together in sequence, the address of any element can be computed from its index using a simple formula: base_address + index * element_size. This is what gives arrays their hallmark O(1) random access.
Arrays are among the oldest and most widely used data structures in computer science. Nearly every programming language provides a built-in array type. They are the foundation on which many higher-level structures — such as dynamic arrays (Python lists, Java ArrayLists), heaps, hash tables, and matrices — are built.
Key characteristics of arrays:
- Fixed size (static arrays): The size is determined at creation time and cannot change. Languages like C and Java (primitive arrays) use fixed-size arrays.
- Dynamic resizing: Higher-level languages provide dynamic arrays (e.g., Python's
list, C++'sstd::vector, Java'sArrayList) that automatically grow when capacity is exceeded, typically doubling in size. - Homogeneous elements: In statically typed languages, all elements must be the same type. Dynamically typed languages like Python allow mixed types.
- Zero-based indexing: Most languages index arrays starting from 0, so the first element is at index 0 and the last is at index
n - 1. - Cache-friendly: Because elements are stored contiguously, arrays exhibit excellent spatial locality, making sequential access very fast on modern CPUs.
The main trade-off is that insertion and deletion in the middle of an array are expensive — O(n) — because elements must be shifted to maintain contiguity. When frequent insertions and deletions are needed, a linked list or other structure may be more appropriate.
Interactive Visualization
arr = [10, 20, 30, 40, 50]
# Access: O(1)
print(arr[2])
# Insert at index i
arr.insert(i, val)
# Delete at index i
arr.pop(i)
# Search (linear)
for x in arr:
if x == target:
return True
return False
Code Implementation
# --- Array Operations in Python ---
# Create an array (Python list)
arr = [5, 12, 8, 3, 19, 7]
print("Original:", arr)
# Access by index - O(1)
print("Element at index 2:", arr[2]) # 8
# Insert at a specific index - O(n)
def insert_at(array, index, value):
"""Insert value at the given index, shifting elements right."""
array.insert(index, value)
return array
insert_at(arr, 2, 99)
print("After insert 99 at index 2:", arr)
# Delete at a specific index - O(n)
def delete_at(array, index):
"""Remove element at the given index, shifting elements left."""
if 0 <= index < len(array):
array.pop(index)
return array
delete_at(arr, 2)
print("After delete at index 2:", arr)
# Linear search - O(n)
def linear_search(array, target):
"""Return the index of target, or -1 if not found."""
for i in range(len(array)):
if array[i] == target:
return i
return -1
idx = linear_search(arr, 19)
print("Search for 19: found at index", idx)
Complexity Analysis
| Operation | Time Complexity | Explanation |
|---|---|---|
| Access | O(1) | Direct address calculation from base address and index. |
| Search | O(n) | Must scan elements one by one in the worst case (linear search). |
| Insertion | O(n) | Elements after the insertion point must be shifted right. |
| Deletion | O(n) | Elements after the deletion point must be shifted left. |
| Space | O(n) | Requires memory proportional to the number of elements stored. |
Note: Appending to the end of a dynamic array (e.g., Python list.append()) is amortized O(1) because resizing doubles the capacity, so the expensive copy happens infrequently. However, inserting at an arbitrary position is always O(n) due to shifting.
Practice Problems
Real-World Applications
list type is a dynamic array; every Python program uses it
Practice
k positions. If k is larger than the array length, wrap around.Quiz
Q1. What is the time complexity of accessing an element in an array by its index?
Q2. Why is inserting an element in the middle of an array O(n)?
Q3. What is the primary advantage of arrays over linked lists?
Q4. In a zero-indexed array of 8 elements, what is the index of the last element?
Q5. What is the amortized time complexity of appending to the end of a dynamic array (e.g., Python list)?