In a method of operating a data storage device including a non-volatile memory device, which includes a closed memory block and an open memory block, a scan pointer and a map scan information of the open memory block is generated. The scan pointer indicates a page next to a page to which a writing operation is completed. The map scan information includes a logical address information mapped in a page of the open memory block. When the data storage device is recovered from a power loss, the logical address information is read based on the map scan information. An address map is rebuilt based on the read logic address information.