Neither ancient Rome nor Sparta had walls for centuries after their rise to prominence. A number of per-Colombian Andean cities didn't have walls. Tenochtitlan didn't have walls and it doesn't look like Cholula did either. And in the Indus Valley Civilization Harappa and Mohenjo-daro didn't have walls.
Tenochtitlan didn't have walls because it already had natural defenses (water); so that's a particular case.
Neither of the other city states in the Aztec Triple Alliance had walls either and they weren’t built on islands.[1] They seem to have had some walled precincts to separate sacred spaces from common areas but now broader system of defensive walls. Much like Ancient Rome they had large and well organized armies.
[1] https://www.public.asu.edu/~mesmith9/1-CompleteSet/MES-SAA-0...
I'm not sure Tenochtitlan was technically a city.
The defining characteristic of a city is that it can't feed itself. (Hence the "urban" vs "rural" dichotomy.)
Correct me if I'm wrong, but Tenochtitlan was a closed system and used to have farms on the lake and the islands.