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
m (→{{header|Wren}}: Minor tidy) |
|||
| (159 intermediate revisions by 85 users not shown) | |||
Line 1:
{{task|Data Structures}}Using the link element defined in [[Singly-Linked List (element)]], define a method to insert an element into a [[singly-linked list]] following a given element.
Using this method, insert an element C into a list comprised of elements A->B, following element A.
{{Template:See also lists}}
<br><br>
=={{header|360 Assembly}}==
The program uses one ASSIST macro (XPRNT) to keep the code as short as possible.
<syntaxhighlight lang="360asm">* Singly-linked list - Insert after 01/02/2017
LISTSINA CSECT
USING LISTSINA,R13 base register
B 72(R15) skip savearea
DC 17F'0' savearea
STM R14,R12,12(R13) prolog
ST R13,4(R15) " <-
ST R15,8(R13) " ->
LR R13,R15 " addressability
* Allocate A
GETMAIN RU,LV=12 get storage
USING NODE,R11 make storage addressable
LR R11,R1 "
MVC VAL,=CL8'A' val='A'
MVC NEXT,=A(0)
DROP R11 base no longer needed
ST R11,A A=@A
* Init LIST
ST R11,LIST init LIST with A
* Allocate C
GETMAIN RU,LV=12 get storage
USING NODE,R11 make storage addressable
LR R11,R1 "
MVC VAL,=CL8'C' val='C'
MVC NEXT,=A(0)
DROP R11 base no longer needed
ST R11,C C=@C
* Insert C After A
MVC P1,A
MVC P2,C
LA R1,PARML
BAL R14,INSERTAF
* Allocate B
GETMAIN RU,LV=12 get storage
USING NODE,R11 make storage addressable
LR R11,R1 "
MVC VAL,=CL8'B' val='B'
MVC NEXT,=A(0)
DROP R11 base no longer needed
ST R11,B B=@B
* Insert B After A
MVC P1,A
MVC P2,B
LA R1,PARML
BAL R14,INSERTAF
* List all
L R11,LIST
USING NODE,R11 address node
LOOP C R11,=A(0)
BE ENDLIST
XPRNT VAL,8
L R11,NEXT
B LOOP
ENDLIST DROP R11
FREEMAIN A=A,LV=12 free A
FREEMAIN A=B,LV=12 free B
FREEMAIN A=C,LV=12 free C
RETURN L R13,4(0,R13) epilog
LM R14,R12,12(R13) " restore
XR R15,R15 " rc=0
BR R14 exit
LIST DS A list head
A DS A
B DS A
C DS A
PARML DS 0A
P1 DS A
P2 DS A
INSERTAF CNOP 0,4
L R2,0(R1) @A
L R3,4(R1) @B
USING NODE,R2 ->A
L R4,NEXT @C
DROP R2
USING NODE,R3 ->B
ST R4,NEXT B.NEXT=@C
DROP R3
USING NODE,R2 ->A
ST R3,NEXT A.NEXT=@B
DROP R2
BR R14 return
LTORG all literals
NODE DSECT node (size=12)
VAL DS CL8
NEXT DS A
YREGS
END LISTSINA</syntaxhighlight>
{{out}}
<pre>
A
B
C
</pre>
=={{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 */
/*******************************************/
/* Constantes file */
/*******************************************/
/* for this file see task include a file in language AArch64 assembly*/
.include "../includeConstantesARM64.inc"
.equ NBELEMENTS, 100 // list size
/*******************************************/
/* Structures */
/********************************************/
/* structure linkedlist*/
.struct 0
llist_next: // next element
.struct llist_next + 8
llist_value: // element value
.struct llist_value + 8
llist_fin:
/*******************************************/
/* Initialized data */
/*******************************************/
.data
szMessInitListe: .asciz "List initialized.\n"
szCarriageReturn: .asciz "\n"
/* datas error display */
szMessErreur: .asciz "Error detected.\n"
/* datas message display */
szMessResult: .asciz "Element No : @ value : @ \n"
sZoneConv: .skip 100
/*******************************************/
/* UnInitialized data */
/*******************************************/
.bss
lList1: .skip llist_fin * NBELEMENTS // list memory place
/*******************************************/
/* code section */
/*******************************************/
.text
.global main
main:
ldr x0,qAdrlList1
mov x1,#0 // list init
str x1,[x0,#llist_next]
ldr x0,qAdrszMessInitListe
bl affichageMess
ldr x0,qAdrlList1
mov x1,#2
bl insertElement // add element value 2
ldr x0,qAdrlList1
mov x1,#5
bl insertElement // add element value 5
//
ldr x3,qAdrlList1
mov x2,#0 // ident element
1:
ldr x0,[x3,#llist_next] // end list ?
cmp x0,#0
beq 100f // yes
add x2,x2,#1
mov x0,x2 // display No element and value
ldr x1,qAdrsZoneConv
bl conversion10S
ldr x0,qAdrszMessResult
ldr x1,qAdrsZoneConv
bl strInsertAtCharInc
mov x5,x0 // address of new string
ldr x0,[x3,#llist_value]
ldr x1,qAdrsZoneConv
bl conversion10S
mov x0,x5 // new address of message
ldr x1,qAdrsZoneConv
bl strInsertAtCharInc
bl affichageMess
ldr x3,[x3,#llist_next] // next element
b 1b // and loop
100: // standard end of the program
mov x8, #EXIT // request to exit program
svc 0 // perform system call
qAdrszMessInitListe: .quad szMessInitListe
qAdrszMessErreur: .quad szMessErreur
qAdrszCarriageReturn: .quad szCarriageReturn
qAdrlList1: .quad lList1
qAdrszMessResult: .quad szMessResult
qAdrsZoneConv: .quad sZoneConv
/******************************************************************/
/* insert element at end of list */
/******************************************************************/
/* x0 contains the address of the list */
/* x1 contains the value of element */
/* x0 returns address of element or - 1 if error */
insertElement:
stp x1,lr,[sp,-16]! // save registers
stp x2,x3,[sp,-16]! // save registers
mov x2,#llist_fin * NBELEMENTS
add x2,x2,x0 // compute address end list
1: // start loop
ldr x3,[x0,#llist_next] // load next pointer
cmp x3,#0 // = zero
csel x0,x3,x0,ne
bne 1b // no -> loop with pointer
add x3,x0,#llist_fin // yes -> compute next free address
cmp x3,x2 // > list end
bge 99f // yes -> error
str x3,[x0,#llist_next] // store next address in current pointer
str x1,[x0,#llist_value] // store element value
mov x1,#0
str x1,[x3,#llist_next] // init next pointer in next address
b 100f
99: // error
mov x0,-1
100:
ldp x2,x3,[sp],16 // restaur 2 registers
ldp x1,lr,[sp],16 // restaur 2 registers
ret // return to address lr x30
/********************************************************/
/* File Include fonctions */
/********************************************************/
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
</syntaxhighlight>
=={{header|ACL2}}==
<syntaxhighlight lang="lisp">(defun insert-after (x e xs)
(cond ((endp xs)
nil)
((equal x (first xs))
(cons (first xs)
(cons e (rest xs))))
(t (cons (first xs)
(insert-after x e (rest xs))))))</syntaxhighlight>
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:
<syntaxhighlight lang="actionscript">package
{
public class Node
{
public var data:Object = null;
public var link:Node = null;
public function insert(node:Node):void
{
node.link = link;
link = node;
}
}
}</syntaxhighlight>
Usage:
<syntaxhighlight lang="actionscript">import Node;
var A:Node = new Node(1);
var B:Node = new Node(2);
var C:Node = new Node(3);
A.insert(B);
A.insert(C);</syntaxhighlight>
=={{header|Ada}}==
We must create a context clause making the predefined generic procedure Ada.Unchecked_Deallocation visible to this program.
<syntaxhighlight lang="ada">with Ada.Unchecked_Deallocation;
-- Define the link type
procedure Singly_Linked is
type Link;
type Link_Access is access Link;
type Link is record
Data : Integer;
Next : Link_Access := null;
end record;
-- Instantiate the generic deallocator for the link type
procedure Free is new Ada.Unchecked_Deallocation(Link, Link_Access);
-- Define the procedure
procedure Insert_Append(Anchor : Link_Access; Newbie : Link_Access) is
begin
if Anchor /= null and Newbie /= null then
Newbie.Next := Anchor.Next;
Anchor.Next := Newbie;
end if;
end Insert_Append;
-- Create the link elements
A : Link_Access := new Link'(1, null);
B : Link_Access := new Link'(2, null);
C : Link_Access := new Link'(3, null);
-- Execute the program
begin
Insert_Append(A, B);
Insert_Append(A, C);
Free(A);
Free(B);
Free(C);
end Singly_Linked;</syntaxhighlight>
=={{header|ALGOL 68}}==
Linked lists are not built into ALGOL 68 ''per se'', nor any available
standard library. However Linked lists are presented in standard text
book examples. Or can be manually constructed, eg:
<syntaxhighlight lang="algol68">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))))));
PROC insert = (REF STRINGLIST list, node)VOID: (
next OF node := next OF list;
next OF list := node
);
STRINGLIST very := ("VERY", NIL);
# EXAMPLE OF INSERTION #
insert(next OF next OF list, very );
REF STRINGLIST node := list;
WHILE REF STRINGLIST(node) ISNT NIL DO
print((value OF node, space));
node := next OF node
OD;
print((newline))</syntaxhighlight>
Output:<pre>Big fjords vex VERY quick waltz nymph </pre>
=={{header|ALGOL W}}==
<syntaxhighlight lang="algolw"> % inserts a new value after the specified element of a list %
procedure insert( reference(ListI) value list
; integer value newValue
) ;
next(list) := ListI( newValue, next(list) );
% declare a variable to hold a list %
reference(ListI) head;
% create a list of integers %
head := ListI( 1701, ListI( 9000, ListI( 42, ListI( 90210, null ) ) ) );
% insert a new value into the list %
insert( next(head), 4077 );</syntaxhighlight>
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi}}
<syntaxhighlight lang="arm assembly">
/* ARM assembly Raspberry PI */
/* program insertList.s */
/* Constantes */
.equ STDOUT, 1 @ Linux output console
.equ EXIT, 1 @ Linux syscall
.equ READ, 3
.equ WRITE, 4
.equ NBELEMENTS, 100 @ list size
/*******************************************/
/* Structures */
/********************************************/
/* structure linkedlist*/
.struct 0
llist_next: @ next element
.struct llist_next + 4
llist_value: @ element value
.struct llist_value + 4
llist_fin:
/* Initialized data */
.data
szMessInitListe: .asciz "List initialized.\n"
szCarriageReturn: .asciz "\n"
/* datas error display */
szMessErreur: .asciz "Error detected.\n"
/* datas message display */
szMessResult: .ascii "Element No :"
sNumElement: .space 12,' '
.ascii " value : "
sValue: .space 12,' '
.asciz "\n"
/* UnInitialized data */
.bss
lList1: .skip llist_fin * NBELEMENTS @ list memory place
/* code section */
.text
.global main
main:
ldr r0,iAdrlList1
mov r1,#0 @ list init
str r1,[r0,#llist_next]
ldr r0,iAdrszMessInitListe
bl affichageMess
ldr r0,iAdrlList1
mov r1,#2
bl insertElement @ add element value 2
ldr r0,iAdrlList1
mov r1,#5
bl insertElement @ add element value 5
ldr r3,iAdrlList1
mov r2,#0 @ ident element
1:
ldr r0,[r3,#llist_next] @ end list ?
cmp r0,#0
beq 100f @ yes
add r2,#1
mov r0,r2 @ display No element and value
ldr r1,iAdrsNumElement
bl conversion10S
ldr r0,[r3,#llist_value]
ldr r1,iAdrsValue
bl conversion10S
ldr r0,iAdrszMessResult
bl affichageMess
ldr r3,[r3,#llist_next] @ next element
b 1b @ and loop
100: @ standard end of the program
mov r7, #EXIT @ request to exit program
svc 0 @ perform system call
iAdrszMessInitListe: .int szMessInitListe
iAdrszMessErreur: .int szMessErreur
iAdrszCarriageReturn: .int szCarriageReturn
iAdrlList1: .int lList1
iAdrszMessResult: .int szMessResult
iAdrsNumElement: .int sNumElement
iAdrsValue: .int sValue
/******************************************************************/
/* insert element at end of list */
/******************************************************************/
/* r0 contains the address of the list */
/* r1 contains the value of element */
/* r0 returns address of element or - 1 if error */
insertElement:
push {r1-r3,lr} @ save registers
mov r2,#llist_fin * NBELEMENTS
add r2,r0 @ compute address end list
1: @ start loop
ldr r3,[r0,#llist_next] @ load next pointer
cmp r3,#0 @ = zero
movne r0,r3 @ no -> loop with pointer
bne 1b
add r3,r0,#llist_fin @ yes -> compute next free address
cmp r3,r2 @ > list end
movge r0,#-1 @ yes -> error
bge 100f
str r3,[r0,#llist_next] @ store next address in current pointer
str r1,[r0,#llist_value] @ store element value
mov r1,#0
str r1,[r3,#llist_next] @ init next pointer in next address
100:
pop {r1-r3,lr} @ restaur registers
bx lr @ return
/******************************************************************/
/* display text with size calculation */
/******************************************************************/
/* r0 contains the address of the message */
affichageMess:
push {r0,r1,r2,r7,lr} @ save registers
mov r2,#0 @ counter length */
1: @ loop length calculation
ldrb r1,[r0,r2] @ read octet start position + index
cmp r1,#0 @ if 0 its over
addne r2,r2,#1 @ else add 1 in the length
bne 1b @ and loop
@ so here r2 contains the length of the message
mov r1,r0 @ address message in r1
mov r0,#STDOUT @ code to write to the standard output Linux
mov r7, #WRITE @ code call system "write"
svc #0 @ call system
pop {r0,r1,r2,r7,lr} @ restaur registers
bx lr @ return
/***************************************************/
/* Converting a register to a signed decimal */
/***************************************************/
/* r0 contains value and r1 area address */
conversion10S:
push {r0-r4,lr} @ save registers
mov r2,r1 @ debut zone stockage
mov r3,#'+' @ par defaut le signe est +
cmp r0,#0 @ negative number ?
movlt r3,#'-' @ yes
mvnlt r0,r0 @ number inversion
addlt r0,#1
mov r4,#10 @ length area
1: @ start loop
bl divisionpar10U
add r1,#48 @ digit
strb r1,[r2,r4] @ store digit on area
sub r4,r4,#1 @ previous position
cmp r0,#0 @ stop if quotient = 0
bne 1b
strb r3,[r2,r4] @ store signe
subs r4,r4,#1 @ previous position
blt 100f @ if r4 < 0 -> end
mov r1,#' ' @ space
2:
strb r1,[r2,r4] @store byte space
subs r4,r4,#1 @ previous position
bge 2b @ loop if r4 > 0
100:
pop {r0-r4,lr} @ restaur registers
bx lr
/***************************************************/
/* division par 10 unsigned */
/***************************************************/
/* r0 dividende */
/* r0 quotient */
/* r1 remainder */
divisionpar10U:
push {r2,r3,r4, lr}
mov r4,r0 @ save value
//mov r3,#0xCCCD @ r3 <- magic_number lower raspberry 3
//movt r3,#0xCCCC @ r3 <- magic_number higter raspberry 3
ldr r3,iMagicNumber @ r3 <- magic_number raspberry 1 2
umull r1, r2, r3, r0 @ r1<- Lower32Bits(r1*r0) r2<- Upper32Bits(r1*r0)
mov r0, r2, LSR #3 @ r2 <- r2 >> shift 3
add r2,r0,r0, lsl #2 @ r2 <- r0 * 5
sub r1,r4,r2, lsl #1 @ r1 <- r4 - (r2 * 2) = r4 - (r0 * 10)
pop {r2,r3,r4,lr}
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
b_next = 0
c = 3
insert_after("c", "a")
Listvars
msgbox
return
insert_after(new, old)
{
local temp
temp := %old%_next
%old%_next := new
%new%_next := temp
}</syntaxhighlight>
=={{header|Axe}}==
<syntaxhighlight lang="axe">Lbl INSERT
{r₁+2}ʳ→{r₂+2}ʳ
r₂→{r₁+2}ʳ
r₁
Return</syntaxhighlight>
=={{header|BBC BASIC}}==
{{works with|BBC BASIC for Windows}}
<syntaxhighlight lang="bbcbasic"> DIM node{pNext%, iData%}
DIM a{} = node{}, b{} = node{}, c{} = node{}
a.pNext% = b{}
a.iData% = 123
b.iData% = 789
c.iData% = 456
PROCinsert(a{}, c{})
END
DEF PROCinsert(here{}, new{})
new.pNext% = here.pNext%
here.pNext% = new{}
ENDPROC
</syntaxhighlight>
=={{header|C}}==
Define the method:
}</syntaxhighlight>
Note that in a production implementation, one should check anchor and newlink to ensure they're valid values.
And now on to the code.
Create our links.
Prepare our initial list
Insert element c after element a
Remember to free the memory once we're done.
free (b);
free (c);</syntaxhighlight>
==
Uses the generic version of the node type located [[Singly-linked_list/Element_definition#C#|here]].
Creates nodes and inserts them from the data passed.
<syntaxhighlight lang="csharp">static void InsertAfter<T>(LinkedListNode<T> prev, T value)
{
prev.Next = new Link() { Value = value, Next = prev.Next };
}</syntaxhighlight>
<syntaxhighlight lang="csharp">static void Main()
{
//Create A(5)->B(7)
var A = new LinkedListNode<int>() { Value = 5 };
InsertAfter(A, 7);
//Insert C between A and B
InsertAfter(A, 15);
}</syntaxhighlight>
=={{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.
};</syntaxhighlight>
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.
Now insert c after a:
Finally destroy the list:
}</syntaxhighlight>
=={{header|Clojure}}==
<syntaxhighlight lang="lisp">(defn insert-after [new old ls]
(cond (empty? ls) ls
(= (first ls) old) (cons old (cons new (rest ls)))
:else (cons (first ls) (insert-after new old (rest ls)))))</syntaxhighlight>
And the test:
<syntaxhighlight lang="lisp">user=> (insert-after 'c 'a '(a b))
(a c b)</syntaxhighlight>
=={{header|Common Lisp}}==
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.
<syntaxhighlight lang="lisp">(defun insert-after (new-element old-element list &key (test 'eql))
"Return a list like list, but with new-element appearing after the
first occurence of old-element. If old-element does not appear in
list, then a list returning just new-element is returned."
(if (endp list) (list new-element)
(do ((head (list (first list)) (cons (first tail) head))
(tail (rest list) (rest tail)))
((or (endp tail) (funcall test old-element (first head)))
(nreconc head (cons new-element tail))))))
(defun ninsert-after (new-element old-element list &key (test 'eql))
"Like insert-after, but modifies list in place. If list is empty, a
new list containing just new-element is returned."
(if (endp list) (list new-element)
(do ((prev list next)
(next (cdr list) (cdr next)))
((or (null next) (funcall test old-element (car prev)))
(rplacd prev (cons new-element next))
list))))</syntaxhighlight>
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.
<syntaxhighlight lang="lisp">(defun simple-insert-after (new-element old-element list &key (test 'eql))
(let ((tail (rest (member old-element list :test test))))
(nconc (ldiff list tail)
(cons new-element tail))))</syntaxhighlight>
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.)
<syntaxhighlight lang="lisp">(defun insert-after (list new existing &key (test #'eql))
"Insert item new into list, before existing, or at the end if existing
is not present. The default comparison test function is EQL. This
function destroys the original list and returns the new list."
(cond
;; case 1: list is empty: just return list of new
((endp list)
(list new))
;; case 2: existing element is first element of list
((funcall test (car list) existing)
`(,(car list) ,new ,@(cdr list)))
;; case 3: recurse: insert the element into the rest of the list,
;; and make that list the new rest.
(t (rplacd list (insert-before (cdr list) new existing :test test))
list)))</syntaxhighlight>
=={{header|D}}==
<syntaxhighlight lang="d">struct SLinkedNode(T) {
T data;
typeof(this)* next;
}
void insertAfter(T)(SLinkedNode!T* listNode, SLinkedNode!T* newNode) {
newNode.next = listNode.next;
listNode.next = newNode;
}
void main() {
alias N = SLinkedNode!char;
auto lh = new N('A', new N('B'));
auto c = new N('C');
// Inserts C after A, creating the (A C B) list:
insertAfter(lh, c);
// The GC will collect the memory.
}</syntaxhighlight>
=={{header|Delphi}}==
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 (* ... *).
<syntaxhighlight lang="delphi">// Using the same type defs from the one way list example.
Type
Line 148 ⟶ 1,004:
end;
// I will
// new node or it will return NIL. In this example I will always insert
// right, to keep the code clear. Since I am using a function all operations
// for the new node will be conducted on the functions result. This seems
//
Function InsertNode(VAR CurrentNode:pOneWayList): pOneWayList
Line 159 ⟶ 1,015:
// I try not to introduce different parts of the language, and keep each
// example to just the code required. in this case it is important to use
// a try/
// running at the same time, you cannot rely on a call to check memory available
// and then attempting to allocate. In the time between the two, another
Line 165 ⟶ 1,021:
Try
// Try to allocate enough memory for a
GetMem(Result,SizeOf(OneWayList));
Except
Line 192 ⟶ 1,048:
CurrentNode.Next := result ;
end;
end;</syntaxhighlight>
=={{header|E}}==
<syntaxhighlight lang="e">def insertAfter(head :LinkedList ? (!head.null()),
new :LinkedList ? (new.next().null())) {
new.setNext(head.next())
head.setNext(new)
}
def a := makeLink(1, empty)
def b := makeLink(2, empty)
def c := makeLink(3, empty)
insertAfter(a, b)
insertAfter(a, c)
var x := a
while (!x.null()) {
println(x.value())
x := x.next()
}</syntaxhighlight>
=={{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.
<syntaxhighlight lang="lisp">
(define (insert-after lst target item)
(when (null? lst) (error "cannot insert in" null))
(let [(sub-list (member target lst))]
(if sub-list (set-cdr! sub-list (cons item (cdr sub-list))) ; make chirurgy if found
(nconc lst item)))) ; else append item
(define L '(a b))
(insert-after L 'a 'c)
L → (a c b)
(insert-after L 'x 'y)
L → (a c b y)
</syntaxhighlight>
=={{header|Elena}}==
<syntaxhighlight lang="elena">singleton linkHelper
{
insertAfter(Link prev, IntNumber i)
{
prev.Next := new Link(i, prev.Next)
}
}</syntaxhighlight>
=={{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 ).
-export( [append/2, foreach/2, free/1, insert/3, new/1, task/0] ).
append( New, Start ) -> Start ! {append, New}.
foreach( Fun, Start ) -> Start ! {foreach, Fun}.
free( Element ) -> Element ! {free}.
insert( New, After, Start ) -> Start ! {insert, New, After}.
new( Data ) -> erlang:spawn( fun() -> loop( Data, nonext ) end ).
task() ->
A = new( a ),
B = new( b ),
append( B, A ),
C = new( c ),
insert( C, A, A ),
foreach( fun(Data) -> io:fwrite("~p~n", [Data]) end, A ).
loop( Data, Next ) ->
My_pid = erlang:self(),
receive
{append, New} ->
New_next = loop_append( New, Next ),
loop( Data, New_next );
{foreach, Fun} ->
catch Fun( Data ),
loop_foreach( Fun, Next ),
loop( Data, Next );
{free} ->
ok;
{insert, New, My_pid} ->
append( Next, New ),
loop( Data, New );
{insert, New, After} ->
Next ! {insert, New, After},
loop( Data, Next )
end.
loop_append( New, nonext ) -> New;
loop_append( New, Next ) ->
Next ! {append, New},
Next.
loop_foreach( _Fun, nonext ) -> ok;
loop_foreach( Fun, Next ) -> Next ! {foreach, Fun}.
</syntaxhighlight>
{{out}}
<pre>
4> singly_linked_list:task().
a
c
b
</pre>
=={{header|Factor}}==
<syntaxhighlight lang="factor">: list-append ( previous new -- )
[ swap next>> >>next drop ] [ >>next drop ] 2bi ;
SYMBOLS: A B C ;
A <linked-list>
[ C <linked-list> list-append ] keep
[ B <linked-list> list-append ] keep
.</syntaxhighlight>
Output:
<pre>
T{ linked-list
{ data A }
{ next
T{ linked-list
{ data B }
{ next T{ linked-list { data C } } }
}
}
}
</pre>
=={{header|Fantom}}==
Extending Node class from [[Singly-Linked_List_(element)]]:
<syntaxhighlight lang="fantom">
class Node
{
const Int value
Node? successor // can be null, for end of series
new make (Int value, Node? successor := null)
{
this.value = value
this.successor = successor
}
// insert method for this problem
public Void insert (Node newNode)
{
newNode.successor = this.successor
this.successor = newNode
}
}
// simple class to test putting 'c' between 'a' and 'b'
class Main
{
public static Void main ()
{
c := Node (2)
b := Node (3)
a := Node (1, b)
a.insert (c)
echo (a.value)
echo (a.successor.value)
echo (a.successor.successor.value)
}
}
</syntaxhighlight>
Output:
<pre>
1
2
3
</pre>
=={{header|Forth}}==
Using the linked list concept described in the [[Singly-Linked_List_(element)]] topic:
<syntaxhighlight lang="forth">\ Create the list and some list elements
create A 0 , char A ,
create B 0 , char B ,
create C 0 , char C ,</syntaxhighlight>
Now insert b after a and c after b, giving a->b->c
<syntaxhighlight lang="forth">B A chain
C B chain</syntaxhighlight>
Here is an abbreviated version of the definition of 'chain' from the other article:
<syntaxhighlight lang="forth"> : chain ( a b -- ) 2dup @ swap ! ! ;</syntaxhighlight>
=={{header|Fortran}}==
In ISO Fortran 95 or later:
<syntaxhighlight lang="fortran">elemental subroutine addAfter(nodeBefore,value)
type (node), intent(inout) :: nodeBefore
real, intent(in) :: value
type (node), pointer :: newNode
allocate(newNode)
newNode%data = value
newNode%next => nodeBefore%next
nodeBefore%next => newNode
end subroutine addAfter</syntaxhighlight>
=={{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}}==
<syntaxhighlight lang="go">package main
import "fmt"
type Ele struct {
Data interface{}
Next *Ele
}
func (e *Ele) insert(data interface{}) {
if e == nil {
panic("attept to modify nil")
}
e.Next = &Ele{data, e.Next}
}
func (e *Ele) printList() {
if e == nil {
fmt.Println(nil)
return
}
fmt.Printf("(%v", e.Data)
for {
e = e.Next
if e == nil {
fmt.Println(")")
return
}
fmt.Print(" ", e.Data)
}
}
func main() {
h := &Ele{"A", &Ele{"B", nil}}
h.printList()
h.insert("C")
h.printList()
}</syntaxhighlight>
Output:
<pre>
(A B)
(A C B)
</pre>
=={{header|Groovy}}==
Solution (uses ListNode from [[Singly-Linked List (element)#Groovy]]):
<syntaxhighlight lang="groovy">class NodeList {
private enum Flag { FRONT }
private ListNode head
void insert(value, insertionPoint=Flag.FRONT) {
if (insertionPoint == Flag.FRONT) {
head = new ListNode(payload: value, next: head)
} else {
def node = head
while (node.payload != insertionPoint) {
node = node.next
if (node == null) {
throw new IllegalArgumentException(
"Insertion point ${afterValue} not already contained in list")
}
}
node.next = new ListNode(payload:value, next:node.next)
}
}
String toString() { "${head}" }
}</syntaxhighlight>
Test:
<syntaxhighlight lang="groovy">def list = new NodeList()
list.insert('B')
list.insert('A')
println list
list.insert('C', 'A')
println list</syntaxhighlight>
Output:
<pre>A -> B -> null
A -> C -> B -> null</pre>
=={{header|Haskell}}==
This kind of list manipulation is [[unidiomatic]] Haskell. But you can try the following:
<syntaxhighlight lang="haskell">insertAfter a b (c:cs) | a==c = a : b : cs
| otherwise = c : insertAfter a b cs
insertAfter _ _ [] = error "Can't insert"</syntaxhighlight>
==Icon and Unicon==
The Icon solution works for both Icon and Unicon, but Unicon permits a class-based solution.
==={{header|Icon}}===
<syntaxhighlight lang="icon">
record Node (value, successor)
procedure insert_node (node, newNode)
newNode.successor := node.successor
node.successor := newNode
end
</syntaxhighlight>
==={{header|Unicon}}===
<syntaxhighlight lang="unicon">
class Node (value, successor)
method insert (node)
node.successor := self.successor
self.successor := node
end
initially (value, successor)
self.value := value
self.successor := successor
end
</syntaxhighlight>
=={{header|J}}==
<syntaxhighlight lang="j">list=: 1 65,:_ 66
A=:0 NB. reference into list
B=:1 NB. reference into list
insertAfter=: monad define
'localListName localListNode localNewValue'=. y
localListValue=: ".localListName
localOldLinkRef=: <localListNode,0
localNewLinkRef=: #localListValue
localNewNode=: (localOldLinkRef { localListValue), localNewValue
(localListName)=: (localNewLinkRef localOldLinkRef} localListValue), localNewNode
)</syntaxhighlight>
With these definitions:
insertAfter 'list';A;67
updates the list inserting the value for C after the value for A.
That said, note that the underlying mechanism is rather silly, for J. Linked lists are only interesting in J for illustrative purposes, and should not be used in code that anyone cares about. I have supplied a correspondingly verbose implementation.
=={{header|Java}}==
Extending [[Singly-Linked_List_(element)#Java]]
<syntaxhighlight lang="java">void insertNode(Node<T> anchor_node, Node<T> new_node)
{
new_node.next = anchor_node.next;
anchor_node.next = new_node;
}</syntaxhighlight>
{{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).
=={{header|JavaScript}}==
Extending [[Singly-Linked_List_(element)#JavaScript]]
<syntaxhighlight lang="javascript">LinkedList.prototype.insertAfter = function(searchValue, nodeToInsert) {
if (this._value == searchValue) {
nodeToInsert.next(this.next());
this.next(nodeToInsert);
}
else if (this.next() == null)
throw new Error(0, "value '" + searchValue + "' not found in linked list.")
else
this.next().insertAfter(searchValue, nodeToInsert);
}
var list = createLinkedListFromArray(['A','B']);
list.insertAfter('A', new LinkedList('C', null));</syntaxhighlight>
=={{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}}==
{{works with|Julia|0.6}}
See the <tt>LinkedList</tt> implemented at [[Singly-linked_list/Element_definition#Julia]].
<syntaxhighlight lang="julia">function Base.insert!(ll::LinkedList{T}, index::Integer, item::T) where T
if index == 1
if isempty(ll)
return push!(ll, item)
else
ll.head = Node{T}(item, ll.head)
end
else
nd = ll.head
while index > 2
if nd.next isa EmptyNode
throw(BoundsError())
else
nd = nd.next
index -= 1
end
end
nd.next = Node{T}(item, nd.next)
end
return ll
end</syntaxhighlight>
=={{header|Kotlin}}==
<syntaxhighlight 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 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")
}</syntaxhighlight>
{{out}}
<pre>
Before insertion : 1 -> 3
After insertion : 1 -> 2 -> 3
</pre>
=={{header|Logo}}==
<syntaxhighlight lang="logo">to insert :after :list :value
localmake "tail member :after :list
if not empty? :tail [.setbf :tail fput :value bf :tail]
output :list
end
show insert 5 [3 5 1 8] 2</syntaxhighlight>
[3 5 2 1 8]
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">Append[{a, b}, c]
->{a, b, c}</syntaxhighlight>
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}}==
<syntaxhighlight lang="modula3">MODULE SinglyLinkedList EXPORTS Main;
TYPE
Link = REF LinkRcd;
LinkRcd = RECORD
Next: Link;
Data: INTEGER
END;
PROCEDURE InsertAppend(anchor, next: Link) =
BEGIN
IF anchor # NIL AND next # NIL THEN
next.Next := anchor.Next;
anchor.Next := next
END
END InsertAppend;
VAR
a: Link := NEW(Link, Next := NIL, Data := 1);
b: Link := NEW(Link, Next := NIL, Data := 2);
c: Link := NEW(Link, Next := NIL, Data := 3);
BEGIN
InsertAppend(a, b);
InsertAppend(a, c)
END SinglyLinkedList.</syntaxhighlight>
=={{header|Nim}}==
<syntaxhighlight lang="nim">type Node[T] = ref object
next: Node[T]
data: T
proc newNode[T](data: T): Node[T] =
Node[T](data: data)
var a = newNode 12
var b = newNode 13
var c = newNode 14
proc insertAppend(a, n: var Node) =
n.next = a.next
a.next = n
a.insertAppend(b)
b.insertAppend(c)</syntaxhighlight>
=={{header|OCaml}}==
This kind of list manipulation is unidiomatic OCaml. But you can try the following:
<syntaxhighlight lang="ocaml">let rec insert_after a b = function
c :: cs when a = c -> a :: b :: cs
| c :: cs -> c :: insert_after a b cs
| [] -> raise Not_found</syntaxhighlight>
=={{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}}==
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).
<syntaxhighlight lang="oforth">Collection Class new: LinkedList(data, mutable next)
LinkedList method: initialize := next := data ;
LinkedList method: data @data ;
LinkedList method: next @next ;
LinkedList method: add(e) e @next LinkedList new := next ;
LinkedList method: forEachNext
dup ifNull: [ drop self ]
dup 1 ifEq: [ drop false return ]
dup next dup ifNull: [ drop 1 ]
swap data true ;
: testLink LinkedList new($A, null) dup add($B) dup add($C) ;
testLink println</syntaxhighlight>
{{out}}
<pre>
[A, C, B]
</pre>
=={{header|ooRexx}}==
See [[Singly-linked_list/Element_definition#ooRexx|Single-linked list/Element definition]] for full class definition.
<syntaxhighlight lang="oorexx">
list = .list~new
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}}==
Note: This code uses only Standard Pascal features. For code using features only available in modern Pascal versions, see above under "[Delphi / Object Pascal / >>Turbo Pascal<<]"
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.
<syntaxhighlight lang="pascal">type
pCharNode = ^CharNode;
CharNode = record
data: char;
next: pCharNode;
end;
(* This procedure inserts a node (newnode) directly after another node which is assumed to already be in a list.
It does not allocate a new node, but takes an already allocated node, thus allowing to use it (together with
a procedure to remove a node from a list) for splicing a node from one list to another. *)
procedure InsertAfter(listnode, newnode: pCharNode);
begin
newnode^.next := listnode^.next;
listnode^.next := newnode;
end;</syntaxhighlight>
Usage example:
<syntaxhighlight lang="pascal">var
A, B: pCharNode;
begin
(* build the two-component list A->C manually *)
new(A);
A^.data := 'A';
new(A^.next);
A^.next^.data := 'C';
A^.next^.next := nil;
(* create the node to be inserted. The initialization of B^.next isn't strictly necessary
(it gets overwritten anyway), but it's good style not to leave any values undefined. *)
new(B);
node^.data := 'B';
node^.next := nil;
(* call the above procedure to insert node B after node A *)
InsertAfter(A, B);
(* delete the list *)
while A <> nil do
begin
B := A;
A := A^.next;
dispose(B);
end
end.</syntaxhighlight>
=={{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.
<syntaxhighlight lang="perl">my @l = ($A, $B);
push @l, $C, splice @l, 1;</syntaxhighlight>
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.
<syntaxhighlight lang="perl">sub insert_after {
# first argument: node to insert after
# second argument: node to insert
$_[1]{next} = $_[0]{next};
$_[0]{next} = $_[1];
}
my %B = (
data => 3,
next => undef, # not a circular list
);
my %A = (
data => 1,
next => \%B,
);
my %C = (
data => 2,
);
insert_after \%A, \%C;</syntaxhighlight>
Note that you don't have to name your new nodes. The following works just as well:
<syntaxhighlight lang="perl"> insert_after \%A, { data => 2 };</syntaxhighlight>
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:
<syntaxhighlight lang="perl">sub insert_after {
my $node = $_[0];
my $next = $node->{next};
shift;
while (defined $_[0]) {
$node->{next} = $_[0];
$node = $node->{next};
shift;
}
$node->{next} = $next;
}</syntaxhighlight>
With this, it's rather easy to build a list:
<syntaxhighlight lang="perl">my %list = ( data => 'A' );
insert_after \%list, { data => 'B' }, { data => 'C' };</syntaxhighlight>
List handling is simplified if the variables themselves contain references. For example:
<syntaxhighlight lang="perl">my $list2;
# create a new list ('A'. 'B', 'C') and store it in $list2
insert_after $list2 = { data => 'A' }, { data => 'B' }, { data => 'C' };
# append two new nodes ('D', 'E') after the first element
insert_after $list2, { data => 'A2' }, { data => 'A3' };
# append new nodes ('A2a', 'A2b') after the second element (which now is 'A2')
insert_after $list2->{next}, { data => 'A2a' }, { data => 'A2b' };</syntaxhighlight>
=={{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>
{{2},{3,"ONE"},{4,"TWO"},{1,"THREE"}}
</pre>
=={{header|PicoLisp}}==
Destructive operation
<syntaxhighlight lang="picolisp">(de insertAfter (Item Lst New)
(when (member Item Lst)
(con @ (cons New (cdr @))) )
Lst )</syntaxhighlight>
Non-destructive operation
<syntaxhighlight lang="picolisp">(de insertAfter (Item Lst New)
(if (index Item Lst)
(conc (cut @ 'Lst) (cons New Lst))
Lst ) )</syntaxhighlight>
Output in both cases:
<pre>: (insertAfter 'A '(A B) 'C)
-> (A C B)
: (insertAfter 'A '(X Y Z A B D E) 'C)
-> (X Y Z A C B D E)</pre>
=={{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. */
allocate node set (Q);
node.p = H; /* The new node now points at the list where we want to insert it. */
node.value = V;
H->p = Q; /* Break the list at H, and point it at the new node. */
</syntaxhighlight>
=={{header|Pop11}}==
In Pop11 one normally uses built-in lists:
<syntaxhighlight lang="pop11">define insert_into_list(anchor, x);
cons(x, back(anchor)) -> back(anchor);
enddefine;
;;; Build inital list
lvars l1 = cons("a", []);
insert_into_list(l1, "b");
;;; insert c
insert_into_list(l1, "c");</syntaxhighlight>
If one wants one can use user-defined list node (for convenience we repeat definition of list node):
<syntaxhighlight lang="pop11">uses objectclass;
define :class ListNode;
slot value = [];
slot next = [];
enddefine;
define insert_into_List(anchor, x);
consListNode(x, next(anchor)) -> next(anchor);
enddefine;
;;; Build inital list
lvars l2 = consListNode("a", []);
insert_into_List(l2, "b");
;;; insert c
insert_into_List(l2, "c");</syntaxhighlight>
Note that user-defined case differs from built-in case only because of names.
=={{header|PureBasic}}==
<syntaxhighlight lang="purebasic">Procedure insertAfter(Value, *node.MyData = #Null)
Protected *newNode.MyData = AllocateMemory(SizeOf(MyData))
If *newNode
If *node
*newNode\next = *node\next
*node\next = *newNode
EndIf
*newNode\Value = Value
EndIf
ProcedureReturn *newNode ;return pointer to newnode
EndProcedure
Define *SL_List.MyData, a = 1, b = 2, c = 3
*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</syntaxhighlight>
=={{header|Python}}==
<syntaxhighlight lang="python">def chain_insert(lst, at, item):
while lst is not None:
if lst[0] == at:
lst[1] = [item, lst[1]]
return
else:
lst = lst[1]
raise ValueError(str(at) + " not found")
chain = ['A', ['B', None]]
chain_insert(chain, 'A', 'C')
print chain</syntaxhighlight>
Output:
<syntaxhighlight lang="python">['A', ['C', ['B', None]]]</syntaxhighlight>
=={{header|Racket}}==
<syntaxhighlight lang="racket">
#lang racket
;; insert b after a in a mutable list (assumes that a is in the input list)
(define (insert-after! list a b)
(if (equal? (mcar list) a)
(set-mcdr! list (mcons b (mcdr list)))
(insert-after! (mcdr list) a b)))
(define l (mcons 1 (mcons 2 (mcons 3 '()))))
(insert-after! l 2 2.5)
l ; -> (mcons 1 (mcons 2 (mcons 2.5 (mcons 3))))
</syntaxhighlight>
=={{header|Raku}}==
(formerly Perl 6)
Extending <tt>class Cell</tt> from [[Singly-linked_list/Element_definition#Raku]]:
<syntaxhighlight lang="raku" line> method insert ($value) {
$.next = Cell.new(:$value, :$.next)
}</syntaxhighlight>
=={{header|REXX}}==
<syntaxhighlight lang="rexx">/*REXX program demonstrates how to create a single-linked list */
/* and how to insert an element */
z.=0 /* define a null linked z. */
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
newval=100 /* Insert this value */
after=97 /* after the element with this value */
nnn=z..after /* position of z´this value */
Call ins_list nnn,newval /* perform the insertion */
Say ''
Say 'a new value of' newval 'has been inserted',
'after element having the value:' after
Call show_list
Exit /* stick a fork in it, we're done.*/
set_list: Procedure Expose z.
Parse Arg value /* get element to be added to list*/
last=z.0 /* set the previous last element. */
new=z.0+1 /* set the new ast element. */
z.0=new /* define next item in linked list*/
z.last.0next=new /* set the next pointer value. */
z.new.0value=value /* set item to the value specified*/
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.nnn.0next=last /* next element */
z..value=last /* store position of the new value*/
z.0width=max(z.0width,length(value)) /*set maximum width of any value*/
Return
show_list:
Say
w=max(7,z.0width) /* use the max width of nums or 7.*/
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}}==
<syntaxhighlight lang="ruby">class ListNode
def insert_after(search_value, new_value)
if search_value == value
self.succ = self.class.new(new_value, succ)
elsif self.succ.nil?
raise StandardError, "value #{search_value} not found in list"
else
self.succ.insert_after(search_value, new_value)
end
end
end
list = ListNode.new(:a, ListNode.new(:b))
list.insert_after(:a, :c)</syntaxhighlight>
=={{header|Rust}}==
Extending [[Singly-Linked List (element)#Rust]]. Please see that page for the Linked List struct declarations.
<syntaxhighlight lang="rust">impl<T> List<T> {
pub fn new() -> Self {
List { head: None }
}
pub fn push(&mut self, elem: T) {
let new_node = Box::new(Node {
elem: elem,
next: self.head.take(),
});
self.head = Some(new_node);
}</syntaxhighlight>
=={{header|Scala}}==
In Scala (and functional programming) we create a new list instead of modifying existing one.
<syntaxhighlight lang="scala">
/*
Here is a basic list definition
sealed trait List[+A]
case class Cons[+A](head: A, tail: List[A]) extends List[A]
case object Nil extends List[Nothing]
*/
object List {
def add[A](as: List[A], a: A): List[A] = Cons(a, as)
}
</syntaxhighlight>
=={{header|Scheme}}==
Non-mutating:
<syntaxhighlight lang="scheme">(define (insert-after a b lst)
(if (null? lst)
lst ; This should be an error, but we will just return the list untouched
(let ((c (car lst))
(cs (cdr lst)))
(if (equal? a c)
(cons a (cons b cs))
(cons c (insert-after a b cs))))))</syntaxhighlight>
Mutating:
<syntaxhighlight lang="scheme">(define (insert-after! a b lst)
(let ((pos (member a lst)))
(if pos
(set-cdr! pos (cons b (cdr pos))))))</syntaxhighlight>
=={{header|Sidef}}==
<syntaxhighlight lang="ruby">func insert_after(a,b) {
b{:next} = a{:next};
a{:next} = b;
}
var B = Hash.new(
data => 3,
next => nil, # not a circular list
);
var A = Hash.new(
data => 1,
next => B,
);
var C = Hash.new(
data => 2,
);
insert_after(A, C);</syntaxhighlight>
=={{header|Stata}}==
See [[Singly-linked list/Element definition#Stata]].
=={{header|Tcl}}==
This task is extremely against the nature of the Tool Command Language. There are built-in lists, which are first-class citizens. The command <tt>linsert</tt> for inserting in such a list is already there, but it returns a new list instead of modifying an existing one. To emulate this, the <i>name</i> of the list (instead of its value) has to be handed over to the procedure and the procedure has to be given access to the variable using the <tt>upvar</tt> construction.
Additionally, the inserting point is usually given by the <i>index</i> of the element, which is to <i>follow</i> the new element, so the insertion always happens <i>before</i>. Since references and pointers don't exist in Tcl, using an existing element (which can only be a value) to determine the position of insertion, is not a good idea, because any value may appear several times in the list.
No error checking is included.
<syntaxhighlight lang="tcl">
proc insertIntoList {existingList predecessor newElement} {
upvar $existingList exList
set exList [linsert $exList [expr [lsearch -exact $exList $predecessor] + 1] $newElement]
}
set list {A B}
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}}==
<syntaxhighlight lang="x86asm">
; x86_64 Linux NASM
; Linked_List_Insert.asm
%ifndef INSERT
%define INSERT
%include "Linked_List_Definition.asm" ; see LL def task
%include "Heap_Alloc.asm" ; see memory allocation task
section .text
; rdi - link to insert after
; rsi - value that the new link will hold
Insert_After:
push rdi
push rsi
mov rdi, linkSize
call alloc
cmp rax, 0
je Memory_Allocation_Failure_Exception
pop rdi
mov dword [rax + value], edi
pop rdi
mov rsi, qword [rdi + next]
mov qword [rax + next], rsi
mov qword [rdi + next], rax
ret
%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:
<syntaxhighlight lang="zkl">L("a","b","c").insert(1,"foo") //-->L("a","foo","b","c")
a:=L("a","b","c"); a.insert(a.find("b"),"foo") //-->L("a","foo","b","c")</syntaxhighlight>
Create a new list:
<syntaxhighlight lang="zkl">a:=ROList("a","b","c");
n:=a.index("b"); a[0,n].append("foo").extend(a[n,*]) //-->ROList("a","foo","b","c")</syntaxhighlight>
=={{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">
</syntaxhighlight>
| |||