Arrays and Strings

An array keeps its elements in one block of adjacent cells and finds each by its position, and a string is an array of characters that cannot be changed in place. It matters because most other structures are built on an array or measured against one, and the costs below decide where it is the right choice. The topic starts with how an index becomes a memory address, in one and two dimensions, and why inserting at the front moves every element. It then shows how a dynamic array grows by doubling, why appending stays O(1) amortised although one append copies everything, and builds one in Python, Java and TypeScript. It ends with strings, where adding in a loop copies the whole text each time and one join keeps it linear. The structure that trades the instant read for cheap inserts belongs to Linked Lists.