A memory controller for controlling a memory device which stores logical-to-physical (L2P) segments includes a map data storage and a map manager. The map data storage stores a plurality of physical-to-logical (P2L) segments including mapping information between a physical address of the memory device in which write data is to be stored and a logical address received from a host, in response to a write request received from the host. The map manager updates the L2P segments stored in the memory device, based on target P2L segments corresponding to a write command provided to the memory device, which have a higher priority than the other P2L segments among the plurality of P2L segments. Each of L2P segments includes mapping information between a logical address and a physical address of data stored in the memory device.