This invention provides a method of creating and recording presentation order management information for a rewritable recording medium, which enables effective control of the amount of the presentation order management information needed when a user edits preferred play lists of recorded data. In the present invention, each time a new play list is made by a user, a user-defined program chain is created, wherein presentation order information units for defining presentation order of user-chosen data are contained. The maximum number of user-defined program chains and the total number of presentation order information units are limited. When editing of a new play list is requested, the number of user-defined program chains created so far and the total number of presentation order information units contained in all the user-defined program chains are checked. The method allows editing of data depending upon the check result, thereby enabling effective control of the size for presentation order management data in the limited maximum size for navigation data.