Imagine a rocket assembled from stages, with each stage pointing to the next through a `nextstage` field. That chain is a linked list: to reach a later stage, you follow links from the first. An array instead supports direct access by index. section 12.6 section 12.6.1
The choice matters when accessing or changing the collection:
- Indexing into a linked list requires walking through preceding elements. A stage lookup at index `i` loops through `nextstage`, making lookup O(n); array lookup is O(1). section 12.6
- Adding or removing the first linked element is fast. Arrays offer faster arbitrary indexed access, while insertion is quick mainly at the end. section 12.6.1 section 12.8
- A chain needs a clear endpoint. An `EmptyPayload` can terminate a chain of stages, and a `SpaceVehicle` wrapper can hold the first stage so that changing the head is straightforward. section 12.6.1
Adding and removing a stage
For a `SpaceVehicle` whose `activestage` holds the head, `pushfirst!(ship, stage)` links the new stage to the old head, then makes it the head. `popfirst!(ship)` returns the old head, detaches it, and advances the wrapper to the next stage. The linked stage must be mutable because these operations change its `nextstage` field. section 12.6.1
Listing 12.29 Adding a stage to the bottom
function pushfirst!(ship::SpaceVehicle, r::StagedRocket)
r.nextstage = ship.activestage #1
ship.activestage = r #2
ship
end
The `pushfirst!` implementation shows both links that must change: the new stage’s `nextstage` and the wrapper’s `activestage`. section 12.6.1
A linked structure can still act like a Julia collection. Implementing iteration lets a staged rocket work with functions such as `map`, `sum`, and `collect`; declaring `IteratorSize` as `SizeUnknown` avoids promising a cheap length calculation. Linked lists are rarely the best general replacement for arrays, but the same idea of linking elements also appears in trees and graphs. section 12.5.1 section 12.7
