Arrays
Arrays are the most fundamental data structure in programming. They store elements in contiguous memory locations, allowing fast access to any element using its index. Even when AI tools can generate array-manipulation code in seconds, understanding how arrays work is essential — it lets you spot bugs, reason about performance costs, and make confident design decisions.
What Is an Array?#
An array is a collection of elements stored at contiguous memory locations. Each element can be accessed directly using its index (its position in the sequence).
Think of an array like a row of numbered mailboxes: each mailbox is in a fixed, predictable slot, and you can reach any one of them directly without searching through the others first.
Indices start at 0 in most languages (C, C++, Java, Python, JavaScript). The first element is at index 0, the second at index 1, and so on.
Key Characteristics#
| Property | Description |
|---|---|
| Fixed Size | Traditional arrays have a fixed size determined at creation |
| Contiguous Memory | Elements are stored next to each other in memory |
| Index-Based | Each element has a numeric index starting from 0 |
| Homogeneous | All elements are typically of the same type |
| Random Access | Any element can be accessed directly in O(1) time |
Memory Layout#
Understanding how arrays are stored in memory helps explain their performance characteristics. When an array is created, the system reserves a block of memory large enough to hold all its elements side by side.
In the formula address = base + (index × size):
- base is the memory address of the first element (e.g., 0x100)
- index is the position you want to access (e.g., 2)
- size is the number of bytes per element (e.g., 4 bytes for a 32-bit integer)
This direct address calculation is why array access is O(1) — the CPU computes the exact memory address in a single arithmetic step and jumps straight to it, regardless of how large the array is.
Basic Operations#
| Operation | Time Complexity | Description |
|---|---|---|
| Access | O(1) | Get element at index |
| Update | O(1) | Modify element at index |
| Insert at End | O(1)* | Add element to the end |
| Insert at Index | O(n) | Shift elements to make room |
| Delete at End | O(1) | Remove last element |
| Delete at Index | O(n) | Shift elements to fill gap |
| Search | O(n) | Find element (unsorted array) |
* Amortized O(1) for dynamic arrays
The * footnote refers to amortized cost: most appends are instant O(1), but occasionally the array must resize itself (allocating new memory and copying all elements). Averaged over many operations, this rare expensive step is negligible — each append costs O(1) on average.
Array Operations
Common operations on arrays with examples
Insertion and Deletion#
When you insert or delete an element in the middle of an array, elements to the right must shift to maintain contiguity. This shifting is what makes these operations O(n) — in the worst case (inserting at index 0), every element in the array must move.
Deletion works the same way in reverse: the element is removed, and everything to its right shifts one position left to close the gap.
Static vs Dynamic Arrays#
| Type | Size | Memory | Languages |
|---|---|---|---|
| Static Array | Fixed at creation | Stack or heap | C, C++, Java (primitive) |
| Dynamic Array | Grows automatically | Heap with resizing | Python list, JavaScript array, ArrayList |
Dynamic Array Resizing#
Dynamic arrays automatically grow when they run out of space. When full, they allocate a new, larger array (typically 2×) and copy all existing elements over before adding the new one.
The resize is expensive (O(n) to copy all elements), but it happens infrequently. Because the capacity doubles each time, the total copy work across all appends is proportional to n, making each append amortized O(1) on average.
Common Patterns#
Two Pointers#
A technique that uses two indices to traverse the array, typically starting from opposite ends and moving toward each other. By doing this in a single pass, it avoids the need for nested loops and keeps the time complexity at O(n).
Reverse Array In-Place
Use two pointers to swap elements from both ends
Sliding Window#
A technique for efficiently processing contiguous subarrays. Instead of recomputing the result for each subarray from scratch, the window slides forward by adding the incoming element on the right and removing the outgoing element on the left. This keeps the window computation O(1) per step, reducing the overall complexity from O(n×k) to O(n). The window can be a fixed size (as below) or variable.
Maximum Sum Subarray of Size K
Find the maximum sum of any contiguous subarray of size k
When to Use Arrays#
| Use Case | Why Arrays Work Well |
|---|---|
| Random access needed | O(1) access by index |
| Iterating through all elements | Cache-friendly, fast iteration |
| Stack implementation | O(1) push/pop at end |
| Known, fixed size | No resizing overhead |
| Sorting algorithms | In-place sorting possible |
When to Consider Alternatives#
| Scenario | Better Alternative |
|---|---|
| Frequent insertions/deletions at beginning | Linked List or Deque |
| Fast lookup by value | Hash Set or Hash Map |
| Maintaining sorted order with insertions | Binary Search Tree or Heap |
| FIFO operations (queue) | Deque or Queue |
Reviewing AI-Generated Code#
When AI generates array code, watch for these common issues:
| Issue | What to Check | Common AI Mistake |
|---|---|---|
| Off-by-one errors | Loop bounds, array access | Using <= instead of < in loops |
| Empty array handling | Edge case checks | Not checking if len(arr) == 0 |
| Index out of bounds | Array access patterns | Accessing arr[i+1] without bounds check |
| Mutation vs copy | In-place operations | Modifying input when copy was needed |
| Inefficient operations | Method complexity | Using list.insert(0, x) in a loop (O(n²)) |
Spotting AI Array Mistakes
Common patterns where AI-generated array code fails
Summary#
| Concept | Key Takeaway |
|---|---|
| Arrays | Contiguous memory, O(1) random access |
| Indexing | Zero-based, direct address calculation |
| Trade-offs | Fast access, slow insertion/deletion in middle |
| Dynamic Arrays | Auto-resize with amortized O(1) append |
| Two Pointers | Efficient technique for many array problems |
| Sliding Window | Process subarrays in O(n) time |
Arrays are the building blocks for many other data structures and algorithms. Master their operations and patterns before moving on to more complex structures!