In this correspondence, we concern the bearing estimation problem of linearly periodic arrays with the presence of sensor position errors. Conventional approaches for solving this problem generally consist of two steps, first calibrating sensor locations and then per-forming bearing estimation based on the calibrated sensor locations. In this correspondence, we propose approaches to carrying out bearing estimation based on the Toeplitz and eigenstructure reconstruction of the covariance matrix without the need for calibration. The Toeplitz approximation method (TAM) and a modification of it (MTAM) are used to reconstruct a matrix with Toeplitz structure. To further enhance the capabilities of the TAM and MTAM, an iterative algorithm incorporating with the TAM (ITAM) and the MTAM (IMTAM) is proposed to iteratively reconstruct both the Toeplitz and the desired eigenstructure from the observed covariance matrix. Computer simulations show that the MTAM is more effective than the TAM. Moreover, the iterative methods are superior to the noniterative ones at the price of computations.