Singly-linked list/Element removal
- 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.
ALGOL W
Uses the ListI record from the Singly Linked List task. <lang algolw>
% deletes the specified element from the list %
% if the element to remove is null or not in the list, %
% nothing happens %
procedure Remove( reference(ListI) value result list
; reference(ListI) value element
) ;
if element not = null then begin
% have an element to remove %
if list = element then % remove the head % list := next(list)
else begin
% not removing the head element %
Reference(ListI) listPos;
listPos := list;
while listPos not = null and next(listPos) not = element do listPos := next(listPos);
if listPos not = null then % found the element % next(listPos) := next(next(listPos))
end
end Remove ;
% declare a ListI list % reference(ListI) head;
% ... add some elements to the list here ... %
% remove the third element from a list % Remove( head, next(next(head)) );
% remove the first element from a list % Remove( head, head );
</lang>
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. 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.
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. Alternatively, use "FROM" for IT and "IT" for NEXT, being careful to keep it straight.
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.2
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>