Singly-linked list/Element removal: Difference between revisions

From Rosetta Code
Content added Content deleted
Line 335: Line 335:
It will be freed back into the heap. The type notation
It will be freed back into the heap. The type notation
‘(v : int)’ is because (perhaps due to an overload of the
‘(v : int)’ is because (perhaps due to an overload of the
‘=’ operator) the typechecker had difficulty determining its
‘=’ operator) the typechecker had difficulty determining the
type. *)
type of v. *)
| ~(v :: tail) when (v : int) = x =>
| ~(v :: tail) when (v : int) = x =>
(* The first element matches. Replace the list with its tail. *)
(* The first element matches. Replace the list with its tail. *)

Revision as of 22:38, 21 March 2022

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.
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.

See also




Action!

The user must type in the monitor the following command after compilation and before running the program!

SET EndProg=*
Library: Action! Tool Kit

<lang Action!>CARD EndProg ;required for ALLOCATE.ACT

INCLUDE "D2:ALLOCATE.ACT" ;from the Action! Tool Kit. You must type 'SET EndProg=*' from the monitor after compiling, but before running this program!

DEFINE PTR="CARD" DEFINE NODE_SIZE="4" TYPE ListNode=[PTR data,nxt]

ListNode POINTER listBegin

PTR FUNC FindLast() 

 ListNode POINTER last
 
 last=listBegin
 IF last=0 THEN
   RETURN (0)
 FI
 WHILE last.nxt#0
 DO
   last=last.nxt
 OD

RETURN (last)

PTR FUNC FindPrev(ListNode POINTER n) 

 ListNode POINTER prev

 IF n=0 OR n=listBegin THEN
   prev=0
 ELSE
   prev=listBegin
   WHILE prev#0 AND prev.nxt#n
   DO
     prev=prev.nxt
   OD
 FI

RETURN (prev)

PROC Append(CHAR ARRAY v) 

 ListNode POINTER n,last

 n=Alloc(NODE_SIZE)
 n.data=v
 n.nxt=0
 last=FindLast()
 IF last THEN
   last.nxt=n
 ELSE
   listBegin=n
 FI

RETURN

PROC Remove(ListNode POINTER n) 

 ListNode POINTER prev,next
 
 IF n=0 THEN Break() FI

 prev=FindPrev(n)
 next=n.nxt 
 IF prev THEN
   prev.nxt=next
 ELSE
   listBegin=next
 FI

 Free(n,NODE_SIZE)

RETURN

PROC PrintList() 

 ListNode POINTER n

 n=listBegin
 Print("(")
 WHILE n
 DO
   Print(n.data)
   IF n.nxt THEN
     Print(", ")
   FI
   n=n.nxt
 OD
 PrintE(")") PutE()

RETURN

PROC TestRemove(ListNode POINTER n) 

 PrintF("Remove ""%S"":%E",n.data)
 Remove(n)
 PrintList()

RETURN

PROC Main() 

 ListNode POINTER p
 Put(125) PutE() ;clear screen
 
 AllocInit(0)
 listBegin=0

 Append("First")
 Append("Second")
 Append("Third")
 Append("Fourth")
 Append("Fifth")
 PrintList()

 TestRemove(listBegin.nxt)
 p=FindLast()
 p=FindPrev(p)
 TestRemove(p)
 TestRemove(listBegin)
 p=FindLast()
 TestRemove(p)
 TestRemove(listBegin)

RETURN</lang>

Output:

Screenshot from Atari 8-bit computer 

(First, Second, Third, Fourth, Fifth)

Remove "Second":
(First, Third, Fourth, Fifth)

Remove "Fourth":
(First, Third, Fifth)

Remove "First":
(Third, Fifth)

Remove "Fifth":
(Third)

Remove "Third":
()

ALGOL 68

Using the STRINGLIST from the Singly-linked list Element traversal task.

Translation of: ALGOL_W

