Singly-linked list/Element insertion: Difference between revisions
Singly-linked list/Element insertion (view source)
Revision as of 11:41, 6 February 2024
, 4 months ago→{{header|Wren}}: Minor tidy
Thundergnat (talk | contribs) (→{{header|Raku}}: Fix up internal link) |
m (→{{header|Wren}}: Minor tidy) |
||
(21 intermediate revisions by 15 users not shown) | |||
Line 8:
=={{header|360 Assembly}}==
The program uses one ASSIST macro (XPRNT) to keep the code as short as possible.
<
LISTSINA CSECT
USING LISTSINA,R13 base register
Line 94:
NEXT DS A
YREGS
END LISTSINA</
{{out}}
<pre>
Line 104:
=={{header|AArch64 Assembly}}==
{{works with|as|Raspberry Pi 3B version Buster 64 bits}}
<syntaxhighlight lang="aarch64 assembly">
/* ARM assembly AARCH64 Raspberry PI 3B */
/* program insertList64.s */
Line 229:
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
</syntaxhighlight>
=={{header|ACL2}}==
<
(cond ((endp xs)
nil)
Line 239:
(cons e (rest xs))))
(t (cons (first xs)
(insert-after x e (rest xs))))))</
Example:
<pre>>(insert-after 'A 'C '(A B))
(A C B)</pre>
=={{header|Action!}}==
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}}
<syntaxhighlight 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="3"
TYPE ListNode=[CHAR data PTR nxt]
ListNode POINTER listBegin
PROC AddBegin(CHAR v)
ListNode POINTER n
n=Alloc(NODE_SIZE)
n.data=v
n.nxt=listBegin
listBegin=n
RETURN
PROC AddAfter(CHAR v ListNode POINTER node)
ListNode POINTER n
IF node=0 THEN
PrintE("The node is null!") Break()
ELSE
n=Alloc(NODE_SIZE)
n.data=v
n.nxt=node.nxt
node.nxt=n
FI
RETURN
PROC Clear()
ListNode POINTER n,next
n=listBegin
WHILE n
DO
next=n.nxt
Free(n,NODE_SIZE)
n=next
OD
listBegin=0
RETURN
PROC PrintList()
ListNode POINTER n
n=listBegin
Print("(")
WHILE n
DO
Put(n.data)
IF n.nxt THEN
Print(", ")
FI
n=n.nxt
OD
PrintE(")")
RETURN
PROC TestAddBegin(CHAR v)
AddBegin(v)
PrintF("Add '%C' at the begin:%E",v)
PrintList()
RETURN
PROC TestAddAfter(CHAR v ListNode POINTER node)
AddAfter(v,node)
PrintF("Add '%C' after '%C':%E",v,node.data)
PrintList()
RETURN
PROC TestClear()
Clear()
PrintE("Clear the list:")
PrintList()
RETURN
PROC Main()
Put(125) PutE() ;clear screen
AllocInit(0)
listBegin=0
PrintList()
TestAddBegin('A)
TestAddAfter('B,listBegin)
TestAddAfter('C,listBegin)
TestClear()
RETURN</syntaxhighlight>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Singly-linked_list_element_insertion.png Screenshot from Atari 8-bit computer]
<pre>
()
Add 'A' at the begin:
(A)
Add 'B' after 'A':
(A, B)
Add 'C' after 'A':
(A, C, B)
Clear the list:
()
</pre>
=={{header|ActionScript}}==
Insertion method:
<
{
public class Node
Line 260 ⟶ 368:
}
}
}</
Usage:
<
var A:Node = new Node(1);
Line 268 ⟶ 376:
var C:Node = new Node(3);
A.insert(B);
A.insert(C);</
=={{header|Ada}}==
We must create a context clause making the predefined generic procedure Ada.Unchecked_Deallocation visible to this program.
<
-- Define the link type
procedure Singly_Linked is
Line 305 ⟶ 413:
Free(B);
Free(C);
end Singly_Linked;</
=={{header|ALGOL 68}}==
Line 311 ⟶ 419:
standard library. However Linked lists are presented in standard text
book examples. Or can be manually constructed, eg:
<
STRINGLIST list := ("Big",
Line 335 ⟶ 443:
node := next OF node
OD;
print((newline))</
Output:<pre>Big fjords vex VERY quick waltz nymph </pre>
=={{header|ALGOL W}}==
<
procedure insert( reference(ListI) value list
; integer value newValue
Line 352 ⟶ 460:
% insert a new value into the list %
insert( next(head), 4077 );</
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi}}
<syntaxhighlight lang="arm assembly">
/* ARM assembly Raspberry PI */
/* program insertList.s */
Line 536 ⟶ 644:
bx lr @ leave function
iMagicNumber: .int 0xCCCCCCCD
</syntaxhighlight>
=={{header|ATS}}==
I repeated the [[Singly-linked_list/Element_definition#ATS|‘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.
Notice that the insertion routine proves that the resulting list is either of
the same length as or one longer than the original list. Also there is proof
that the insertion routine will terminate.
<syntaxhighlight 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 insertion routine will
be specifically for lists of ‘int’. We shall not take advantage of
the template system. *)
(* Some things that will be needed. *)
#include "share/atspre_staload.hats"
(* The list is passed by reference and will be replaced by the new
list. The old list is invalidated. *)
extern fun
rclist_int_insert
{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 (if no match were found) or a list
one longer. *)
[n : int | n == m || n == m + 1]
rclist_vt (int, n),
after : int,
x : int) :<!wrt> void
implement
rclist_int_insert {m} (lst, after, x) =
{
(* A recursive nested function that finds the matching element
and inserts the new node. *)
fun
find {k : int | 0 <= 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),
after : int,
x : int) :<!wrt> void =
case+ lst of
| rclist_vt_nil () => () (* Not found. Do nothing *)
| @ rclist_vt_cons (head, tail) when head = after =>
{
val _ = tail := rclist_vt_cons (x, tail)
prval _ = fold@ lst (* I need this unfolding and refolding
stuff to make ‘tail’ a reference
rather than a value, so I can
assign to it. *)
}
| @ rclist_vt_cons (head, tail) =>
{
val _ = find (tail, after, x)
prval _ = fold@ lst
}
(* The following is needed to prove that the initial k above
satisfies 0 <= k. *)
prval _ = lemma_rclist_vt_param lst
val _ = find (lst, after, x)
}
(* Now let’s try it. *)
(* Some convenient notation. *)
#define NIL rclist_vt_nil ()
#define :: rclist_vt_cons
overload insert with rclist_int_insert
val A = 123
val B = 789
val C = 456
(* ‘var’ to make lst a mutable variable rather than a
value (‘val’). *)
var lst = A :: B :: NIL
(* Do the insertion. *)
val () = insert (lst, A, 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 () = ()</syntaxhighlight>
{{out}}
<pre>$ patscc -DATS_MEMALLOC_LIBC singly_linked_list_insertion.dats && ./a.out
123
456
789</pre>
=={{header|AutoHotkey}}==
<syntaxhighlight lang="autohotkey">a = 1
a_next = b
b = 2
Line 555 ⟶ 799:
%old%_next := new
%new%_next := temp
}</
=={{header|Axe}}==
<
{r₁+2}ʳ→{r₂+2}ʳ
r₂→{r₁+2}ʳ
r₁
Return</
=={{header|BBC BASIC}}==
{{works with|BBC BASIC for Windows}}
<
DIM a{} = node{}, b{} = node{}, c{} = node{}
Line 581 ⟶ 825:
here.pNext% = new{}
ENDPROC
</syntaxhighlight>
=={{header|C}}==
Line 587 ⟶ 831:
Define the method:
<
newlink->next = anchor->next;
anchor->next = newlink;
}</
Note that in a production implementation, one should check anchor and newlink to ensure they're valid values. (I.e., not NULL.)
Line 597 ⟶ 841:
Create our links.
<
a = malloc(sizeof(link));
b = malloc(sizeof(link));
Line 603 ⟶ 847:
a->data = 1;
b->data = 2;
c->data = 3;</
Prepare our initial list
<syntaxhighlight lang
Insert element c after element a
<syntaxhighlight lang
Remember to free the memory once we're done.
<
free (b);
free (c);</
=={{header|C sharp|C#}}==
Line 620 ⟶ 864:
Creates nodes and inserts them from the data passed.
<
{
prev.Next = new Link() { Value = value, Next = prev.Next };
}</
<
{
//Create A(5)->B(7)
Line 632 ⟶ 876:
//Insert C between A and B
InsertAfter(A, 15);
}</
=={{header|C++}}==
This uses the generic version of the link node. Of course, normally this would be just some implementation detail inside some list class, not to be used directly by client code.
<
{
new_node->next = list_node->next;
list_node->next = new_node;
};</
Here's the example code using that method:
The following code creates the links. As numeric values I've just taken the corresponding character values.
<
link<int>* c = new link<int>('C');</
Now insert c after a:
<syntaxhighlight lang
Finally destroy the list:
<
{
link<int>* tmp = a;
a = a->next;
delete tmp;
}</
=={{header|Clojure}}==
<
(cond (empty? ls) ls
(= (first ls) old) (cons old (cons new (rest ls)))
:else (cons (first ls) (insert-after new old (rest ls)))))</
And the test:
<
(a c b)</
=={{header|Common Lisp}}==
Line 675 ⟶ 919:
For many list manipulations in Common Lisp, there are both destructive and non-destructive versions. <code>insert-after</code> is non-destructive, copying the structure of list up to and including the occurrence of the old-element, and sharing the list structure afterward. <code>ninsert-after</code> may modify the structure of the input list.
<
"Return a list like list, but with new-element appearing after the
first occurence of old-element. If old-element does not appear in
Line 693 ⟶ 937:
((or (null next) (funcall test old-element (car prev)))
(rplacd prev (cons new-element next))
list))))</
A simpler implementation that traverses the list a bit more can also be written. This takes advantage of the fact that member returns the tail of the list beginning with the first occurrence of an item, and that ldiff copies as much of its list argument as necessary.
<
(let ((tail (rest (member old-element list :test test))))
(nconc (ldiff list tail)
(cons new-element tail))))</
Lastly, here is a recursive version. Case 3 could be optimized by only doing the rplacd operation when the recursive call returns a tail whose first cell is now different compared to that of the previous tail. (I.e. the recursive call has immediately hit case 1 or 2 which allocate new structure.)
<
"Insert item new into list, before existing, or at the end if existing
is not present. The default comparison test function is EQL. This
Line 718 ⟶ 962:
;; and make that list the new rest.
(t (rplacd list (insert-before (cdr list) new existing :test test))
list)))</
=={{header|D}}==
<
T data;
typeof(this)* next;
Line 741 ⟶ 985:
// The GC will collect the memory.
}</
=={{header|Delphi}}==
Line 747 ⟶ 991:
A simple insertion into a one way list. I use a generic pointer for the data that way it can point to any structure, individual variable or whatever. '''NOTE:''' For original versions of Turbo Pascal, substitute the MemAvail Function for the Try Except block as this does not exist in this version of the pascal language. Also, Turbo Pascal doesn't have C++-style comments, therefore those have to be replaced with Pascal style comments, i.e. { ... } or (* ... *).
<
Type
Line 804 ⟶ 1,048:
CurrentNode.Next := result ;
end;
end;</
=={{header|E}}==
<
new :LinkedList ? (new.next().null())) {
new.setNext(head.next())
Line 825 ⟶ 1,069:
println(x.value())
x := x.next()
}</
=={{header|EchoLisp}}==
Lists are mutable, and we use the destructive - and dangerous - set-cdr! operator which modifies the 'rest' part of a list or sub-list.
<
(define (insert-after lst target item)
(when (null? lst) (error "cannot insert in" null))
Line 841 ⟶ 1,085:
(insert-after L 'x 'y)
L → (a c b y)
</syntaxhighlight>
=={{header|Elena}}==
<
{
insertAfter(Link prev, IntNumber i)
Line 850 ⟶ 1,094:
prev.Next := new Link(i, prev.Next)
}
}</
=={{header|Erlang}}==
Lists are builtin, but Erlang is single assignment. Here we need mutable link to next element. Mutable in Erlang usually means a process, so:
<syntaxhighlight lang="erlang">
-module( singly_linked_list ).
Line 906 ⟶ 1,150:
loop_foreach( _Fun, nonext ) -> ok;
loop_foreach( Fun, Next ) -> Next ! {foreach, Fun}.
</syntaxhighlight>
{{out}}
<pre>
Line 916 ⟶ 1,160:
=={{header|Factor}}==
<
[ swap next>> >>next drop ] [ >>next drop ] 2bi ;
Line 924 ⟶ 1,168:
[ C <linked-list> list-append ] keep
[ B <linked-list> list-append ] keep
.</
Output:
<pre>
Line 942 ⟶ 1,186:
Extending Node class from [[Singly-Linked_List_(element)]]:
<
class Node
{
Line 977 ⟶ 1,221:
}
}
</syntaxhighlight>
Output:
Line 989 ⟶ 1,233:
Using the linked list concept described in the [[Singly-Linked_List_(element)]] topic:
<
create A 0 , char A ,
create B 0 , char B ,
create C 0 , char C ,</
Now insert b after a and c after b, giving a->b->c
<
C B chain</
Here is an abbreviated version of the definition of 'chain' from the other article:
<
=={{header|Fortran}}==
In ISO Fortran 95 or later:
<
type (node), intent(inout) :: nodeBefore
real, intent(in) :: value
Line 1,012 ⟶ 1,256:
newNode%next => nodeBefore%next
nodeBefore%next => newNode
end subroutine addAfter</
=={{header|FreeBASIC}}==
Assumes you already have the ll_int data type, defined [[Singly-linked_list/Element_definition#FreeBASIC|here]].
<syntaxhighlight lang="freebasic">sub insert_ll_int( anchor as ll_int ptr, ins as ll_int ptr)
ins->nxt = anchor->nxt
anchor->nxt = ins
end sub</syntaxhighlight>
=={{header|Go}}==
<
import "fmt"
Line 1,052 ⟶ 1,303:
h.insert("C")
h.printList()
}</
Output:
<pre>
Line 1,061 ⟶ 1,312:
=={{header|Groovy}}==
Solution (uses ListNode from [[Singly-Linked List (element)#Groovy]]):
<
private enum Flag { FRONT }
private ListNode head
Line 1,080 ⟶ 1,331:
}
String toString() { "${head}" }
}</
Test:
<
list.insert('B')
list.insert('A')
Line 1,089 ⟶ 1,340:
list.insert('C', 'A')
println list</
Output:
Line 1,097 ⟶ 1,348:
=={{header|Haskell}}==
This kind of list manipulation is [[unidiomatic]] Haskell. But you can try the following:
<
| otherwise = c : insertAfter a b cs
insertAfter _ _ [] = error "Can't insert"</
==Icon and Unicon==
Line 1,107 ⟶ 1,358:
==={{header|Icon}}===
<syntaxhighlight lang="icon">
record Node (value, successor)
Line 1,114 ⟶ 1,365:
node.successor := newNode
end
</syntaxhighlight>
==={{header|Unicon}}===
<syntaxhighlight lang="unicon">
class Node (value, successor)
Line 1,130 ⟶ 1,381:
self.successor := successor
end
</syntaxhighlight>
=={{header|J}}==
<
A=:0 NB. reference into list
B=:1 NB. reference into list
Line 1,144 ⟶ 1,395:
localNewNode=: (localOldLinkRef { localListValue), localNewValue
(localListName)=: (localNewLinkRef localOldLinkRef} localListValue), localNewNode
)</
With these definitions:
Line 1,156 ⟶ 1,407:
=={{header|Java}}==
Extending [[Singly-Linked_List_(element)#Java]]
<
{
new_node.next = anchor_node.next;
anchor_node.next = new_node;
}</
{{works with|Java|1.5+}}
Java allows the use of generics to allow the data type to be determined at compile time. This will only work on reference types, not primitive types like int or float (wrapper classes like Integer and Float are available).
Line 1,166 ⟶ 1,417:
=={{header|JavaScript}}==
Extending [[Singly-Linked_List_(element)#JavaScript]]
<
if (this._value == searchValue) {
nodeToInsert.next(this.next());
Line 1,177 ⟶ 1,428:
}
var list = createLinkedListFromArray(['A','B']);
list.insertAfter('A', new LinkedList('C', null));</
=={{header|jq}}==
{{works with|jq}}
'''Works with gojq, the Go implementation of jq'''
For context and a definition of `is_singly_linked_list`,
see [[Singly-linked_list/Element_definition#jq]].
<syntaxhighlight lang="jq"> def new($item; $next):
if $next | (.==null or is_singly_linked_list)
then {$item, $next}
else "new(_;_) called with invalid SLL: \($next)" | error
end;
# A constructor:
def new($x): new($x; null);
def insert($x):
if is_empty_singly_linked_list then {item: $x, next: null}
else .next |= new($x; .)
end;</syntaxhighlight>
'''An example''':
<syntaxhighlight lang="jq">
new(1) | insert(2)
</syntaxhighlight>
{{out}}
<pre>
{
"item": 1,
"next": {
"item": 2,
"next": null
}
}
</pre>
=={{header|Julia}}==
Line 1,183 ⟶ 1,469:
See the <tt>LinkedList</tt> implemented at [[Singly-linked_list/Element_definition#Julia]].
<
if index == 1
if isempty(ll)
Line 1,203 ⟶ 1,489:
end
return ll
end</
=={{header|Kotlin}}==
<
class Node<T: Number>(var data: T, var next: Node<T>? = null) {
Line 1,232 ⟶ 1,518:
insertAfter(a, c)
println("After insertion : $a")
}</
{{out}}
Line 1,241 ⟶ 1,527:
=={{header|Logo}}==
<
localmake "tail member :after :list
if not empty? :tail [.setbf :tail fput :value bf :tail]
Line 1,247 ⟶ 1,533:
end
show insert 5 [3 5 1 8] 2</
[3 5 2 1 8]
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
->{a, b, c}</
Node = {"item": null, "next": null}
Node.init = function(item)
node = new Node
node.item = item
return node
end function
=={{header|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.
<syntaxhighlight lang="miniscript">
> myList = [100, 101, 102]
> myList.push 103
[100, 101, 102, 103]
> myList.insert 0, 99
[99, 100, 101, 102, 103]
> myList.insert 3,101.5
[99, 100, 101, 101.5, 102, 103]
</syntaxhighlight>
=={{header|Modula-3}}==
<
TYPE
Line 1,280 ⟶ 1,585:
InsertAppend(a, b);
InsertAppend(a, c)
END SinglyLinkedList.</
=={{header|Nim}}==
<
next: Node[T]
data: T
Line 1,299 ⟶ 1,604:
a.insertAppend(b)
b.insertAppend(c)</
=={{header|OCaml}}==
This kind of list manipulation is unidiomatic OCaml. But you can try the following:
<
c :: cs when a = c -> a :: b :: cs
| c :: cs -> c :: insert_after a b cs
| [] -> raise Not_found</
=={{header|Odin}}==
<syntaxhighlight lang="odin">package main
Node :: struct {
data: rune,
next: ^Node,
}
insert_after :: proc(node, new_node: ^Node) {
new_node.next = node.next
node.next = new_node
}
main :: proc() {
a := new(Node)
a.data = 'A'
b := new(Node)
b.data = 'B'
c := new(Node)
c.data = 'C'
insert_after(a, b) // A -> B
insert_after(a, c) // A -> C -> B
assert(a.data == 'A')
assert(a.next.data == 'C')
assert(a.next.next.data == 'B')
}</syntaxhighlight>
=={{header|Oforth}}==
Line 1,312 ⟶ 1,648:
Method forEachNext is defined in order to traverse the LinkedList. This method is used by println (as a LinkedLIst is defined as a subclass of Collection).
<
LinkedList method: initialize := next := data ;
Line 1,327 ⟶ 1,663:
: testLink LinkedList new($A, null) dup add($B) dup add($C) ;
testLink println</
{{out}}
Line 1,336 ⟶ 1,672:
=={{header|ooRexx}}==
See [[Singly-linked_list/Element_definition#ooRexx|Single-linked list/Element definition]] for full class definition.
<syntaxhighlight lang="oorexx">
list = .
index = list~insert("abc") -- insert a first item, keeping the index
Call show
list~insert("def") -- adds to the end
Call show
list~insert("123", .nil) -- adds to the begining
Call show
list~insert("456", index) -- inserts between "abc" and "def"
Call show
list~remove(index) -- removes "abc"
Call show
exit
show:
s=''
Do x over list
s=s x
end
say s
Return</syntaxhighlight>
{{out]]
<pre> abc
abc def
123 abc def
123 abc 456 def
123 456 def
</pre>
=={{header|Pascal}}==
Line 1,350 ⟶ 1,705:
Since Standard Pascal doesn't know a generic pointer type, and also no generic types, one has to settle for a specific data type for the linked list. Since the task mentions node names "A", "B", "C", here a char is chosen. Of course any data type (including pointers to a specific data type) could have been used here.
<
pCharNode = ^CharNode;
CharNode = record
Line 1,364 ⟶ 1,719:
newnode^.next := listnode^.next;
listnode^.next := newnode;
end;</
Usage example:
<
A, B: pCharNode;
begin
Line 1,392 ⟶ 1,747:
dispose(B);
end
end.</
=={{header|Perl}}==
If you don't really need the constant-time insertion property of singly linked lists, just use an array. You can traverse and splice it any way.
<
push @l, $C, splice @l, 1;</
However, if you really need a linked list, or all you got is an algorithm in a foreign language, you can use references to accomplish the translation.
<
# first argument: node to insert after
# second argument: node to insert
Line 1,417 ⟶ 1,772:
data => 2,
);
insert_after \%A, \%C;</
Note that you don't have to name your new nodes. The following works just as well:
<
Note the curly braces instead of round parentheses.
It is straightforward to extend the function to take an arbitrary number of list nodes to insert:
<
my $node = $_[0];
my $next = $node->{next};
Line 1,433 ⟶ 1,788:
}
$node->{next} = $next;
}</
With this, it's rather easy to build a list:
<
insert_after \%list, { data => 'B' }, { data => 'C' };</
List handling is simplified if the variables themselves contain references. For example:
<
# create a new list ('A'. 'B', 'C') and store it in $list2
Line 1,447 ⟶ 1,802:
# append new nodes ('A2a', 'A2b') after the second element (which now is 'A2')
insert_after $list2->{next}, { data => 'A2a' }, { data => 'A2b' };</
=={{header|Phix}}==
See also [[Singly-linked_list/Traversal#Phix|Traversal]] and [[Singly-linked_list/Element_removal#Phix|Removal]].
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">enum</span> <span style="color: #000000;">NEXT</span><span style="color: #0000FF;">,</span><span style="color: #000000;">DATA</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">empty_sll</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}}</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">sll</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">empty_sll</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">insert_after</span><span style="color: #0000FF;">(</span><span style="color: #004080;">object</span> <span style="color: #000000;">data</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">pos</span><span style="color: #0000FF;">=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sll</span><span style="color: #0000FF;">))</span>
<span style="color: #000000;">sll</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sll</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">sll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pos</span><span style="color: #0000FF;">][</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">],</span><span style="color: #000000;">data</span><span style="color: #0000FF;">})</span>
<span style="color: #000000;">sll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pos</span><span style="color: #0000FF;">][</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sll</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">insert_after</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"ONE"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">insert_after</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"TWO"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">insert_after</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"THREE"</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">sll</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 1,472 ⟶ 1,830:
=={{header|PicoLisp}}==
Destructive operation
<
(when (member Item Lst)
(con @ (cons New (cdr @))) )
Lst )</
Non-destructive operation
<
(if (index Item Lst)
(conc (cut @ 'Lst) (cons New Lst))
Lst ) )</
Output in both cases:
<pre>: (insertAfter 'A '(A B) 'C)
Line 1,489 ⟶ 1,847:
=={{header|PL/I}}==
<syntaxhighlight lang="pl/i">
/* Let H be a pointer to a node in a one-way-linked list. */
/* Insert an element, whose value is given by variable V, following that node. */
Line 1,497 ⟶ 1,855:
node.value = V;
H->p = Q; /* Break the list at H, and point it at the new node. */
</syntaxhighlight>
=={{header|Pop11}}==
Line 1,503 ⟶ 1,861:
In Pop11 one normally uses built-in lists:
<
cons(x, back(anchor)) -> back(anchor);
enddefine;
Line 1,510 ⟶ 1,868:
insert_into_list(l1, "b");
;;; insert c
insert_into_list(l1, "c");</
If one wants one can use user-defined list node (for convenience we repeat definition of list node):
<
define :class ListNode;
slot value = [];
Line 1,527 ⟶ 1,885:
insert_into_List(l2, "b");
;;; insert c
insert_into_List(l2, "c");</
Note that user-defined case differs from built-in case only because of names.
=={{header|PureBasic}}==
<
Protected *newNode.MyData = AllocateMemory(SizeOf(MyData))
If *newNode
Line 1,549 ⟶ 1,907:
*SL_List = insertAfter(a) ;start the list
insertAfter(b, *SL_List) ;insert after head of list
insertAfter(c, *SL_List) ;insert after head of list and before tail</
=={{header|Python}}==
<
while lst is not None:
if lst[0] == at:
Line 1,563 ⟶ 1,921:
chain = ['A', ['B', None]]
chain_insert(chain, 'A', 'C')
print chain</
Output:
<
=={{header|Racket}}==
<syntaxhighlight lang="racket">
#lang racket
Line 1,581 ⟶ 1,939:
(insert-after! l 2 2.5)
l ; -> (mcons 1 (mcons 2 (mcons 2.5 (mcons 3))))
</syntaxhighlight>
=={{header|Raku}}==
Line 1,588 ⟶ 1,946:
Extending <tt>class Cell</tt> from [[Singly-linked_list/Element_definition#Raku]]:
<syntaxhighlight lang="raku"
$.next = Cell.new(:$value, :$.next)
}</
=={{header|REXX}}==
<
Call set_list 3 /* linked list: 12 Proth primes */
Call set_list 5 /*see https://mathworld.wolfram.com/ProthPrime.html*/
Call set_list 13
Call set_list 17
Call set_list 41
Call set_list 97
Call set_list 113
Call set_list 193
Call set_list 241
Call set_list 257
Call set_list 353
Call set_list 449
Call show_list
nnn=z..after
Call ins_list nnn,newval /* perform the insertion */
Say ''
Say 'a new value of' newval 'has been inserted',
Call show_list
Exit /* stick a fork in it, we're done.*/
set_list: Procedure Expose z.
last=z.0 /* set the previous last element. */
new=z.0+1 /* set the new ast element. */
z.new.0next=0 /* set the next pointer value. */
z..value=new /* set a locator pointer to self. */
z.0width=max(z.0width,length(value)) /*set maximum width of any value*/
Return
ins_list: Procedure Expose z.
Parse Arg nnn,value
z.0=z.0+1 /* bump number of list elements. */
last=z.0 /* position of the new value */
z.last.0value=value /* store the new value */
z.last.0next=z.nnn.0next /* uptate the pointers to the */
z.0width=max(z.0width,length(value)) /*set maximum width of any value*/
Return
show_list:
Say
Say center('item',6) 'position' center('value',w) center('next',6)
Say center('',6,'-') '--------' center('',w,'-') center('',6,'-')
p=1
Do j=1 Until p==0 /* show all entries of linked list*/
Say right(j,6) right(p,8) right(z.p.0value,w) right(z.p.0next,6)
p=z.p.0next
End /* j */
Return</syntaxhighlight>
'''output'''
<pre>
item position value next
------ -------- ------- ------
1 1 3 2
2 2 5 3
3 3 13 4
4 4 17 5
5 5 41 6
6 6 97 7
7 7 113 8
8 8 193 9
9 9 241 10
10 10 257 11
11 11 353 12
12 12 449 0
a new value of 100 has been inserted after element having the value: 97
item position value next
------ -------- ------- ------
1 1 3 2
2 2 5 3
3 3 13 4
4 4 17 5
5 5 41 6
6 6 97 13
7 13 100 7
8 7 113 8
9 8 193 9
10 9 241 10
11 10 257 11
12 11 353 12
13 12 449 0</pre>
=={{header|Ruby}}==
<
def insert_after(search_value, new_value)
if search_value == value
Line 1,697 ⟶ 2,060:
list = ListNode.new(:a, ListNode.new(:b))
list.insert_after(:a, :c)</
=={{header|Rust}}==
Extending [[Singly-Linked List (element)#Rust]]. Please see that page for the Linked List struct declarations.
<
pub fn new() -> Self {
List { head: None }
Line 1,713 ⟶ 2,076:
});
self.head = Some(new_node);
}</
=={{header|Scala}}==
In Scala (and functional programming) we create a new list instead of modifying existing one.
<
/*
Here is a basic list definition
Line 1,729 ⟶ 2,092:
def add[A](as: List[A], a: A): List[A] = Cons(a, as)
}
</syntaxhighlight>
=={{header|Scheme}}==
Non-mutating:
<
(if (null? lst)
lst ; This should be an error, but we will just return the list untouched
Line 1,740 ⟶ 2,103:
(if (equal? a c)
(cons a (cons b cs))
(cons c (insert-after a b cs))))))</
Mutating:
<
(let ((pos (member a lst)))
(if pos
(set-cdr! pos (cons b (cdr pos))))))</
=={{header|Sidef}}==
<
b{:next} = a{:next};
a{:next} = b;
Line 1,766 ⟶ 2,129:
);
insert_after(A, C);</
=={{header|Stata}}==
Line 1,780 ⟶ 2,143:
No error checking is included.
<
proc insertIntoList {existingList predecessor newElement} {
upvar $existingList exList
Line 1,789 ⟶ 2,152:
insertIntoList list A C
puts $list
</syntaxhighlight>
{{out}}
<pre>
A C B
</pre>
=={{header|Wren}}==
{{libheader|Wren-llist}}
<syntaxhighlight lang="wren">import "./llist" for LinkedList
var ll = LinkedList.new(["A", "B"])
ll.insertAfter("A", "C")
System.print(ll)</syntaxhighlight>
{{out}}
<pre>
[A -> C -> B]
</pre>
=={{header|X86 Assembly}}==
<
; x86_64 Linux NASM
; Linked_List_Insert.asm
Line 1,826 ⟶ 2,202:
%endif
</syntaxhighlight>
=={{header|XPL0}}==
<syntaxhighlight lang="xpl0">def \Node\ Link, Data; \linked list element definition
def IntSize = 4; \number of bytes in an integer
proc Insert(List, Node); \Insert Node into List
int List, Node;
[Node(Link):= List(Link);
List(Link):= Node;
];
int MyNode, MyList;
int A, B, C;
[A:= Reserve(2*IntSize);
B:= Reserve(2*IntSize);
C:= Reserve(2*IntSize);
A(Data):= 1;
B(Data):= 2;
C(Data):= 3;
MyList:= A; \make initial list
A(Link):= 0;
Insert(A, B); \insert node B after A
Insert(A, C); \insert node C after A
MyNode:= MyList; \traverse the linked list
while MyNode # 0 do \display the example data
[IntOut(0, MyNode(Data));
ChOut(0, ^ );
MyNode:= MyNode(Link); \move to next node
];
]</syntaxhighlight>
{{out}}
<pre>
1 3 2
</pre>
=={{header|Yabasic}}==
<syntaxhighlight lang="yabasic">// Rosetta Code problem: http://rosettacode.org/wiki/Singly-linked_list/Element_insertion
// 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 printNode(node)
local prevNode
prevNode = searchNode(node)
node = list(prevNode, LINK)
// print list(node, FIL);
print list(node, DATO);
// print list(node, LINK);
print
end sub
insertNode(1, 1000, true)
insertNode(1, 2000, true)
insertNode(1, 3000, true)
printNode(1)
printNode(2)
printNode(3)</syntaxhighlight>{{out}}
<pre>1000
3000
2000
---Program done, press RETURN---</pre>
=={{header|zkl}}==
In place:
<
a:=L("a","b","c"); a.insert(a.find("b"),"foo") //-->L("a","foo","b","c")</
Create a new list:
<
n:=a.index("b"); a[0,n].append("foo").extend(a[n,*]) //-->ROList("a","foo","b","c")</
=={{header|Zig}}==
<syntaxhighlight lang="zig">
const std = @import("std");
var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
const allocator = arena.allocator();
pub fn LinkedList(comptime Value: type) type {
return struct {
const This = @This();
const Node = struct {
value: Value,
next: ?*Node,
};
head: ?*Node,
tail: ?*Node,
pub fn init() This {
return LinkedList(Value) {
.head = null,
.tail = null,
};
}
pub fn add(this: *This, value: Value) !void {
var newNode = try allocator.create(Node);
newNode.* = .{ .value = value, .next = null };
if (this.tail) |tail| {
tail.next = newNode;
this.tail = newNode;
} else if (this.head) |head| {
head.next = newNode;
this.tail = newNode;
} else {
this.head = newNode;
}
}
};
}
</syntaxhighlight>
Create a new list:
<syntaxhighlight lang="zig">
var l1 = LinkedList(i32).init();
</syntaxhighlight>
Add element:
<syntaxhighlight lang="zig">
try list.add(1);
</syntaxhighlight>
|