Lesson 2 of 14

Arrays and References

Numbered lockers let you go straight to locker 12. An array works similarly: each item has a position, called an index, that lets you access it directly.

What arrays do well

• A conventional array uses equal-sized slots in contiguous memory. Its starting address and slot size determine an item’s position.
• Python’s list uses a resizable array implementation. Each slot holds a reference to a Python object.
• Indexes start at 0. Three items occupy positions 0, 1, and 2.

scores = [72, 88, 91]
print(scores[1])
scores.insert(1, 80)
print(scores)

This prints 88, then [72, 80, 88, 91]. Inserting 80 at position 1 requires shifting the following items one place to the right.

Indexed access is O(1); insertion or deletion in the middle is O(n) in the worst case. Adding at the end with append is O(1) when averaged across a sequence of operations. This is called an amortized cost. A single append that expands storage can take O(n).

Does another name create a copy?

original = [10, 20]
shared = original
copied = original.copy()
shared[0] = 99
print(original)
print(copied)

The results are [99, 20] and [10, 20]. Both shared and original refer to the same list. The copy() method makes a new outer list. If it contains other lists, those inner objects remain shared: this is a shallow copy.

C pointers work with memory addresses. Python expresses relationships through object references without direct address arithmetic. We will use references to connect the next item in a linked list.

Check your understanding

You frequently insert at the beginning of an array. Does fast indexed access alone make it a good choice?

Python documentation: Lists