<lang algol68># removes the specified element from the list, modifying list if necessary # PRIO REMOVE = 1; OP REMOVE = ( REF STRINGLIST list, REF STRINGLIST element )REF STRINGLIST: 

    IF element ISNT REF STRINGLIST(NIL) THEN
        # have an element to remove #
        IF REF STRINGLIST(list) IS REF STRINGLIST(element) THEN
            # remove the head #
            list := next OF list
        ELSE
            # not removing the head element #
            REF STRINGLIST list pos := list;
            WHILE IF   REF STRINGLIST(list pos) IS REF STRINGLIST(NIL) THEN FALSE
                  ELSE REF STRINGLIST(next OF list pos) ISNT REF STRINGLIST(element)
                  FI
            DO
                list pos := next OF list pos
            OD;
            IF REF STRINGLIST(list pos) ISNT REF STRINGLIST(NIL) THEN
                # found the element #
                next OF list pos := next OF next OF list pos
            FI
        FI;
        list
    ELSE
        list
    FI # REMOVE # ;

MODE STRINGLIST = STRUCT(STRING value, REF STRINGLIST next); STRINGLIST list := ("Big", 

   LOC STRINGLIST := ("fjords",
     LOC STRINGLIST := ("vex",
       LOC STRINGLIST := ("quick",
         LOC STRINGLIST := ("waltz",
           LOC STRINGLIST := ("nymph",NIL))))));
  1. remove the third and then the first element from the STRINGLIST #

( list REMOVE next OF next OF list ) REMOVE list;

</lang>

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>

ATS

I repeated the ‘Rosetta Code linear list type’ here, so you can simply copy the code below, compile it, and run it.

Also I put the executable parts in initialization rather than the main program, to avoid being forced to ‘consume’ the list (free its memory). I felt that would be a distraction.

The deletion routine below may be surprisingly involved. Keep in mind, however, that deleting a node means altering the node that comes before it. Thus one has to look ahead in the list, to see whether you have gotten to the right place. Also, unless your list structure includes a ‘phony’ first node (which is sometimes done), you have to handle a match with the first node specially.

The deletion routine presented here proves that the result is the same length or one node shorter than the original. Also the search is proven to terminate.

<lang ATS>(*------------------------------------------------------------------*)

