  We prove that strong structural controllability of a pair of structural
matrices $(\mathcal{A},\mathcal{B})$ can be verified in time linear in $n + r +
\nu$, where $\mathcal{A}$ is square, $n$ and $r$ denote the number of columns
of $\mathcal{A}$ and $\mathcal{B}$, respectively, and $\nu$ is the number of
non-zero entries in $(\mathcal{A},\mathcal{B})$. We also present an algorithm
realizing this bound, which depends on a recent, high-level method to verify
strong structural controllability and uses sparse matrix data structures.
Linear time complexity is actually achieved by separately storing both the
structural matrix $(\mathcal{A},\mathcal{B})$ and its transpose, linking the
two data structures through a third one, and a novel, efficient scheme to
update all the data during the computations. We illustrate the performance of
our algorithm using systems of various sizes and sparsity.
