To investigate the formation mechanism of a physically cross-linked double-network hydrogel and its application as a framework for nanomaterial, in this work, calcium alginate and polyvinyl alcohol (PVA) were selected as hydrogel-forming polymers to form a double-network hydrogel utilized as a framework for graphene oxide (GO). The results showed that completely physically cross-linked double-network hydrogels were obtained with good shape-recovery and self-healing properties. Moreover, the first network had a significant influence on the properties of double networks: when calcium alginate acts as the first network, the hydrogels have denser structures, a lower swelling ratio and higher mechanical properties. The GO/double-network composite hydrogel shows a 3D porous network structure with no obvious aggregation of GO nanosheets and an excellent removal rate for methylene blue. The results indicate the potential of the polymer double network utilized as a nanomaterial framework in biomedical and environmental areas.