Singly-linked list/Element removal

From Rosetta Code
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
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
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
# 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))))));

# remove the third and then the first element from the STRINGLIST #

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

ALGOL W

Uses the ListI record from the Singly Linked List task. 

    % 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 );

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. 

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

(* 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. *)
#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. *)
#define NIL rclist_vt_nil ()
#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 () = ()
Output:
$ patscc -DATS_MEMALLOC_LIBC singly_linked_list_deletion.dats && ./a.out
123
789

Afterword. The Rosetta Code linear list type was a good exercise. The linear lists code in the ATS2 prelude contains many unsafe operations, which is fine for a well tested library, but not terribly enlightening. In contrast, I wrote the Rosetta Code linear list type using only ‘safe’ ATS2 code.

THE PURPOSE OF COMPUTING IS INSIGHT, NOT NUMBERS

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. 

#include<stdlib.h>
#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;
}

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: 

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 = &copy;
        Console.WriteLine("restored from copy:          " + head->ToString());

        Remove(&head, head->Next);
        Console.WriteLine("after removing second node:  " + head->ToString());
    }
}
Output:
original:                    1 -> 2
after removing head:         2
restored from copy:          1 -> 2
after removing second node:  1

C++ 

#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";
}
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

F#

Not really a functional thing to do but... 

// Singly-linked list/Element removal. Nigel Galloway: March 22nd., 2022
let N=[23;42;1;13;0]
let fG n g=List.indexed n|>List.filter(fun(n,_)->n<>g)|>List.map snd
printfn "   before: %A\nand after: %A" N (fG N 2)
Output:
   before: [23; 42; 1; 13; 0]
and after: [23; 42; 13; 0]

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. 

      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

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 

          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.

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 

      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.

No label, no nasty literal GO TO - even though an "END DO" hides one.

FreeBASIC

Translation of: Yabasic
#define FIL   1
#define DATO  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)
Output:
1000
3000
2000

1000
2000

Go

This reuses code from other singly-linked list tasks. 

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()
}
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). 

# Input: a JSON object representing a SLL
# Output: an object with the same value after
# 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;

# Input: a JSON entity representing a SLL.
# Output: an object with the same value after
# 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;

Example 

{
  "item": 1,
  "next": {
    "item": 2,
    "next": null
  }
}
| remove_all(. == 1)
Output:
{
  "item": 2,
  "next": null
}

Julia

Works with: Julia version 0.6

See the LinkedList defined at Singly-linked_list/Element_definition#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

Kotlin 

// 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")
}
Output:
Before insertion  : 1 -> 3
After  insertion  : 1 -> 2 -> 3
After 1st removal : 1 -> 3
After 2nd removal : 1

MiniScript

We're choosing here to use the built-in list type, rather than make our own from scratch, since this is more representative of how one is likely to actually use MiniScript. 

> myList = range(100, 110)
> myList
[100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110]
> myList.pop // removes the last element
110
> myList
[100, 101, 102, 103, 104, 105, 106, 107, 108, 109]
> myList.pull // removes the first element
100
> myList
[101, 102, 103, 104, 105, 106, 107, 108, 109]
> myList.remove 5 // removes 106 at index 5
> myList
[101, 102, 103, 104, 105, 107, 108, 109]


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

with javascript_semantics
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 = {{0,data}}
        sll_head = 1
        sll_free = 0
    else
        integer curr = sll_head, next, flag = 0
        object node = 0
        while 1 do
            next = sll[curr][NEXT]
            if data<sll[curr][DATA] then
                flag = 1
                node = sll[curr]
            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
                node = deep_copy(sll[curr])
                node[NEXT] = next
                if flag=1 then
                    node[DATA] = data
                end if
                sll[curr] = node
                exit
            end if
            curr = 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))
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

(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) )
Output:
L (1 2 3 4 5)
fin (1 3 4 5)

Destructive

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

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()
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/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))
Output:
(2 3)
(1 3)
(1 2)
(1 2 3)

Raku

(formerly Perl 6)

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

    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;
    }

Usage: 

my $list = cons 10, (cons 20, (cons 10, (cons 30, Nil)));

$list = $list.delete(10);

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. 

    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

Wren

Library: Wren-llist
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)")
Output:
Before removals: [dog -> cat -> bear]
After removal 1: [dog -> bear]
After removal 2: [bear]

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)
Output:
1000
3000
2000

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