(* The Rosetta Code linear list type can contain any vt@ype. 

  (The ‘@’ means it doesn’t have to be the size of a pointer.
  You can read {0 <= n} as ‘for all non-negative n’. *)

dataviewtype rclist_vt (vt : vt@ype+, n : int) = | rclist_vt_nil (vt, 0) | {0 <= n} rclist_vt_cons (vt, n + 1) of (vt, rclist_vt (vt, n))

(* A lemma one will need: lists never have negative lengths. *) extern prfun {vt : vt@ype} lemma_rclist_vt_param 

         {n : int}
         (lst : !rclist_vt (vt, n)) :<prf> [0 <= n] void

(* Proof of the lemma. *) primplement {vt} lemma_rclist_vt_param lst = 

 case+ lst of
 | rclist_vt_nil () => ()
 | rclist_vt_cons _ => ()

(*------------------------------------------------------------------*)

(* For simplicity, the Rosetta Code linear list deletion routine will 

  be specifically for lists of ‘int’. *)

(* Some things that will be needed. *)

  1. include "share/atspre_staload.hats"

(* The list is passed by reference and will be overwritten with 

  the new list. It will be proven that the new list is either
  equal in length to the original or exactly one node shorter
  than it.
    (One might notice that in type expressions the equals sign
  is ‘==’, even though in executable code it is ‘=’. There are
  two distinct sublanguages; to my knowledge, this is merely how
  the operators happen to be assigned in each sublanguage, within
  the compiler’s prelude.) *)

extern fun rclist_int_delete 

         {m   : int}                   (* ‘for all list lengths m’ *)
         (lst : &rclist_vt (int, m) >> (* & = pass by reference *)
                  (* The new type will be a list of the same
                     length or one less. *)
                  [n : int | n == m || (m <> 0 && n == m - 1)]
                  rclist_vt (int, n),
          x   : int) : void

(* The implementation is rather involved, and it will help to have 

  some convenient notation. The :: operator is already declared
  in the compiler’s prelude as a right-associative infix operator. *)
  1. define NIL rclist_vt_nil ()
  2. define :: rclist_vt_cons

implement rclist_int_delete {m} (lst, x) = 

 let
   (* A recursive nested function that finds and deletes the node. *)
   fun
   find {k : int | 1 <= k}
        .<k>. (* Means: ‘k must uniformly decrease towards zero.’
                 If so, that is proof that ‘find’ terminates. *)
        (lst : &rclist_vt (int, k) >>
                 [j : int | j == k || j == k - 1]
                 rclist_vt (int, j),
         x   : int) : void =
     case+ lst of
     | (_ :: NIL) => ()        (* x was not found. Do nothing. *)
     | (_ :: v :: _) when v = x =>
       {
         val+ @ (u :: tl) = lst (* @ = unfold. tl will be mutable. *)
         val+ ~ (v :: tail) = tl (* ~ = consume. The v node will be
                                    freed back into the heap. *)
         val () = (tl := tail) (* Replace the u node’s tail with the
                                  shortened tail. *)
         prval () = fold@ lst  (* Refold. Using ‘prval’ rather than
                                  ‘val’ means this statement applies
                                  only to the typechecking phase. *)
       }
     | (_ :: _ :: _) =>
       {
         val+ @ (_ :: tl) = lst (* Unfold, so tl will be
                                   referenceable. *)
         val () = find (tl, x) (* Loop by tail recursion. *)
         prval () = fold@ lst  (* Refold. Using ‘prval’ rather than
                                  ‘val’ means this statement applies
                                  only to the typechecking phase. *)
       }

   (* The following is needed to prove that lst does not have a
      negative length. *)
   prval _ = lemma_rclist_vt_param lst
 in
   case+ lst of
   | NIL => ()                 (* An empty list. Do nothing. *)
   (* In the following, the ‘~’ means that the v node is consumed.
      It will be freed back into the heap. The type notation
      ‘(v : int)’ is because (perhaps due to an overload of the
      ‘=’ operator) the typechecker had difficulty determining the
      type of v. *)
   | ~(v :: tail) when (v : int) = x =>
     (* The first element matches. Replace the list with its tail. *)
     lst := tail
   | (_ :: _) => find (lst, x) (* Search in the list. *)
 end

(* Now let’s try it. *)

overload delete with rclist_int_delete

val A = 123 val B = 789 val C = 456

(* ‘var’ instead of ‘val’, to make lst a mutable variable that can be 

  passed by reference. *)

var lst = A :: C :: B :: NIL

val () = delete (lst, C)

fun loop {k : int | 0 <= k} .<k>. 

    (p : !rclist_vt (int, k)) : void =
 case+ p of
 | NIL => ()
 | head :: tail =>
   begin
     println! (head);
     loop tail
   end

prval () = lemma_rclist_vt_param lst val () = loop lst

(*------------------------------------------------------------------*)

implement main0 () = ()</lang>

Output:
$ patscc -DATS_MEMALLOC_LIBC singly_linked_list_deletion.dats && ./a.out
123
789

C

This implementation takes up integers from the command line and then asks which element has to be removed. List is printed before and after removal, usage printed on incorrect invocation. <lang C>

  1. include<stdlib.h>
  2. include<stdio.h>

typedef struct elem{ int data; struct elem* next; }cell;

typedef cell* list;

list addToList(list a,int num){

list iter, temp; int i=0;

if(a==NULL){ a = (list)malloc(sizeof(cell)); a->data = num; a->next = NULL; } else{ iter = a;

while(iter->next!=NULL){ iter = iter->next; }

temp = (list)malloc(sizeof(cell)); temp->data = num; temp->next = NULL;

iter->next = temp; } return a; }

list deleteFromList(list a,int pos){

int i=1; list temp,iter;

if(a!=NULL){ iter = a;

if(pos==1){ a = a->next; iter->next = NULL; free(iter); }

else{ while(i++!=pos-1) iter = iter->next; temp = iter->next; iter->next = temp->next; temp->next = NULL; free(temp); } } return a; }

void printList(list a){ list temp = a;

printf("List contains following elements : \n");

while(temp!=NULL){ printf("%d ",temp->data); temp = temp->next; } }

int main(int argC,char* argV[]) { list a = NULL; int i;

if(argC == 1) printf("Usage : %s <list of integers to be inserted into the list>",argV[0]); else{ for(i=2;i<=argC;i++) a = addToList(a,atoi(argV[i-1]));

printList(a);

do{ printf("\nEnter position of element to be removed (1-%d) : ",argC-1);

scanf("%d",&i);

if(i>0 && i<=argC-1){ a = deleteFromList(a,i); printList(a); } }while(i>argC-1||i<=0); } return 0; } </lang> Invocation, interaction and output : 

C:\rosettaCode>linkedList.exe 1 2 3
List contains following elements :
1 2 3
Enter position of element to be removed (1-3) : 2
List contains following elements :
1 3

C#

Tasteful & unsafe

Translation of: Taste (old version)

Semantically identical translation of Torvalds' tasteful C version using C# unsafe pointers:

<lang csharp>using System; using System.Runtime.InteropServices;

static unsafe class Program { 

   ref struct LinkedListNode
   {
       public int Value;
       public LinkedListNode* Next;
       public override string ToString() => this.Value + (this.Next == null ? string.Empty : " -> " + this.Next->ToString());
   }

   static void Remove(LinkedListNode** head, LinkedListNode* entry)
   {
       // The "indirect" pointer points to the
       // *address* of the thing we'll update

       LinkedListNode** indirect = head;

       // Walk the list, looking for the thing that
       // points to the entry we want to remove

       while (*indirect != entry)
           indirect = &(*indirect)->Next;

       // .. and just remove it
       *indirect = entry->Next;
   }

   static void Main()
   {
       // Allocate like real C!
       var head = (LinkedListNode*)Marshal.AllocHGlobal(sizeof(LinkedListNode));
       head->Value = 1;
       head->Next = (LinkedListNode*)Marshal.AllocHGlobal(sizeof(LinkedListNode));
       head->Next->Value = 2;
       head->Next->Next = null;

       LinkedListNode copy = *head;

       Console.WriteLine("original:                    " + head->ToString());

       Remove(&head, head);
       Console.WriteLine("after removing head:         " + head->ToString());

       head = ©
       Console.WriteLine("restored from copy:          " + head->ToString());

       Remove(&head, head->Next);
       Console.WriteLine("after removing second node:  " + head->ToString());
   }

}</lang>

Output:
original:                    1 -> 2
after removing head:         2
restored from copy:          1 -> 2
after removing second node:  1

C++

<lang cpp>#include <iostream>

// define a singly linked list struct link { 

 link* next;
 int data;

 link(int newItem, link* head)
 : next{head}, data{newItem}{}

};

