Arrays Basics
Learn array fundamentals including memory layout, operations, and time complexity analysis for efficient data manipulation.
Learn array fundamentals including memory layout, operations, and time complexity analysis for efficient data manipulation. This hands-on tutorial focuses on practical implementation of arrays basics concepts.
Arrays Basics
Arrays are one of the most fundamental data structures. They store elements in contiguous memory locations, allowing fast access by index.
What is an Array?
An array is a collection of elements stored in consecutive memory locations. Each element can be accessed directly using its index.
# Python lists are dynamic arrays
numbers = [10, 20, 30, 40, 50]
print(numbers[0]) # Access first element: 10
print(numbers[2]) # Access third element: 30
Key Properties:
- Fixed/Dynamic size: Static arrays have fixed size, dynamic arrays can grow
- Indexed access: O(1) time to access any element
- Contiguous memory: Elements stored next to each other
Static vs Dynamic Arrays
Static Arrays
- Fixed size determined at creation
- No resizing - cannot add beyond capacity
- Memory efficient - exact space allocated
- Examples: C arrays, NumPy arrays
Dynamic Arrays
- Variable size - grows as needed
- Automatic resizing when capacity reached
- Extra memory for future growth
- Examples: Python lists, Java ArrayList, C++ vector
# Python list is a dynamic array
arr = [] # Starts empty
arr.append(1) # Grows to size 1
arr.append(2) # Grows to size 2
# Internally, Python over-allocates for efficiency
Memory Layout & Cache Locality
Arrays benefit from cache locality because elements are stored consecutively in memory.
Memory Layout:
Address: 1000 1004 1008 1012 1016
Value: [10] [20] [30] [40] [50]
↑
Base address
When you access arr[0], the CPU loads nearby elements into cache, making subsequent accesses to arr[1], arr[2] very fast!
Array Operations & Time Complexity
Access - O(1)
value = arr[index] # Direct memory calculation
# Address = base_address + (index × element_size)
Insertion
At End - O(1) amortized
arr.append(5) # Usually O(1), occasionally O(n) during resize
At Beginning/Middle - O(n)
arr.insert(0, 5) # Must shift all elements right
Deletion
From End - O(1)
arr.pop() # Just decrease size
From Beginning/Middle - O(n)
arr.pop(0) # Must shift all elements left
Search - O(n)
if 42 in arr: # Must check each element (unsorted)
print("Found")
Traversal Patterns
Forward Traversal
for i in range(len(arr)):
print(arr[i])
# Or more Pythonic
for element in arr:
print(element)
Reverse Traversal
for i in range(len(arr) - 1, -1, -1):
print(arr[i])
# Or
for element in reversed(arr):
print(element)
With Index and Value
for index, value in enumerate(arr):
print(f"arr[{index}] = {value}")
Common Array Operations
AI Mentor
Confused about "arrays basics data structures memory layout time complexity operations"? Ask our AI mentor for a simplified explanation.
Quiz
Quiz
Question 1 of 5What is the time complexity of accessing arr[i]?
Key Takeaways
✅ Arrays store elements in contiguous memory for O(1) access
✅ Dynamic arrays automatically resize when needed
✅ Insertion/deletion at beginning/middle is O(n) due to shifting
✅ Cache locality makes arrays very fast for sequential access
✅ Essential operations: access, append, insert, delete, search
Practice Now
Ready to test your knowledge? Head over to the Arrays & Basics Practice to solve hands-on problems!
Next, we'll learn advanced array techniques like prefix sum and sliding window! 🚀