Singly-linked list/Element removal: Difference between revisions
Singly-linked list/Element removal (view source)
Revision as of 01:27, 24 December 2016
, 7 years ago→{{header|Fortran}}
Line 84:
</pre>
Although this will survive not finding a match for X and the linked-list being empty (because the link to the head is null, being zero, and LINK(0) ''is'' zero) there is no attempt to prevent infinite loops (such as when an item is linked to itself), nor checks for valid bounds to a link. Further, the unlinked element is simply abandoned. ''This is a memory leak!'' It should be transferred to some sort of "available" linked-list for potential re-use later. If instead the elements were separately
Although in this example the linked-list is held in an array, and array elements can be accessed at random, the key difficulty is that to unlink an element, the element fingering that has to be linked to the follower of the to-be-unlinked element, and to find the parent of a randomly-selected item will require a search through the links. By following the links, this information is in hand when the unwanted item is found. On the other hand, if the caller could be persuaded to identify the node to be removed by fingering the node that points to it, no chase is needed and the code becomes <code>LINK(X) = LINK(LINK(X))</code>, hardly worth the trouble of devising a subroutine - unless it added the unlinked node to an "available" list, provided checking and debugging output, ''etc''.
In messing with linked-lists, one must give close attention to just how an element is identified. Is element X (for removal) the X'th element in sequence along the linked list (first, second, third, etc.), or, is it the element at at a specified memory address or index position X in the LIST array (as here
The code involves repeated mention of <code>LINK(IT)</code> and for those who do not have total faith in the brilliance of code generated by a compiler, one could try <lang Fortran> IT = 0 !This list element fingers the start of the list..
Line 101:
END IF !So much for that node.
</lang>
The introduction of a mnemonic "NEXT" might help the interpretation of the code, but one must be careful about phase: NEXT is the "nextness" for IT which fingers node NEXT which is the candidate for matching against X, not IT. And ... there is a blatant GO TO (aside from the equivalent concealed via RETURN) but using a WHILE-loop would require a repetition of NEXT = LINK(IT). If Fortran were to enable assignment within an expression (as in Algol) then <lang Fortran> IT = 0 !This list element fingers the start of the list..
DO WHILE((NEXT = LINK(IT)).GT.0) !Finger the follower of IT.
IF (NEXT.EQ.X) THEN !Is it the unwanted one?
| |||