Theory

How a slice actually works

In lesson 1 you used a []Item for the library and did not think about it. Now think about it, because every structure that follows is measured against this one.

What a slice variable actually holds

A Go slice is not an array. It is a three-field header that points at one:

Field What it means
pointer where the real array starts in memory
len how many elements are in use right now
cap how many fit before the array has to move

On a 64-bit machine that header is 24 bytes — three eight-byte fields. Remember that number; it turns up in a real system in step 3.

What each operation costs

Operation Cost Why
lib[i] O(1) address = start + i × size. One multiply.
append when len < cap O(1) writes into room it already has
append when len == cap O(n) new array, and everything is copied
insert / delete in the middle O(n) every later element shifts

Two of those rows are uncomfortable, and both matter later:

Inserting into the middle is O(n). Not because finding the spot is slow — you already know where it goes — but because an array stores elements back to back, and there is no room in the middle until you push everything else along. Lesson 3 builds a structure that never has to.

append sometimes costs O(n). But not often. How often is not something you will guess — it is something you will measure.

Amortized O(1)

append is described as "amortized O(1)": constant time on average, even though individual calls are expensive.

"Amortized" means averaged over many operations, not "usually fast". And it means the average is constant — not that the constant is small. In step 2 you will find out what it actually is.