DSA Arrays
An array stores items one after another, and each item has a numbered position called an index.
What is an Array?
Think of a row of lockers numbered 0, 1, 2, 3. Each locker holds one item. If you know the number, you can open that locker directly.
In memory, an array's items sit next to each other. That is why the computer can jump to any index in one step.
In Python, the built-in list works as a dynamic array: it can grow and shrink.
Example
marks = [72, 85, 64, 90]
print(marks[0])
print(marks[3])
print(len(marks))
marks[2] = 70
print(marks)72 90 4 [72, 85, 70, 90]
Costs of Array Operations
| Operation | Python | Big O | Why |
|---|---|---|---|
| Read by index | a[i] | O(1) | Jump straight to the position |
| Change by index | a[i] = x | O(1) | Same reason |
| Add at the end | a.append(x) | O(1) on average | Space is usually ready |
| Insert at the start or middle | a.insert(0, x) | O(n) | Items must shift right |
| Delete from the start or middle | a.pop(0) | O(n) | Items must shift left |
| Search for a value | x in a | O(n) | May check every item |
Inserting at the front of a big list is slow because every item has to move. If you often add at the front, use a different structure, such as a deque (see the queues lesson).
Traversing an Array
Traversal means visiting every item. This finds the smallest and largest marks in one pass:
Example
marks = [72, 85, 64, 90, 58]
lowest = marks[0]
highest = marks[0]
for m in marks:
if m < lowest:
lowest = m
if m > highest:
highest = m
print("Lowest:", lowest)
print("Highest:", highest)
print("Average:", sum(marks) / len(marks))Lowest: 58 Highest: 90 Average: 73.8
This is O(n): one loop over the data.
Reversing an Array In Place
Swap the first and last items, then move both pointers towards the middle. This uses no extra list, so the extra space is O(1).
Example
def reverse(items):
left = 0
right = len(items) - 1
while left < right:
items[left], items[right] = items[right], items[left]
left += 1
right -= 1
nums = [1, 2, 3, 4, 5]
reverse(nums)
print(nums)[5, 4, 3, 2, 1]
This two-pointer technique appears in many interview problems.
Two-dimensional Arrays
A list of lists works like a table, with rows and columns. Here are the marks of three students in two subjects:
Example
results = [
[80, 75],
[62, 90],
[55, 68],
]
print(results[1][1])
for row in results:
print(sum(row))90 155 152 123
results[1][1] means row 1, column 1 (counting from zero).
Exercise
Exercise
Why is reading arr[500] from an array O(1)?