We present the explicit form of the symplectic structure of anti-self-dual Yang-Mills (ASDYM) equations in Yang's J- and K-gauges in order to establish the bi-Hamiltonian structure of this completely integrable system. Dirac's theory of constraints is applied to the degenerate Lagrangians that yield the ASDYM equations. The constraints axe second class as in the case of all completely integrable systems which stands in sharp contrast to the situation in full Yang-Mills theory. We construct the Dirac brackets and the symplectic 2-forms for both J- and K-gauges. The covariant symplectic structure of ASDYM equations is obtained using the Witten-Zuckerman formalism. We show that the appropriate component of the Witten-Zuckerman closed and conserved 2-form vector density reduces to the symplectic 2-form obtained from Dirac's theory. Finally, we present the Backlund transformation between the J- and K-gauges in order to apply Magri's theorem to the respective two Hamiltonian structures.