void PrintList(link* head) { 

   if(!head) return;
   std::cout << head->data << " ";
   PrintList(head->next);

}

link* RemoveItem(int valueToRemove, link*&head) { 

   // walk the list to look for the node conaining the value including
   // the head node itself
   for(link** node = &head; *node; node = &((*node)->next))
   {
       if((*node)->data == valueToRemove)
       {
           // the item was found; remove it and return its node
           link* removedNode = *node;
           *node = removedNode->next;
           removedNode->next = nullptr;
           return removedNode;
       }
   }

   // the node was not found in the list
   return nullptr;

}

int main() { 

   // link some nodes into a list
   link link33{33, nullptr};
   link link42{42, &link33};
   link link99{99, &link42};
   link link55{55, &link99};
   link* head = &link55;

   std::cout << "Full list: ";
   PrintList(head);

   std::cout << "\nRemove 55: ";
   auto removed = RemoveItem(55, head);
   PrintList(head);
   std::cout << "\nThe removed item: ";
   PrintList(removed);

   std::cout << "\nTry to remove -3: ";
   auto removed2 = RemoveItem(-3, head);
   PrintList(head);
   if (!removed2) std::cout << "\nItem not found\n";

}</lang>

Output:
Full list: 55 99 42 33 
Remove 55: 99 42 33 
The removed item: 55 
Try to remove -3: 99 42 33 
Item not found

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.

FreeBASIC

Translation of: Yabasic

<lang freebasic>#define FIL 1

  1. define DATO 2
  2. define LINK 3

Dim Shared As Integer countNodes, Nodes countNodes = 0 : Nodes = 10 Dim Shared As Integer list(Nodes, 3)

Function searchNode(node As Integer) As Integer 

   Dim As Integer i, prevNode
   
   For i = 1 To countNodes
       If i = node Then Exit For 'break
       prevNode = list(prevNode, LINK)
   Next i
   
   Return prevNode

