Arrays and dynamic arrays

An array keeps items in consecutive slots, so the address of item i is simple arithmetic and reading or replacing it takes Θ(1). Inserting or removing anywhere but the end means shifting every item after it, and a fixed-size array has to be reallocated to grow. A dynamic array keeps spare capacity: when it fills up it allocates Θ(n) extra slots and copies across, so one append occasionally costs Θ(n) but appends are Θ(1) amortized. Python’s complexity notes put it plainly: the largest costs come from growing past the current allocation, or from inserting or deleting near the beginning, “because everything after that must move”.

This is the default container nearly everywhere. Python’s list is a variable-length array of references, not a linked list. Java’s ArrayList runs get and set in constant time and add in amortized constant time. C++’s std::vector gives O(1) random access, amortized O(1) insertion and removal at the end, and linear cost elsewhere. Rust’s Vec is the one its docs tell you to “probably just use”. Go’s slices grow by copying into a larger array, which is “how dynamic array implementations from other languages work behind the scenes”. When you know the final size, reserve it up front (Vec::with_capacity, std::vector::reserve, make([]T, 0, n)) to skip the copies.

Keeping the array sorted buys O(log n) search by binary search (bisect in Python, slices.BinarySearch in Go), but each insert still costs O(n). Python’s bisect docs warn that the O(log n) search is dominated by the slow O(n) insertion step. For many inserts into sorted data, use a search tree.