Imagine keeping your to-dos in numbered drawers. An array puts the items right next to one another in memory, so you can go straight to the drawer you want. Its positions start at 0: the first item is at position 0, the second at position 1, and so on. section 2.1 section 2.2 section 1.4
Finding an item
Suppose five items occupy consecutive slots starting at address 00. You can work out where the fifth item is: address 04. A linked list cannot offer that same direct jump; you must follow links from one item to the next. This is why arrays are useful when you need to read items in no particular order. section 2.4 section 2.8
What happens when your to-do list changes?
- Adding an item may require moving the whole array to a larger, contiguous space. Reserving extra slots avoids some moves, but unused slots can waste memory—and you might still run out. section 2.2
- Inserting a task in the middle means shifting the items after it. A linked list can instead change which item the previous one points to. section 2.6
Arrays provide random access: you can jump directly to an item rather than read every earlier item. Their neighboring items can also make reading a run of items faster through caching. Choose based on the job: arrays favor reads, while linked lists favor inserts and deletes. section 2.8 section 2.11
mid = (low + high) // 2 #1 guess = arr[mid]
In this Python binary-search example, `mid` selects a position and `arr[mid]` reads the item there. Binary search requires the array to be sorted. section 1.4 section 2.0