End Function

Sub insertNode(node As Integer, newNode As Integer, after As Integer) 

   Dim As Integer i, prevNode
   
   prevNode = searchNode(node)
   If after Then prevNode = list(prevNode, LINK)
   
   For i = 1 To Nodes
       If Not list(i, FIL) Then Exit For
   Next i
   
   list(i, FIL) = true
   list(i, DATO) = newNode
   list(i, LINK) = list(prevNode, LINK)
   list(prevNode, LINK) = i
   
   countNodes += 1
   If countNodes = Nodes Then Nodes += 10 : Redim list(Nodes, 3)

End Sub

Sub removeNode(n As Integer) 

   Dim As Integer prevNode = searchNode(n)
   Dim As Integer node = list(prevNode, LINK)
   
   list(prevNode, LINK) = list(node, LINK)
   list(node, FIL) = false
   countNodes -= 1

End Sub

Sub printNode(node As Integer) 

   Dim As Integer prevNode = searchNode(node)
   
   node = list(prevNode, LINK)
   Print list(node, DATO);
   Print

End Sub

insertNode(1, 1000, true) insertNode(1, 2000, true) insertNode(1, 3000, true)

printNode(1) printNode(2) printNode(3)

removeNode(2)

Print printNode(1) printNode(2)</lang>

Output:
1000
3000
2000

1000
2000

Go

This reuses code from other singly-linked list tasks. <lang go>package main

import "fmt"

type Ele struct { 

   Data interface{}
   Next *Ele

}

var head *Ele

func (e *Ele) Append(data interface{}) *Ele { 

   if e == nil {
       return e
   }
   if e.Next == nil {
       e.Next = &Ele{data, nil}
   } else {
       e.Next = &Ele{data, e.Next}
   }
   return e.Next

}

// Removes first element with given data value from the list. // If this is 'head' element, resets 'head' to next element. // Does nothing if data value is not present. func (e *Ele) Remove(data interface{}) { 

   if e == nil {
       return
   }
   if e.Data == data {
       if e == head {
           head = e.Next
       }
       e.Next = nil
       return
   }
   prev := e
   for iter := e.Next; iter != nil; iter = iter.Next {
       if iter.Data == data {
           prev.Next = iter.Next
           iter.Next = nil
           return
       }
       prev = iter
   }

}

func (e *Ele) String() string { 

   return fmt.Sprintf("%v", e.Data)

}

func (e *Ele) Traverse() { 

   if e == nil {
       fmt.Println(e)
       return
   }
   for iter := e; iter != nil; iter = iter.Next {
       fmt.Println(iter)
   }

}

func main() { 

   head = &Ele{"tacos", nil}
   next := head.Append("burritos")
   next = next.Append("fajitas")
   next = next.Append("enchilatas")

   fmt.Println("Before any removals:")
   head.Traverse()

   head.Remove("fajitas")
   fmt.Println("\nAfter removing fajitas:")
   head.Traverse()

   head.Remove("tacos")
   fmt.Println("\nAfter removing tacos:")
   head.Traverse()

   head.Remove("enchilatas")
   fmt.Println("\nAfter removing enchilatas:")
   head.Traverse()

   head.Remove("burritos")
   fmt.Println("\nAfter removing burritos:")
   head.Traverse()

}</lang>

Output:
Before any removals:
tacos
burritos
fajitas
enchilatas

After removing fajitas:
tacos
burritos
enchilatas

After removing tacos:
burritos
enchilatas

After removing enchilatas:
burritos

After removing burritos:
<nil>

jq

Works with: jq

Works with gojq, the Go implementation of jq

For context see Singly-linked_list/Element_definition#jq.

Here we define three filters for removing items from a SLL. The functions which are defined recursively have an inner function to take advantage of jq's tail-call optimization (TCO).

<lang jq># Input: a JSON object representing a SLL

  1. Output: an object with the same value after
  2. removal of the first item for which (.item|f) is truthy

def remove(f): 

 def r:
   if has("item") and (.item|f) then .next
   elif .next then .next |= r
   else .
   end;
 r;
  1. Input: a JSON entity representing a SLL.
  2. Output: an object with the same value after
  3. removal of the first occurrence of $x if any.

def remove_item($x): 

 remove(. == $x);

