The uncertainty of measurements and map features in quantity, as well as Data Association (DA) between measurements and map features, are two prevalent challenges in Simultaneous Localization and Mapping (SLAM). By leveraging Random Finite Set (RFS) theory, SLAM can be naturally formulated as a complete Bayesian estimation problem. In this article, we begin by performing a recursive Bayesian estimator to propagate the joint probability density of the platform’s pose and map, and then derive the marginal probability densities for the pose and map individually. Thus, we propose a Pose and Map Alternating Update (PMAU)-SLAM, which achieves favorable linear computational complexity with respect to the number of landmarks in the Field-of-View (FOV). This approach maintains a single probabilistic representation of the map, avoiding the need for multiple parallel maps fusion, as typically required by a particle-based SLAM method. We consider the propagation of the Probability Hypothesis Density (PHD) for the map RFS and the pose probability density, leading to the derivation of the PHD-PMAU-SLAM method. The labeled and unlabeled Gaussian Mixture (GM)-PHD-PMAU-SLAM algorithms are introduced, in which GM models, the Unscented Kalman Filter (UKF) and Covariance Intersection (CI) are used to address PHD approximation, nonlinear filtering, and pose fusion, respectively. Experimental results on both simulated and real-world datasets demonstrate that the proposed methods improve the accuracy and robustness of landmark-based SLAM in cluttered environments while remaining computationally efficient.