Introduction
In computer science and software development, a data structure is a way to organize and store data so that we can perform operations on it efficiently (like searching, inserting, deleting, etc.). One of the simplest and most important data structures is the array.
An array is a collection of elements (all of the same kind, e.g. all integers or all strings), stored in contiguous (next-to-each-other) memory locations, accessible by their index (position). Because of this structure, arrays let us access any element quickly when we know its index.
What Is an Array?
Think of an array as a row of boxes, each box labeled with a number (or index). In each box, you can store one item (say, an integer, or a string). Because the boxes are lined up consecutively, if you know the starting box number and the index, you can jump directly to the box you want. That is what gives the array its power: direct access.
Formally:
An array stores elements of the same data type (homogeneous).
Elements are stored in contiguous memory locations (so they’re next to each other in memory).
Each element is identified by an index (often starting from 0).
Because the size is fixed, you can’t easily grow the array (unless you allocate a new one).
Why Contiguous Memory?
Because the elements are stored in adjacent memory addresses, we can compute the address of an element if we know:
Thus, we can do constant time access (O(1)) to any element via its index.
Key Properties of Arrays (with Explanations)
Here are the important properties of arrays, described in simple words:
| Property | Description | Why It Matters |
|---|
| Fixed Size | When you create an array, you decide how many elements it can hold, and that doesn’t change (unless you recreate a new array). | You can’t dynamically increase the size in place. |
| Homogeneous Elements | All elements in an array are of the same type (e.g. all integers, all strings). | This uniformity makes memory allocation and indexing simpler. |
| Contiguous Memory | The elements are stored one after another in memory. | Enables fast indexing and good cache performance. |
| Index-based Access | You use an integer index (often starting from 0) to get any element. | Direct (random) access to any element is fast (constant time). |
| Sequential Structure | Array is a linear or one-dimensional structure by default. | Helps in walking through the array in order. |
Types of Arrays
Arrays can come in different forms depending on how many dimensions they have.
One-Dimensional Array (1D array)
This is the simple, straight line of boxes case we described above.
Example in Python:
arr = [10, 20, 30, 40, 50]
Multi-Dimensional Array (2D, 3D, …)
These are arrays of arrays. For example, a 2D array is like a table or grid (rows and columns).
Example in Python (2D list):
matrix = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
Dynamic Arrays / Resizable Arrays
In some languages (or libraries), arrays can “grow” by internally creating a new larger array and copying the elements. In Python, the built-in list behaves like a dynamic array.
Even though Python’s list is more flexible, under the hood, it uses similar contiguous memory logic to some extent.
Common Operations on Arrays
Here are the typical operations you perform on arrays, and how they behave (with examples). We also discuss their time complexity (how the runtime changes when the array has more elements, n).
1. Access (Read) an Element
You want to get the element at a particular index.
Example in Python:
arr = [10, 20, 30, 40, 50]
print(arr[2]) # prints 30
Time Complexity: O(1), constant time, because we directly compute the location based on index.
2. Update (Write) an Element
You want to change the value of an element at a certain index.
Example in Python:
arr = [10, 20, 30, 40, 50]
arr[3] = 100print(arr) # now: [10, 20, 30, 100, 50]
Time Complexity: O(1)
3. Traversal (Iterating Through All Elements)
You go through each element one by one (for example, to print or sum all).
Example:
for elem in arr:
print(elem)
or using indices:
for i in range(len(arr)):
print(arr[i])
Time Complexity: O(n) — you visit every element once.
4. Searching (Finding an Element)
You want to check whether a value exists in the array, and maybe get its index.
Linear Search (for unsorted array): check each element one by one
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1
Binary Search (for sorted array): repeatedly divide the search interval
Example:
def binary_search(arr, target):
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
5. Insertion (Add an Element)
You insert a new element at a given position (or at end).
If you insert at the end (and there is free space), it can be done in O(1).
If you insert at the middle or beginning, you have to shift all elements to make room -> O(n).
In Python’s list, you might do:
arr.insert(2, 25) # insert 25 at index 2
But internally, elements from index 2 onward will shift right by one.
6. Deletion (Remove an Element)
You remove an element at a given index (or first occurrence of a value).
Deleting from the end is simple, O(1).
Deleting from the middle or beginning requires shifting elements to fill the gap -> O(n).
In Python:
del arr[2] # delete element at index 2# or
arr.pop(2) # remove and return element at index 2
Python Example: Putting It All Together
Here is a small Python script that shows creating an array, doing some operations, and printing results:
def main():
# 1. Create / initialize array (Python list)
arr = [5, 10, 15, 20]
print("Initial array:", arr)
# 2. Access element
print("Element at index 2:", arr[2]) # 15
# 3. Update element
arr[1] = 12
print("After update:", arr) # [5, 12, 15, 20]
# 4. Insert new element
arr.insert(2, 13)
print("After inserting 13 at index 2:", arr) # [5,12,13,15,20]
# 5. Delete element
arr.pop(3) # remove element at index 3
print("After deletion:", arr)
# 6. Search
target = 20
if target in arr:
idx = arr.index(target)
print(f"{target} found at index {idx}")
else:
print(f"{target} not found in array")
# 7. Traverse / print all
print("Traverse:")
for x in arr:
print(x, end=" ")
print()
if __name__ == "__main__":
main()
Output will be something like:
Initial array: [5, 10, 15, 20]
Element at index 2: 15After update: [5, 12, 15, 20]
After inserting 13 at index 2: [5, 12, 13, 15, 20]
After deletion: [5, 12, 13, 20]
20 found at index 3Traverse:5 12 13 20
Note: Although Python’s list behaves dynamically, conceptually it mirrors many array operations.
Time Complexity Table (Big O Notation)
Here's a quick reference:
| Operation | Time Complexity |
|---|
| Access / Read | O(1) |
| Update / Write | O(1) |
| Traversal | O(n) |
| Search (linear) | O(n) |
| Search (binary, sorted) | O(log n) |
| Insertion (end) | O(1) amortized (if space) |
| Insertion (middle / beginning) | O(n) |
| Deletion (end) | O(1) |
| Deletion (middle / beginning) | O(n) |
Use Cases / Real-Life Analogies
Books on a shelf: Think of books lined up in order. You can pick the 3rd book directly (if you count). But inserting a new book in between means shifting those on the right a little.
Seats in a row: You have seats labeled 0,1,2,... and people sitting in them. You can ask: who is in seat 5? But to insert someone in seat 2, you may shift others.
Monthly temperature records: You may store temperatures for 12 months in an array of size 12.
Tables or matrices (2D arrays): For a spreadsheet or grid, you use a 2D array (rows and columns).
Arrays also serve as the foundation for more advanced data structures:
A stack or queue can be implemented using arrays
A matrix (in maths) is a 2D array
Some graph adjacency matrices use arrays
Many algorithms (sorting, searching) assume arrays
Limitations of Arrays (When Not to Use Them)
While arrays are simple and efficient for many tasks, they have drawbacks too:
Fixed Size: You must know (or guess) the maximum size ahead of time. If you exceed it, you have to allocate a new array and copy data.
Costly Insert/Delete in Middle: Inserting or deleting in middle requires shifting many elements → O(n) time.
Wasted Memory: If you allocate more space than needed, that extra is unused (waste). If you allocate too little, you may run out.
Not Flexible for Non-Contiguous Storage: Sometimes data needs to grow in irregular ways; linked lists or dynamic structures might suit better.
Costly Resizing: In “dynamic arrays” (like Python lists or Java’s ArrayList), resizing involves creating a new bigger array and copying, which is expensive occasionally.
Array vs Other Linear Data Structures
When choosing, you consider:
Arrays in Memory (Under the Hood)
It helps to understand what “contiguous memory” means at a low level:
Thus, to find the address of element at index i, you compute:
address = base_address + i * (size of each element)
That’s why access is constant time: direct computation.
Because of this contiguous layout, arrays also enjoy cache locality (processors can fetch nearby data faster).
Summary
An array is a fundamental data structure that stores a fixed-size sequence of homogeneous elements in contiguous memory, enabling constant-time O(1) access by index. Common operations on arrays include access, update, traversal, search, insertion, and deletion, each with its own time complexity. Arrays are simple and efficient for many tasks, forming the foundation for numerous advanced data structures. However, they become less efficient when frequent insertions or deletions in the middle are required, or when the size needs to be dynamic. In Python, the built-in list often serves as an “array-like” structure that supports dynamic resizing, though it conceptually follows many of the same principles. A strong understanding of arrays is essential, as many algorithms and higher-level structures are built upon or extend this core concept.