def remove_all(f): 

 def r:
   if has("item") and (.item|f) then .next | r
   elif .next then .next |= r
   else .
   end;
 r;</lang>

Example <lang jq>{ 

 "item": 1,
 "next": {
   "item": 2,
   "next": null
 }

} | remove_all(. == 1)</lang>

Output:
{
  "item": 2,
  "next": null
}

Julia

Works with: Julia version 0.6

See the LinkedList defined at Singly-linked_list/Element_definition#Julia. <lang julia>function Base.deleteat!(ll::LinkedList, index::Integer) 

   if isempty(ll) throw(BoundsError()) end
   if index == 1
       ll.head = ll.head.next
   else
       nd = ll.head
       index -= 1
       while index > 1 && !isa(nd.next, EmptyNode)
           nd = nd.next
           index -= 1
       end
       if nd.next isa EmptyNode throw(BoundsError()) end
       nx = nd.next
       nd.next = nd.next.next
   end
   return ll

end</lang>

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

Nim

<lang Nim>import strutils

type 

 Node[T] = ref object
   next: Node[T]
   data: T

 SinglyLinkedList[T] = object
   head, tail: Node[T]

proc newNode[T](data: T): Node[T] = 

 Node[T](data: data)

proc append[T](list: var SinglyLinkedList[T]; node: Node[T]) = 

 if list.head.isNil:
   list.head = node
   list.tail = node
 else:
   list.tail.next = node
   list.tail = node

proc append[T](list: var SinglyLinkedList[T]; data: T) = 

 list.append newNode(data)

proc prepend[T](list: var SinglyLinkedList[T]; node: Node[T]) = 

 if list.head.isNil:
   list.head = node
   list.tail = node
 else:
   node.next = list.head
   list.head = node

proc prepend[T](list: var SinglyLinkedList[T]; data: T) = 

 list.prepend newNode(data)

proc remove[T](list: var SinglyLinkedList[T]; node: Node[T]) = 

 if node.isNil:
   raise newException(ValueError, "trying to remove nil reference.")
 if node == list.head:
   list.head = list.head.next
   if list.head.isNil: list.tail = nil
 else:
   var n = list.head
   while not n.isNil and n.next != node:
     n = n.next
   if n.isNil: return  # Not found: ignore.
   n.next = node.next
   if n.next.isNil: list.tail = n

proc find[T](list: SinglyLinkedList[T]; data: T): Node[T] = 

 result = list.head
 while not result.isNil and result.data != data:
   result = result.next

proc `$`[T](list: SinglyLinkedList[T]): string = 

 var s: seq[T]
 var n = list.head
 while not n.isNil:
   s.add n.data
   n = n.next
 result = s.join(" → ")

var list: SinglyLinkedList[int]

for i in 1..5: list.append(i) echo "List: ", list list.remove(list.find(3)) echo "After removing 3: ", list list.remove(list.find(1)) echo "After removing 1: ", list list.remove(list.find(5)) echo "After removing 5: ", list</lang>

Output:
List: 1 → 2 → 3 → 4 → 5
After removing 3: 1 → 2 → 4 → 5
After removing 1: 2 → 4 → 5
After removing 5: 2 → 4

Phix

Note that singly-linked lists are a bit alien to Phix, since the core sequence type is so versatile.

While Singly-linked_list/Traversal#Phix inserts at the end, I thought I'd mix things up and try an in-order insert here and then mix them up again and remove items in a random order. Obviously remove_item() forms the meat of the task requirement; insert_inorder(), show(), and test() aren't really and can be skipped. <lang Phix>enum NEXT,DATA sequence sll = {} integer sll_head = 0, 

       sll_free = 0

procedure insert_inorder(object data) 

   if length(sll)=0 or sll_head=0 then
       sll = Template:0,data
       sll_head = 1
       sll_free = 0
   else
       integer this = sll_head, next, flag = 0
       object node = 0
       while 1 do
           next = sll[this][NEXT]
           if data<sll[this][DATA] then
               flag = 1
               node = sll[this]
           elsif next=0 then
               flag = 2
               node = {0,data}
           end if
           if flag then
               if sll_free then
                   next = sll_free
                   sll_free = sll[next][NEXT]
                   sll[next] = node
               else
                   sll = append(sll,node)
                   next = length(sll)
               end if
               sll[this][NEXT] = next
               if flag=1 then
                   sll[this][DATA] = data
               end if
               exit
           end if
           this = next
       end while
   end if

