Singly-linked list/Element removal: Difference between revisions
Content deleted Content added
→{{header|Fortran}}: Ah, zero-based indexing. |
→{{header|Fortran}}: A full file scheme. |
||
Line 12: | Line 12: | ||
F90 offers further opportunities, whereby instead of LL being an array of some size defined before it is used, it would instead consist of single items each containing the cargo for one item plus a link to the address of another item, with items allocated as the need arises. This however involves a lot of additional syntax and lengthy words such as ALLOCATE, all distracting from the exhibition of a solution, which is simple... |
F90 offers further opportunities, whereby instead of LL being an array of some size defined before it is used, it would instead consist of single items each containing the cargo for one item plus a link to the address of another item, with items allocated as the need arises. This however involves a lot of additional syntax and lengthy words such as ALLOCATE, all distracting from the exhibition of a solution, which is simple... |
||
For convenience, rather than have the "head" pointer to the first or head element of the linked list be a separate variable, it is found as element zero of the LIST array that holds the links. Because this element is accessible in the same way as the other links in the array representing the linked-list, no special code is needed when it is the head entry that is to be removed and thus it is the pointer to it that must be changed. However, defining arrays starting at index zero is a feature of F90, and having subroutines recognise that their array parameter starts at index zero requires the MODULE protocol. Previously, arrays started with index one, and the code would just have to recognise this with the appropriate offsets. Thus, the first element available for an item would be at index two, not one, and so forth. On the other hand, the zero element just needs its link, and any associated cargo would represented wasted storage. If that cargo were to be held in a disc file there would be no such waste, as record numbers start with one, not zero. But, if the linked-list is to be stored entirely in a disc file, the first record has to be reserved to hold the link to the head record and the first available storage record is number two, just as with an array starting at one, not zero. |
For convenience, rather than have the "head" pointer to the first or head element of the linked list be a separate variable, it is found as element zero of the LIST array that holds the links. Because this element is accessible in the same way as the other links in the array representing the linked-list, no special code is needed when it is the head entry that is to be removed and thus it is the pointer to it that must be changed. However, defining arrays starting at index zero is a feature of F90, and having subroutines recognise that their array parameter starts at index zero requires the MODULE protocol. Previously, arrays started with index one, and the code would just have to recognise this with the appropriate offsets. Thus, the first element available for an item would be at index two, not one, and so forth. On the other hand, the zero element just needs its link, and any associated cargo would represented wasted storage. If that cargo were to be held in a disc file there would be no such waste, as record numbers start with one, not zero. But, if the linked-list is to be stored entirely in a disc file, the first record has to be reserved to hold the link to the head record and the first available storage record is number two, just as with an array starting at one, not zero. Indeed, a more comprehensive solution would probably reserve the first record as a header, containing a finger to the start of the linked-list, another finger to the start of the "available" (i.e. deleted and thus reusable) linked-list of records, and a record counter to identify the last record in the file so that if the "available" list is empty, the file can be extended by one record to hold a new entry. |
||
Having a value of zero signify that there is no follower is the obvious choice for ending a linked-list. When addresses are being tossed about, this might be dressed up via words such as NULL rather than a literal zero just in case a "null address" does not manifest as a zero value. <lang Fortran> MODULE SIMPLELINKEDLIST !Play with an array. Other arrays might hold content. |
Having a value of zero signify that there is no follower is the obvious choice for ending a linked-list. When addresses are being tossed about, this might be dressed up via words such as NULL rather than a literal zero just in case a "null address" does not manifest as a zero value. <lang Fortran> MODULE SIMPLELINKEDLIST !Play with an array. Other arrays might hold content. |