Array

Array

An array is the most fundamental data structure in computing, and almost every other structure is built on top of it. The intuition is simple: imagine a long row of identical, numbered boxes standing shoulder to shoulder in memory. Each box holds one value, every box is exactly the same size, and the boxes are physically adjacent. Because they are adjacent and equal-sized, you never have to search for box number 7 — you can compute exactly where it lives and jump straight to it. That single property, direct address computation, is the entire reason arrays exist and the source of both their superpowers and their sharp limitations.

Precise definition

An array is a contiguous block of memory divided into n equal-sized cells, each holding an element of the same type. The array knows two things: its base address (where the block starts) and the element size in bytes. Element i lives at:

address(i) = base + i × element_size

This is why array indexing is 0-based in most languages: index i literally means "i elements past the start", so the first element sits at offset 0. Because the address is a single multiply-and-add, accessing any element is O(1) — constant time, independent of n and independent of which element you want. This is called random access: reaching the millionth element costs the same as reaching the first.

Two flavours matter. A static/fixed array has a size fixed at creation (C arrays, Java int[]). A dynamic array (Python list, Java ArrayList, C++ vector, Go slice) wraps a fixed array and transparently grows it when full — we analyse that below.

Worked example: the cost of inserting in the middle

Beginners assume arrays are fast at everything. They are not. Take arr = [42, 17, 99, 8, 5] (length 5) and insert 77 at index 2, so the result should be [42, 17, 77, 99, 8, 5]. Reading any element was one operation. Insertion is different, because the contiguity we depend on must be preserved — there is no free gap to slot into.

• Element at index 4 (value 5) shifts to index 5 — move #1
• Element at index 3 (value 8) shifts to index 4 — move #2
• Element at index 2 (value 99) shifts to index 3 — move #3
• Now index 2 is free; write 77 there — 1 write

That is 3 shifts + 1 write to insert near the front of a 5-element array. Insert at the very front of an n-element array and you shift all n elements: O(n). The same is true of deletion in the middle — you shift everything after the hole leftward to close it. So the honest scorecard is: access by index O(1), but insert/delete anywhere except the end is O(n). Appending at the end is the happy case: no shifting, so it is O(1) (amortised — see below).

Dynamic arrays and amortised append

A dynamic array hides a fixed array of some capacity that may exceed its length. Appending while there is spare capacity is a plain O(1) write. When it fills up, the array resizes: it allocates a new, larger block (typically 2× capacity), copies all existing elements over, and frees the old block — an O(n) event.

That single copy looks alarming, but it is rare. Growing from capacity 1 by doubling to reach n elements costs copies of 1 + 2 + 4 + … + n ≈ 2n in total. Spread across the n appends, that averages to about 2 operations per append — a constant. This is amortised O(1): any single append may be O(n) in the worst case, but the average over a long run is O(1). Interviewers love this term because it separates people who memorise "append is O(1)" from people who can explain why despite the occasional expensive resize. Note the doubling matters: growing by a fixed +k each time would give amortised O(n), which is why real implementations multiply.

Pitfalls and what an interviewer probes

• Off-by-one and out-of-bounds. Valid indices are 0 to n-1. Writing to arr[n] is the classic bug; in C it is undefined behaviour that silently corrupts adjacent memory, in Java/Python it throws. Interviewers watch your loop bounds like a hawk.
• Confusing length with capacity. A dynamic array's length is how many elements you have; capacity is how many it can hold before resizing. Only length is user-visible; capacity explains the performance.
• Assuming insert/delete is cheap. Stating "array insertion is O(1)" without qualifying at the end is a red flag. The default (arbitrary position) is O(n).
• Ignoring cache locality. Contiguity means array traversal is extremely fast in practice because the CPU prefetches adjacent memory into cache. This is a real, measurable edge over pointer-chasing structures, and mentioning it signals systems maturity.
• Fixed vs dynamic confusion. Know whether your language's array can grow. A Java int[] cannot; an ArrayList can.

When it matters: trade-offs vs neighbours

Choose an array when you need fast indexed access and mostly append/read rather than middle-insert. It is the backbone of stacks, hash-table buckets, heaps, dynamic programming tables, and matrices.

The key comparison is against the linked list. A linked list makes insertion/deletion at a known position O(1) (just relink pointers, no shifting), but pays for it with O(n) access (you must walk from the head) and poor cache behaviour (nodes scattered in memory). So the trade is a mirror image: array = O(1) access / O(n) insert; linked list = O(n) access / O(1) splice. In real hardware the array usually wins anyway, because its cache-friendly contiguity often beats the linked list's theoretical splice advantage. Against a hash table, arrays lose O(1) key-based lookup but keep order and locality and use less memory. Against a balanced tree (O(log n) ordered insert), arrays trade ordered-mutation speed for simplicity and raw access speed.

Key takeaways

• O(1) random access via base + i × element_size is the array's defining superpower and the reason indexing is 0-based.
• Insert/delete in the middle is O(n) because contiguity forces you to shift elements; only append/pop at the end is cheap.
• Dynamic arrays give amortised O(1) append by doubling capacity on resize; the rare O(n) copy averages out to a constant.
• Versus a linked list, arrays win on access and cache locality but lose on arbitrary-position splicing — pick by which operation dominates your workload.