This work addresses the superdiffusive motion of a discrete time random walker on ordered discrete substrates and complex networks with the presence of long-range interactions (LRIs). In ordered regular lattices, where LRIs have a clear geometrical meaning, their presence allow for hoppings between more distant sites, yet with a smaller probability. In such cases, it is found that LRIs do not affect the dependency of the mean square displacement (MSD) traveled by the walker: exact analytical results for the the cycle graph within the Markov chain framework shows that MSD follows the same linearly increasing behavior with time when LRIs are absent, independently of the strength of LRI. This contrasts with the superdiffusive scenario in complex networks. When they have very short diameter ($\sim \log N$), the analysis of the time dependency of MSD becomes quite difficult, as it saturates very quickly even when LRIs are absent. The presence of a faster than linearly increasing growth phase can be noticed, but it can hardly be measured with precision. This effect is sidestepped on small-world Newman-Watts (NW) networks, where the network diameter can be controlled by the number of new links (shortcuts) that are added to the cycle graph. The time duration $t_f$ of the superdiffusive regime and the power law exponent can be adequately evaluated by numerical methods. They depend on the number of nodes and shortcuts, as well as the strength of LRIs. Although the later causes a strong reduction in $t_f$ when shortcuts are present, their presence by itself is not sufficient to trigger a superdiffusive behavior., Comment: 30 pages, 13 figures