Singly-linked list/Element removal: Difference between revisions
m →{{header|Fortran}}: Clarify knowledge about the linked-list. |
m →{{header|Fortran}}: Record counting. |
||
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. |
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. |
||
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. |
Revision as of 11:23, 21 March 2017
- Task
Define a method to remove an element from a singly-linked list and demonstrate its use.
You may wish to use the link element defined in Singly-Linked List (element) for the purposes of this task.
Fortran
This sort of thing has long been done in Fortran via the standard trick of fiddling with arrays, and using array indices as the equivalent of the memory addresses of nodes. The task makes no mention of there being any content associated with the links of the linked-list; this would be supplied via auxiliary arrays or disc file records, etc. With F90 and later, one can define compound data aggregates, so something like LL.NEXT would hold the link to the next element and LL.STUFF would hold the cargo, with LL being an array of such a compound entity rather than separate simple arrays such as LLNEXT and LLSTUFF.
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.
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.
CONTAINS !Demonstration only! SUBROUTINE LLREMOVE(LINK,X) !Remove entry X from the links in LINK. INTEGER LINK(0:) !The links. INTEGER X !The "address" or index, of the unwanted one. INTEGER IT !A stepper. IT = 0 !This list element fingers the start of the list.. DO WHILE(LINK(IT).GT.0) !While a live follower, IF (LINK(IT).EQ.X) THEN !Is that follower unwanted? LINK(IT) = LINK(LINK(IT)) !Yes! Step over it! RETURN !Done. Escape! END IF !But if the follower survives, IT = LINK(IT) !Advance to finger it. END DO !And try afresh. END SUBROUTINE LLREMOVE !No checks for infinite loops!
SUBROUTINE LLFOLLOW(LINK) !Show the sequence. INTEGER LINK(0:) !The links. IT = 0 !Start by fingering the head. WRITE (6,1) "Head",IT,LINK(IT) !Show it. 1 FORMAT (A6,I3," -->",I3) !This will do. 2 IT = LINK(IT) !Advance. IF (IT.LE.0) RETURN !Done yet? WRITE (6,1) "at",IT,LINK(IT) !Nope. Show. GO TO 2 !And try afresh. END SUBROUTINE LLFOLLOW !No checks for infinite loops! END MODULE SIMPLELINKEDLIST !A bit trickier with bidirectional links.
PROGRAM POKE USE SIMPLELINKEDLIST !Just so. INTEGER LINK(0:5) !This will suffice. DATA LINK/3, 2,4,1,5,0/ !Set the head and its followers.
WRITE (6,*) "A linked-list, no cargo." CALL LLFOLLOW(LINK)
WRITE (6,*) "The element at one suffers disfavour." CALL LLREMOVE(LINK,1) CALL LLFOLLOW(LINK)
WRITE (6,*) "Off with the head!" CALL LLREMOVE(LINK,LINK(0)) !LINK(0) fingers the head element. CALL LLFOLLOW(LINK)
WRITE (6,*) "And off with the tail." CALL LLREMOVE(LINK,5) !The tail element is not tracked. CALL LLFOLLOW(LINK) !But, I know where it was, in this example.
END</lang>
Output:
A linked-list, no cargo. Head 0 --> 3 at 3 --> 1 at 1 --> 2 at 2 --> 4 at 4 --> 5 at 5 --> 0 The element at one suffers disfavour. Head 0 --> 3 at 3 --> 2 at 2 --> 4 at 4 --> 5 at 5 --> 0 Off with the head! Head 0 --> 2 at 2 --> 4 at 4 --> 5 at 5 --> 0 And off with the tail. Head 0 --> 2 at 2 --> 4 at 4 --> 0
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-allocated pieces of storage, such storage should be diligently de-allocated for potential re-use later.
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 LINK(X) = LINK(LINK(X))
, 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), or, is it the element whose cargo matches X?
The code involves repeated mention of LINK(IT)
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..
1 NEXT = LINK(IT) !This is the node of interest. IF (NEXT.GT.0) THEN !Is it a live node? IF (NEXT.EQ.X) THEN !Yes. Is it the unwanted one? LINK(IT) = LINK(NEXT) !Yes! Step over it! RETURN !Done. Escape! END IF !But if the follower survives, IT = NEXT !Advance to finger it. GO TO 1 !And try afresh. 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? LINK(IT) = LINK(NEXT) !Yes! Step over it! RETURN !Done. Escape! END IF !But if not, IT = NEXT !Advance to the follower. END DO !Ends when node IT's follower is null.
</lang> No label, no nasty literal GO TO - even though an "END DO" hides one.
Kotlin
<lang scala>// version 1.1.1
class Node<T: Number>(var data: T, var next: Node<T>? = null) {
override fun toString(): String { val sb = StringBuilder(this.data.toString()) var node = this.next while (node != null) { sb.append(" -> ", node.data.toString()) node = node.next } return sb.toString() }
}
fun <T: Number> insertAfter(prev: Node<T>, new: Node<T>) {
new.next = prev.next prev.next = new
}
fun <T: Number> remove(first: Node<T>, removal: Node<T>) {
if (first === removal) first.next = null else { var node: Node<T>? = first while (node != null) { if (node.next === removal) { val next = removal.next removal.next = null node.next = next return } node = node.next } }
}
fun main(args: Array<String>) {
val b = Node(3) val a = Node(1, b) println("Before insertion : $a") val c = Node(2) insertAfter(a, c) println("After insertion : $a") remove(a, c) // remove node we've just inserted println("After 1st removal : $a") remove(a, b) // remove last node println("After 2nd removal : $a")
}</lang>
- Output:
Before insertion : 1 -> 3 After insertion : 1 -> 2 -> 3 After 1st removal : 1 -> 3 After 2nd removal : 1
Visual Basic .NET
The contract requirement for these functions is:
- that the entry to be removed is not Nothing - the entry is present in the list. - the list Head is not Nothing
The contract ensures:
- The entry has been removed.
<lang vbnet>
Module Module1
Public Class ListEntry Public value As String Public [next] As ListEntry End Class
Public Head As ListEntry
<summary> Straight translation of Torvalds' tasteless version. </summary> <param name="entry"></param> Sub RemoveListEntryTasteless(entry As ListEntry)
Dim prev As ListEntry = Nothing Dim walk = Head
' Walk the list While walk IsNot entry prev = walk walk = walk.next End While
' Remove the entry by updating the head or the previous entry. If prev Is Nothing Then Head = entry.next Else prev.next = entry.next End If End Sub
<summary> Straight translation of Torvalds' tasteful version. </summary> <param name="entry"></param> Sub RemoveListEntryTastefull(entry As ListEntry)
Dim indirect = New ListEntry indirect.next = Head
' Walk the list looking for the thing that points at the thing that we ' want to remove. While indirect.next IsNot entry indirect = indirect.next End While
' ... and just remove it. indirect.next = entry.next
End Sub
End Module
</lang>