- What an Array Really Is
- Why Arrays Matter
- Indexing and Memory
- Operations and Their Cost
- Python Lists as Dynamic Arrays
- One-Dimensional vs Two-Dimensional Arrays
- Arrays vs Lists
- Practice Checklist
- Real Problem Context
Arrays are the starting point of data structures for a reason. They are simple, predictable, and brutally honest about performance. If something is slow with arrays, it is usually slow everywhere else too.
This chapter exists to build intuition. Not tricks. Not shortcuts. By the end, you should be able to look at any array operation and immediately reason about its cost.
If you skip this and jump ahead, it will catch up with you later.
What an Array Really Is¶
An array is a collection of elements stored in contiguous memory locations.
That single sentence explains almost everything important about arrays.
Because elements are stored next to each other in memory:
Accessing an element by index is fast
Traversing the array is straightforward
Inserting or deleting elements can be expensive
In low-level languages like C or C++, arrays have a fixed size. Once created, the size cannot change.
Python does not expose raw arrays by default. Instead, it gives you lists, which behave like dynamic arrays. The rules are the same. Python just hides the resizing work.
Why Arrays Matter¶
Arrays show up everywhere, even when you do not see them.
They are used to:
Store input data
Build strings
Implement stacks and queues
Represent matrices and grids
Act as building blocks for more complex data structures
If you understand arrays well, many other topics feel less intimidating.
Indexing and Memory¶
Array indexing is the superpower here.
When you write arr[i], the program does not loop or search. It calculates the memory address directly using a formula.
That is why access time is constant.
This is also why arrays need contiguous memory. Without it, direct address calculation would not work.
Operations and Their Cost¶
Do not memorize time complexities. Understand why they happen.
Access by index Constant time because the memory location is directly computed
Update by index Constant time for the same reason as access
Traversal Linear time because every element must be visited
Insertion At the end is usually constant time in Python lists At the beginning or middle is linear time due to shifting
Deletion Linear time in most cases because elements must be shifted
If this feels abstract, draw boxes on paper and simulate shifting.
Python Lists as Dynamic Arrays¶
Python lists automatically resize when they run out of space.
To make this efficient, Python allocates extra memory in advance. Most append operations are fast, but occasional resizes cost more.
This is why append is amortized constant time, not guaranteed constant time.
You do not need to memorize this term. Just remember that Python trades memory for speed.
One-Dimensional vs Two-Dimensional Arrays¶
A one-dimensional array is a simple list of values.
A two-dimensional array is a list of lists.
There is no real matrix structure in Python lists. It is just nesting.
This leads to common mistakes:
Accidentally sharing inner lists
Confusing rows and columns
Incorrect indexing order
Most 2D problems are logic problems, not syntax problems.
Arrays vs Lists¶
In interviews, this distinction is often tested conceptually.
Arrays use contiguous memory and fixed size
Python lists are dynamic and resizable
Arrays are memory efficient
Lists are flexible and easier to work with
You should be able to explain when each choice makes sense.
Practice Checklist¶
Do not rush these. Write them from scratch.
Find the largest element in an array
Count occurrences of a given element
Remove duplicates while preserving order
Reverse an array in place
Real Problem Context¶
Arrays and lists are rarely the final answer. They are the tool you use on the way to the answer.
They appear in:
Sliding window problems
Two pointer techniques
Prefix sum optimizations
Dynamic programming tables
Graph and tree representations
If arrays feel solid, problem solving becomes calmer.
That is the goal.