We present a new method (LinK) to form the exact exchange matrix, as needed in Hartree-Fock and hybrid density functional theory calculations, with an effort capable of scaling only Linearly with molecular size. It preserves the highly optimized structure of conventional direct self-consistent held (SCF) methods with only negligible prescreening overhead and does not impose predefined decay properties. Our LinK method leads to very early advantages as compared to conventional methods for systems with larger band gaps. Due to negligible screening overhead it is also competitive with conventional SCF schemes both for small molecules and systems with small band gaps. For the formation of an exchange-type matrix in coupled perturbed SCF theory our LinK method can exhibit sublinear scaling, or more precisely, independence of the computational effort from molecular size.