An array is the most fundamental data structure in programming: a collection of elements stored in contiguous memory, each accessible by a numeric index. That word "contiguous" is the key to everything about how arrays behave — because every element sits right next to the last one in memory, the computer can calculate the exact memory address of any element instantly, just from its index.
This is why array indexing — items[5] — is one of the few truly O(1) operations in computer science: no searching is involved, just a single arithmetic calculation (start address + index × element size).
Array Operations and Their Complexity
items = [10, 20, 30, 40, 50]
# Access by index -- O(1)
print(items[2]) # jumps directly to the 3rd slot
# Search by value -- O(n), must check elements one by one
print(30 in items) # may have to scan the whole array
# Append to the end -- O(1) on average (more on this below)
items.append(60)
# Insert in the middle -- O(n), every element after the insertion point must shift
items.insert(1, 15) # everything from index 1 onward shifts right by one
# Delete from the middle -- O(n), same shifting problem in reverse
items.pop(1)Output:
30
True
Insertion and deletion at the end of an array are cheap, but anywhere else they're expensive, because every subsequent element has to physically move over by one slot to keep the array contiguous. This single fact explains most of the tradeoffs you'll see when comparing arrays to other structures like linked lists.
Static vs Dynamic Arrays
A static array (common in lower-level languages like C) has a fixed size decided at creation — you can't grow it without creating a new, larger array and copying everything over. A dynamic array (Python's list, Java's ArrayList, JavaScript's Array) handles this resizing automatically behind the scenes: when it runs out of room, it allocates a new, bigger block of memory (often double the size) and copies the old elements into it. This resizing step is O(n) when it happens, but because it happens so rarely relative to the number of appends, the average cost per append works out to O(1) — a concept called amortized complexity.
When Arrays Are the Right Choice
Reach for an array when you need fast, predictable index-based access and your insertions/deletions mostly happen at the end — think of a list of scores, a buffer of recent events, or any data you process sequentially. If you find yourself frequently inserting or removing from the middle or front of a large collection, that's a strong signal to look at a linked list instead, which trades away O(1) indexing for O(1) insertion/deletion once you have a reference to the right spot.