Singly-linked list/Element removal: Difference between revisions

The user must type in the monitor the following command after compilation and before running the program!<pre>SET EndProg=*</pre>

{{libheader|Action! Tool Kit}}

 

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

TestRemove(p)

TestRemove(listBegin)

{{out}}

[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Singly-linked_list_element_removal.png Screenshot from Atari 8-bit computer]

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

{{Trans|ALGOL_W}}

PRIO REMOVE = 1;

OP REMOVE = ( REF STRINGLIST list, REF STRINGLIST element )REF STRINGLIST:

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

 

 

=={{header|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, %

Remove( head, head );

 

 

=={{header|ATS}}==

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.

 

implement

 

{{out}}

 

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

 

=={{header|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>

return 0;

}

Invocation, interaction and output :

<pre>

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

 

using System.Runtime.InteropServices;

 

Console.WriteLine("after removing second node: " + head->ToString());

}

 

{{out}}

 

=={{header|C++}}==

 

// define a singly linked list

PrintList(head);

if (!removed2) std::cout << "\nItem not found\n";

{{out}}

<pre>

Item not found</pre>

 

=={{header|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.

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.

 

CONTAINS !Demonstration only!

SUBROUTINE LLREMOVE(LINK,X) !Remove entry X from the links in LINK.

CALL LLFOLLOW(LINK) !But, I know where it was, in this example.

 

Output:

<pre>

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?

 

1 NEXT = LINK(IT) !This is the node of interest.

IF (NEXT.GT.0) THEN !Is it a live node?

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.

 

DO WHILE((NEXT = LINK(IT)).GT.0) !Finger the follower of IT.

IF (NEXT.EQ.X) THEN !Is it the unwanted one?

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.

 

=={{header|FreeBASIC}}==

{{trans|Yabasic}}

#define DATO 2

#define LINK 3

Print

printNode(1)

{{out}}

<pre>1000

=={{header|Go}}==

This reuses code from other singly-linked list tasks.

 

import "fmt"

fmt.Println("\nAfter removing burritos:")

head.Traverse()

 

{{out}}

to take advantage of jq's tail-call optimization (TCO).

 

# Output: an object with the same value after

# removal of the first item for which (.item|f) is truthy

else .

end;

'''Example'''

"item": 1,

"next": {

}

}

{{out}}

<pre>

{{works with|Julia|0.6}}

See the <tt>LinkedList</tt> defined at [[Singly-linked_list/Element_definition#Julia]].

if isempty(ll) throw(BoundsError()) end

if index == 1

end

return ll

 

=={{header|Kotlin}}==

 

class Node<T: Number>(var data: T, var next: Node<T>? = null) {

remove(a, b) // remove last node

println("After 2nd removal : $a")

 

{{out}}

After 2nd removal : 1

</pre>

 

=={{header|Nim}}==

 

type

echo "After removing 1: ", list

list.remove(list.find(5))

 

{{out}}

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.

{{out}}

<pre>

=={{header|PicoLisp}}==

===Non destructive===

(if (index Item Lst)

(conc

(println 'L L)

(setq L (delnon N L))

{{out}}

<pre>

</pre>

===Destructive===

(let Lst (val "Var")

(let? M (member Item Lst)

(println 'L L)

(deldestr N 'L)

{{out}}

<pre>

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):

mylist.print_llist()

 

 

{{out}}

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)

 

 

(define (rev l (acc null))

(displayln (remove-at '(1 2 3) 1))

(displayln (remove-at '(1 2 3) 2))

 

{{out}}

Extending <tt>class Cell</tt> from [[Singly-linked_list/Element_definition#Raku]]:

 

my $prev = Nil;

my $cell = self;

return $new-head;

 

Usage:

 

 

 

=={{header|Visual Basic .NET}}==

- The entry has been removed.

 

 

Module Module1

End Module

 

 

=={{header|Wren}}==

{{libheader|Wren-llist}}

 

var ll = LinkedList.new(["dog", "cat", "bear"])

System.print("After removal 1: %(ll)")

ll.removeAt(0) // remove by index

 

{{out}}

 

=={{header|Yabasic}}==

// by Galileo, 02/2022

 

print

printNode(1)

{{out}}

<pre>1000