end procedure

procedure remove_item(object data) 

   integer idx = sll_head, prev
   while idx do
       if sll[idx][DATA]=data then
           if idx=sll_head then
               sll_head = sll[idx][NEXT]
           else
               sll[prev][NEXT] = sll[idx][NEXT]
           end if
           sll[idx][NEXT] = sll_free
           sll[idx][DATA] = 0
           sll_free = idx
           exit
       end if
       prev = idx
       idx = sll[idx][NEXT]
   end while

end procedure

procedure show() integer idx = sll_head sequence list = {} 

   while idx do
       list = append(list,sll[idx][DATA])
       idx = sll[idx][NEXT]
   end while
   ?list

end procedure

enum ADD,REMOVE procedure test(integer mode, sequence list) 

   ?{{"add","remove"}[mode],list}
   for i=1 to length(list) do
       if mode=ADD then
           insert_inorder(list[i])
       else
           remove_item(list[i])
       end if
       show()
   end for

end procedure

sequence list = {"1","2","3","4"} test(ADD,shuffle(list)) test(REMOVE,shuffle(list))</lang>

Output:
{"add",{"4","2","3","1"}}
{"4"}
{"2","4"}
{"2","3","4"}
{"1","2","3","4"}
{"remove",{"1","3","2","4"}}
{"2","3","4"}
{"2","4"}
{"4"}
{}

PicoLisp

Non destructive

<lang PicoLisp>(de delnon (Item Lst) 

  (if (index Item Lst)
     (conc
        (head (dec @) Lst)
        (tail (- @) Lst) )
     Lst ) )

