Singly-linked list/Element removal

Singly-linked list/Element removal is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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.

Having a value of zero signify that there is no follower is the obvious choice for ending a linked-list. <lang Fortran> MODULE SIMPLELINKEDLIST !Play with an array. Other arrays might hold content.

      CONTAINS			!Demonstration only!
       SUBROUTINE LLREMOVE(LIST,X)	!Remove entry X from the links in LIST.
        INTEGER LIST(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(LIST(IT).GT.0)	!While a live follower,
           IF (LIST(IT).EQ.X) THEN		!Is that follower unwanted?
             LIST(IT) = LIST(LIST(IT))		!Yes! Step over it!
             RETURN				!Done. Escape!
           END IF			!But if the follower survives,
           IT = LIST(IT)		!Advance to finger it.
         END DO		!And try afresh.
       END SUBROUTINE LLREMOVE	!No checks for infinite loops!

       SUBROUTINE LLFOLLOW(LIST)	!Show the sequence.
        INTEGER LIST(0:)	!The links.
         IT = 0			!Start by fingering the head.
         WRITE (6,1) "Head",IT,LIST(IT)	!Show it.
   1     FORMAT (A6,I3," -->",I3)		!This will do.
   2     IT = LIST(IT)		!Advance.
         IF (IT.LE.0) RETURN		!Done yet?
         WRITE (6,1) "at",IT,LIST(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 LIST(0:5)		!This will suffice.
     DATA LIST/3, 2,4,1,5,0/	!Set the head and its followers.

     WRITE (6,*) "A linked-list, no cargo."
     CALL LLFOLLOW(LIST)

     WRITE (6,*) "The element at one suffers disfavour."
     CALL LLREMOVE(LIST,1)
     CALL LLFOLLOW(LIST)

     WRITE (6,*) "Off with the head!"
     CALL LLREMOVE(LIST,3)
     CALL LLFOLLOW(LIST)

     WRITE (6,*) "And off with the tail."
     CALL LLREMOVE(LIST,5)
     CALL LLFOLLOW(LIST)

     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

The example makes 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.

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 index position X in the LIST array as here or at a specified memory address, or, is it the element whose cargo matches X?

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>