Array

structurebeginnerTime O(n)Space O(1)

Numbered slots side by side. Reading slot k is instant, but making room in the middle means shifting everything after it.

Delete index 1. Removing 1 leaves a gap that everything to the right must close.

How it runs, step by step

Delete index 1. Removing 1 leaves a gap that everything to the right must close.
Array of 5 values. Deleting 1 at index 1 requires shifting 3 values left.
Clear index 1. The slot is empty now.
1 removed. Index 1 is an empty slot.
Move 4 from index 2 to index 1.
Shift: 4 moves left from index 2 to index 1.
Move 2 from index 3 to index 2.
Shift: 2 moves left from index 3 to index 2.
Move 8 from index 4 to index 3.
Shift: 8 moves left from index 4 to index 3.
Done: 3 shifts. The last slot is now empty; the array holds 4 values.
Result: 1 deleted after 3 shifts. 4 values remain and the last slot is empty.

Write it yourself

Define linearSearch(values, target) and return the index of the target, or -1 when it is not there. It runs in your browser against this lesson's own 2 examples.

1// Nothing is sorted here, so there is nothing to halve: look at each value in turn.2function linearSearch(values, target) {3  4  return -1;5}6

Ln 1, Col 16 linesTab indents; Escape then Tab leaves the editor. Ctrl-Enter runs, Cmd-Enter on a Mac.

Remember

Access by index is O(1), because the address is just start plus index times slot size.
Insert or delete in the middle is O(n) because of the shifting.
A fixed array cannot grow. That is the problem dynamic arrays solve.

Topics covered

Where this is used

Scientific computingNumPy ndarray

A NumPy array is one contiguous block of memory plus a shape and a set of strides, so element (i, j) is a single address computation rather than a chase through objects. When the block is contiguous and the dtype already matches, that layout is what lets NumPy pass it straight to BLAS or to vector CPU instructions with no repacking. It is also why np.insert returns a new array instead of editing in place: there is nowhere to put the extra element without moving the tail.

Operating systemsThe file descriptor table

Linux keeps every open file of a process in a per-process array, and a file descriptor is just the index into it, which is why read(3, ...) resolves the file with one lookup on the syscall path. It also explains two behaviours programmers notice: descriptors are small integers, and open always returns the lowest free one, because the kernel keeps a bitmap of which slots are taken and picks the first zero bit.

DatabasesLine pointers in a PostgreSQL page

An 8 KB heap page begins with a small header, and right after it sits an array of fixed-size line pointers, four bytes each; a row's CTID is the pair (page number, index into that array). The fixed size is the whole point: the database reaches slot k by arithmetic, with no scan of the page. A line pointer is never moved until it is freed, so when the page is compacted and the row itself slides to a different offset, the slot number an index entry already holds still finds it.

GraphicsVertex buffers on the GPU

A mesh is uploaded as one flat array of vertices with a declared stride, and an index buffer is a second array of integers naming which vertices to draw. Because the stride is fixed and declared up front, the hardware works out the address of vertex k without reading anything first, so thousands of cores fetch their own vertices in parallel with no coordination. A pointer-chasing layout would make every fetch wait on the load before it.

Why it works this way

Why do indexes start at zero?

The address of slot k is start + k * slotSize, so with zero-based indexing the index is literally how far the slot sits from the start and the base address needs no correction term. It also keeps ranges clean: 0 <= i < n has no off-by-one at either end, the half-open range [i, j) has length exactly j - i, and an empty range is just i == j instead of a special case.

Why can the shifting not be avoided?

The O(1) lookup only works because slot k sits at a position computed from k alone. Inserting in the middle renumbers every element after the gap, and a renumbered element has to physically move to its new address, so the shift is the price of the lookup rather than a sloppy implementation. In this flat layout you cannot have both O(1) indexing and O(1) middle insert. Text editors dodge it with a gap buffer: they park the empty space at the cursor, so typing is cheap and only moving the cursor pays for a shift.

Deleting while looping forward skips elements

Writing for (i in 0 until size) { if (a[i] == x) deleteAt(a, size, i) } silently misses matches. After the shift, the element that was at i + 1 has moved into slot i, and the loop has already advanced past it, so two matches in a row only lose one. Iterate backwards, or do not advance i on a delete. Better still, sweep once with two pointers and copy the keepers forward, which removes everything in a single O(n) pass instead of one O(n) shift per removal.

Clearing the vacated slot is not tidiness, it is a leak fix

deleteAt writes null into the last slot after shifting. If you only decrement the size and leave the stale reference behind, the array is still holding a live pointer to an object the program has logically thrown away, and a garbage collector cannot free it. The array stays as large as it ever was, so the leak grows with the high-water mark, not the current contents. This is the classic bug in a hand-rolled stack or list class.