(let (N 2 L (range 1 5)) 

  (delnon N L)
  (println 'L L)
  (setq L (delnon N L))
  (println 'fin L) )</lang>
Output:
L (1 2 3 4 5)
fin (1 3 4 5)

Destructive

<lang PicoLisp>(de deldestr (Item "Var") 

  (let Lst (val "Var")
     (let? M (member Item Lst)
        (ifn (prior M Lst)
           (set "Var" (cdr Lst))
           (con @ (cdr M))
           (val "Var") ) ) ) )

(let (N 3 L (range 1 5)) 

  (println 'L L)
  (deldestr N 'L)
  (println 'fin 'L L) )</lang>
Output:
L (1 2 3 4 5)
fin L (1 2 4 5)

Python

I added a lot of comments to be more beginnner friendly. This program will remove elements in any position based on their value, not key.

<lang python> class Node: 

   def __init__(self, data=None):
       self.data = data
       self.next = None


class SLinkedList: 

   def __init__(self):
       self.head = None

   def insert_first(self, insert_this):
       new_node = Node(insert_this)
       new_node.next = self.head
       self.head = new_node

   def remove_node(self, remove_this):

       # declare the "first" in list
       head_val = self.head

       # IF first in list isn't None, then...
       # IF first in list == value to be removed, then...
       # assign the NEXT node as the new "first in list"
       if head_val is not None:
           if head_val.data == remove_this:
               self.head = head_val.next
               return

       # WHILE first in list is not None, then...
       # IF first in list == value to be removed, then...
       # BREAK
       # ELSE assign current first in list in "prev" (to preserve it's value) , and...
       # assign next value as first in list
       while head_val is not None:
           if head_val.data == remove_this:
               break
           prev = head_val
           head_val = head_val.next

       # if first in list is empty, exit function
       if head_val is None:
           return

       # this assignment removes the value to be deleted
       prev.next = head_val.next

   def print_llist(self):
       print_node = self.head
       while print_node:
           print(print_node.data),
           print_node = print_node.next

mylist = SLinkedList() mylist.insert_first("red") mylist.insert_first("orange") mylist.insert_first("yellow") mylist.insert_first("green") print("Original list:") mylist.print_llist() mylist.remove_node("orange") print("\nAfter orange is removed:") mylist.print_llist()

</lang>

Output:
Original list:
green
yellow
orange
red

After orange is removed:
green
yellow
red

Racket

This is written entirely in terms of car and cdr (the linked list/pair primitives in Racket and Scheme). Usually, you'd have reverse and append available to you... but, again, it's interesting to see how they are implemented (by me, at least)

<lang racket>#lang racket/base

(define (rev l (acc null)) 

   (if (null? l)
       acc
       (rev (cdr l) (cons (car l) acc))))

(define (++ l m) 

   (if (null? l)
       m
       (let recur ((l-rev (rev l)) (acc m))
         (if (null? l-rev)
             acc
             (recur (cdr l-rev) (cons (car l-rev) acc))))))

(define (remove-at l i (acc null)) 

 (cond
   [(null? l) (rev acc)]
   [(positive? i) (remove-at (cdr l) (sub1 i) (cons (car l) acc))]
   [else (++ (rev acc) (cdr l))]))

(displayln (remove-at '(1 2 3) 0)) (displayln (remove-at '(1 2 3) 1)) (displayln (remove-at '(1 2 3) 2)) (displayln (remove-at '(1 2 3) 3))</lang>

Output:
(2 3)
(1 3)
(1 2)
(1 2 3)

Raku

(formerly Perl 6)

Extending class Cell from Singly-linked_list/Element_definition#Raku:

<lang perl6> method delete ($value --> Cell) { 

       my $prev = Nil;
       my $cell = self;
       my $new-head = self;
       
       while $cell {
           my $next = $cell.next;
           if $cell.value == $value {
               $prev.next = $next if $prev;
               $cell.next = Nil;
               $new-head = $next if $cell === $new-head;
           }
           else {
               $prev = $cell;
           }
           $cell = $next;
       }
       
       return $new-head;
   }</lang>

Usage:

<lang perl6>my $list = cons 10, (cons 20, (cons 10, (cons 30, Nil)));

$list = $list.delete(10);</lang>

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>

Wren

Library: Wren-llist

<lang ecmascript>import "/llist" for LinkedList

var ll = LinkedList.new(["dog", "cat", "bear"]) System.print("Before removals: %(ll)") ll.remove("cat") // remove by element System.print("After removal 1: %(ll)") ll.removeAt(0) // remove by index System.print("After removal 2: %(ll)")</lang>

Output:
Before removals: [dog -> cat -> bear]
After removal 1: [dog -> bear]
After removal 2: [bear]

Yabasic

<lang Yabasic>// Rosetta Code problem: http://rosettacode.org/wiki/Singly-linked_list/Element_insertion & removal // by Galileo, 02/2022

FIL = 1 : DATO = 2 : LINK = 3 countNodes = 0 : Nodes = 10

dim list(Nodes, 3)


sub searchNode(node) 

   local i, prevNode
   
   for i = 1 to countNodes
       if i = node break
       prevNode = list(prevNode, LINK)
   next
   
   return prevNode

end sub

sub insertNode(node, newNode, after) 

   local prevNode, i
   
   prevNode = searchNode(node)
   
   if after prevNode = list(prevNode, LINK)
   
   for i = 1 to Nodes
       if not list(i, FIL) break
   next
   
   list(i, FIL) = true
   list(i, DATO) = newNode
   list(i, LINK) = list(prevNode, LINK)
   list(prevNode, LINK) = i
   
   countNodes = countNodes + 1
   if countNodes = Nodes then Nodes = Nodes + 10 : redim list(Nodes, 3) : end if

end sub


sub removeNode(n) 

   local prevNode, node
   
   prevNode = searchNode(n)
   node = list(prevNode, LINK)
   list(prevNode, LINK) = list(node, LINK)
   list(node, FIL) = false
   countNodes = countNodes - 1

end sub


sub printNode(node) 

   local prevNode
   
   prevNode = searchNode(node)
   node = list(prevNode, LINK)
   print list(node, DATO);
   print

end sub


insertNode(1, 1000, true) insertNode(1, 2000, true) insertNode(1, 3000, true)

printNode(1) printNode(2) printNode(3)

removeNode(2)

print printNode(1) printNode(2)</lang>

Output:
1000
3000
2000

1000
2000
---Program done, press RETURN---
Retrieved from "https://rosettacode.org/wiki/Singly-linked_list/Element_removal?oldid=271381"