We present a detailed discussion of our novel diagrammatic coupled cluster Monte Carlo (diagCCMC) [Scott et al. J. Phys. Chem. Lett. 10, 925 (2019)]. The diagCCMC algorithm performs an imaginary-time propagation of the similarity-transformed coupled cluster Schrödinger equation. Imaginary-time updates are computed by the stochastic sampling of the coupled cluster vector function: each term is evaluated as a randomly realized diagram in the connected expansion of the similarity-transformed Hamiltonian. We highlight similarities and differences between deterministic and stochastic linked coupled cluster theory when the latter is re-expressed as a sampling of the diagrammatic expansion and discuss details of our implementation that allow for a walker-less realization of the stochastic sampling. Finally, we demonstrate that in the presence of locality, our algorithm can obtain a fixed errorbar per electron while only requiring an asymptotic computational effort that scales quartically with system size, independent of the truncation level in coupled cluster theory. The algorithm only requires an asymptotic memory cost scaling linearly, as demonstrated previously. These scaling reductions require no ad hoc modifications to the approach.