An apparatus of recording data on a recording medium includes a pickup unit and a microcomputer. The pickup unit records data in a plurality of data frames included in a cluster. The microcomputer controls the pickup unit to record status information within the cluster, which indicates a status of the data being recorded in each data frame. In addition, the microcomputer further controls the pickup unit to record previous location information within the cluster when the cluster is determined to be a replacement cluster. The previous location information indicates a previous location of an original cluster associated with the replacement cluster.