Singly-linked list/Element insertion
You are encouraged to solve this task according to the task description, using any language you may know.
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.
- See also
- Array
- Associative array: Creation, Iteration
- Collections
- Compound data type
- Doubly-linked list: Definition, Element definition, Element insertion, List Traversal, Element Removal
- Linked list
- Queue: Definition, Usage
- Set
- Singly-linked list: Element definition, Element insertion, List Traversal, Element Removal
- Stack
360 Assembly
The program uses one ASSIST macro (XPRNT) to keep the code as short as possible. <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</lang>
- Output:
A B C
ACL2
<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))))))</lang>
Example:
>(insert-after 'A 'C '(A B)) (A C B)
ActionScript
Insertion method: <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; } } }</lang> Usage: <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);</lang>
Ada
We must create a context clause making the predefined generic procedure Ada.Unchecked_Deallocation visible to this program. <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;</lang>
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: <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))</lang>
Output:
Big fjords vex VERY quick waltz nymph
ALGOL W
<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 );</lang>
AutoHotkey
<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
}</lang>
Axe
<lang axe>Lbl INSERT {r₁+2}ʳ→{r₂+2}ʳ r₂→{r₁+2}ʳ r₁ Return</lang>
BBC BASIC
<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
</lang>
C
Define the method:
<lang c>void insert_append (link *anchor, link *newlink) {
newlink->next = anchor->next; anchor->next = newlink;
}</lang>
Note that in a production implementation, one should check anchor and newlink to ensure they're valid values. (I.e., not NULL.)
And now on to the code.
Create our links. <lang c>link *a, *b, *c; a = malloc(sizeof(link)); b = malloc(sizeof(link)); c = malloc(sizeof(link)); a->data = 1; b->data = 2; c->data = 3;</lang>
Prepare our initial list <lang c> insert_append (a, b);</lang>
Insert element c after element a <lang c> insert_append (a, c);</lang>
Remember to free the memory once we're done. <lang c> free (a);
free (b); free (c);</lang>
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.
<lang cpp>template<typename T> void insert_after(link<T>* list_node, link<T>* new_node) {
new_node->next = list_node->next; list_node->next = new_node;
};</lang>
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. <lang cpp>link<int>* a = new link<int>('A', new link<int>('B')); link<int>* c = new link<int>('C');</lang>
Now insert c after a: <lang cpp> insert_after(a, c);</lang>
Finally destroy the list: <lang cpp>while (a) {
link<int>* tmp = a; a = a->next; delete tmp;
}</lang>
C#
Creates nodes and inserts them from the data passed. <lang csharp>static void InsertAfter(Link prev, int i) {
prev.next = new Link() { item = i, next = prev.next };
}</lang> <lang csharp>static void Main() {
//Create A(5)->B(7)
var A = new Link() { item = 5 };
InsertAfter(A, 7);
//Insert C between A and B
InsertAfter(A, 15);
}</lang>
Clojure
<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)))))</lang>
And the test: <lang lisp>user=> (insert-after 'c 'a '(a b)) (a c b)</lang>
Common Lisp
For many list manipulations in Common Lisp, there are both destructive and non-destructive versions. insert-after is non-destructive, copying the structure of list up to and including the occurrence of the old-element, and sharing the list structure afterward. ninsert-after may modify the structure of the input list.
<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))))</lang>
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.
<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))))</lang>
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.)
<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)))</lang>
D
<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.
}</lang>
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 (* ... *).
<lang delphi>// Using the same type defs from the one way list example.
Type
// The pointer to the list structure pOneWayList = ^OneWayList;
// The list structure
OneWayList = record
pData : pointer ;
Next : pOneWayList ;
end;
// I will illustrate a simple function that will return a pointer to the // 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 // somewhat counter intuitive, but it is the simplest way to accomplish this.
Function InsertNode(VAR CurrentNode:pOneWayList): pOneWayList begin
// 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/except block. In any OS that is multi-threaded and has many apps // 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 // program may have grabbed the memory you were trying to get.
Try
// Try to allocate enough memory for a variable the size of OneWayList
GetMem(Result,SizeOf(OneWayList));
Except
On EOutOfMemoryError do
begin
Result := NIL
exit;
end;
end;
// Initialize the variable. Result.Next := NIL ; Reuslt.pdata := NIL ;
// Ok now we will insert to the right.
// Is the Next pointer of CurrentNode Nil? If it is we are just tacking // on to the end of the list.
if CurrentNode.Next = NIL then
CurrentNode.Next := Result
else
// We are inserting into the middle of this list
Begin
Result.Next := CurrentNode.Next ;
CurrentNode.Next := result ;
end;
end;</lang>
E
<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()
}</lang>
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. <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)
</lang>
Elena
<lang elena>singleton linkHelper {
insertAfter(Link prev, IntNumber i)
[
prev Next := Link new(i, prev Next).
]
}</lang>
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: <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}. </lang>
- Output:
4> singly_linked_list:task(). a c b
Factor
<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 .</lang> Output:
T{ linked-list
{ data A }
{ next
T{ linked-list
{ data B }
{ next T{ linked-list { data C } } }
}
}
}
Fantom
Extending Node class from Singly-Linked_List_(element):
<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) }
} </lang>
Output:
1 2 3
Forth
Using the linked list concept described in the Singly-Linked_List_(element) topic: <lang forth>\ Create the list and some list elements create A 0 , char A , create B 0 , char B , create C 0 , char C ,</lang>
Now insert b after a and c after b, giving a->b->c <lang forth>B A chain C B chain</lang>
Here is an abbreviated version of the definition of 'chain' from the other article: <lang forth> : chain ( a b -- ) 2dup @ swap ! ! ;</lang>
Fortran
In ISO Fortran 95 or later: <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</lang>
Go
<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()
}</lang> Output:
(A B) (A C B)
Groovy
Solution (uses ListNode from Singly-Linked List (element)#Groovy): <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}" }
}</lang>
Test: <lang groovy>def list = new NodeList() list.insert('B') list.insert('A') println list
list.insert('C', 'A') println list</lang>
Output:
A -> B -> null A -> C -> B -> null
Haskell
This kind of list manipulation is unidiomatic Haskell. But you can try the following: <lang haskell>insertAfter a b (c:cs) | a==c = a : b : cs
| otherwise = c : insertAfter a b cs
insertAfter _ _ [] = error "Can't insert"</lang>
Icon and Unicon
The Icon solution works for both Icon and Unicon, but Unicon permits a class-based solution.
Icon
<lang Icon> record Node (value, successor)
procedure insert_node (node, newNode)
newNode.successor := node.successor node.successor := newNode
end </lang>
Unicon
<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 </lang>
J
<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
)</lang>
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.
Java
Extending Singly-Linked_List_(element)#Java <lang Java>void insertNode(Node<T> anchor_node, Node<T> new_node) {
new_node.next = anchor_node.next; anchor_node.next = new_node;
}</lang>
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).
JavaScript
Extending Singly-Linked_List_(element)#JavaScript <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));</lang>
Julia
See the LinkedList implemented at Singly-linked_list/Element_definition#Julia.
<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</lang>
Kotlin
<lang scala>// version 1.1.2
class Node<T: Number>(var data: T, var next: Node<T>? = null) {
override fun toString(): String {
val sb = StringBuilder(this.data.toString())
var node = this.next
while (node != null) {
sb.append(" -> ", node.data.toString())
node = node.next
}
return sb.toString()
}
}
fun <T: Number> insertAfter(prev: Node<T>, new: Node<T>) {
new.next = prev.next prev.next = new
}
fun 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")
}</lang>
- Output:
Before insertion : 1 -> 3 After insertion : 1 -> 2 -> 3
Logo
<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</lang>
[3 5 2 1 8]
Mathematica
<lang Mathematica>Append[{a, b}, c] ->{a, b, c}</lang>
Modula-3
<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.</lang>
Nim
<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)</lang>
OCaml
This kind of list manipulation is unidiomatic OCaml. But you can try the following: <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</lang>
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).
<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</lang>
- Output:
[A, C, B]
ooRexx
See Single-linked list/Element definition for full class definition. <lang ooRexx> list = .linkedlist~new index = list~insert("abc") -- insert a first item, keeping the index list~insert("def") -- adds to the end list~insert("123", .nil) -- adds to the begining list~insert("456", index) -- inserts between "abc" and "def" list~remove(index) -- removes "abc" </lang>
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.
<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;</lang> Usage example: <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.</lang>
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. <lang perl>my @l = ($A, $B); push @l, $C, splice @l, 1;</lang> 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. <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;</lang> Note that you don't have to name your new nodes. The following works just as well: <lang perl> insert_after \%A, { data => 2 };</lang> 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: <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;
}</lang> With this, it's rather easy to build a list: <lang perl>my %list = ( data => 'A' ); insert_after \%list, { data => 'B' }, { data => 'C' };</lang> List handling is simplified if the variables themselves contain references. For example: <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' };</lang>
Perl 6
<lang perl6>my $letters = 'A' => 'C' => Mu;
sub insert-after($list, $after, $new) {
loop (my $l = $list; $l; $l = $l.value) {
if $l.key eqv $after {
$l.value = $new => $l.value;
return;
}
}
die "Element $after not found";
}
$letters.&insert-after('A', 'B');</lang>
Phix
See also Singly-linked_list/Traversal. <lang Phix>enum NEXT,DATA constant empty_sll = Template:1 sequence sll = empty_sll
procedure insert_after(object data, integer pos=length(sll))
sll = append(sll,{sll[pos][NEXT],data})
sll[pos][NEXT] = length(sll)
end procedure
insert_after("ONE") insert_after("TWO") insert_after("THREE")
?sll</lang>
- Output:
{{2},{3,"ONE"},{4,"TWO"},{1,"THREE"}}
PicoLisp
Destructive operation <lang PicoLisp>(de insertAfter (Item Lst New)
(when (member Item Lst)
(con @ (cons New (cdr @))) )
Lst )</lang>
Non-destructive operation <lang PicoLisp>(de insertAfter (Item Lst New)
(if (index Item Lst)
(conc (cut @ 'Lst) (cons New Lst))
Lst ) )</lang>
Output in both cases:
: (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)
PL/I
<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. */ </lang>
Pop11
In Pop11 one normally uses built-in lists:
<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");</lang>
If one wants one can use user-defined list node (for convenience we repeat definition of list node):
<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");</lang>
Note that user-defined case differs from built-in case only because of names.
PureBasic
<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</lang>
Python
<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</lang> Output: <lang python>['A', ['C', ['B', None]]]</lang>
Racket
<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)))) </lang>
REXX
<lang rexx>/*REXX program demonstrates how to create and show a single-linked list.*/ @.=0 /*define a null linked list. */ call set@ 3 /*linked list: 12 Proth primes. */ call set@ 5 call set@ 13 call set@ 17 call set@ 41 call set@ 97 call set@ 113 call set@ 193 call set@ 241 call set@ 257 call set@ 353 call set@ 449 call list@
after = 97 /* ◄──── REXX code to do insert. */
newVal=100 /* ◄──── " " " " " */
#=@..after /* ◄──── " " " " " */
call ins@ #,newVal /* ◄──── " " " " " */
say say 'a new value of' newval "has been inserted after element value:" after call list@ exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────INS@ subroutine─────────────────────*/ ins@: procedure expose @.; parse arg #,y @._last=@._last+1 /*bump number of list elements. */ _=@._last @._._value=y /*define new value list element. */ @._._next=@.#._next @.#._next=_ @..y=_ /*set a locator pointer to self. */ @.max_width=max(@.max_width,length(y)) /*set maximum width of any value.*/ return /*return to invoker of this sub. */ /*──────────────────────────────────LIST@ subroutine────────────────────*/ list@: say; w=max(7, @.max_width ) /*use the max width of nums or 7.*/ say center('item',6) 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._value,w) right(@.p._next,6)
p=@.p._next
end /*j*/
return /*──────────────────────────────────SET@ subroutine─────────────────────*/ set@: procedure expose @.; parse arg y /*get element to be added to list*/ _=@._last /*set the previous last element. */ n=_+1 /*bump last ptr in linked list. */ @._._next=n /*set the next pointer value. */ @._last=n /*define next item in linked list*/ @.n._value=y /*set item to the value specified*/ @.n._next=0 /*set the next pointer value. */ @..y=n /*set a locator pointer to self. */ @.max_width=max(@.max_width,length(y)) /*set maximum width of any value.*/ return /*return to invoker of this sub. */</lang> output
item value next
────── ─────── ──────
1 3 2
2 5 3
3 13 4
4 17 5
5 41 6
6 97 7
7 113 8
8 193 9
9 241 10
10 257 11
11 353 12
12 449 0
a new value of 100 has been inserted after element value: 97
item value next
────── ─────── ──────
1 3 2
2 5 3
3 13 4
4 17 5
5 41 6
6 97 13
7 100 7
8 113 8
9 193 9
10 241 10
11 257 11
12 353 12
13 449 0
Ruby
<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)</lang>
Rust
Extending Singly-Linked List (element)#Rust. Please see that page for the Linked List struct declarations. <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);
}</lang>
Scala
In Scala (and functional programming) we create a new list instead of modifying existing one. <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)
} </lang>
Scheme
Non-mutating: <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))))))</lang>
Mutating: <lang scheme>(define (insert-after! a b lst)
(let ((pos (member a lst)))
(if pos
(set-cdr! pos (cons b (cdr pos))))))</lang>
Sidef
<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);</lang>
Stata
See Singly-linked list/Element definition#Stata.
X86 Assembly
<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 </lang>
zkl
In place: <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")</lang> Create a new list: <lang zkl>a:=ROList("a","b","c"); n:=a.index("b"); a[0,n].append("foo").extend(a[n,*]) //-->ROList("a","foo","b","c")</lang>
- Programming Tasks
- Data Structures
- 360 Assembly
- ACL2
- ActionScript
- Ada
- ALGOL 68
- ALGOL W
- AutoHotkey
- Axe
- BBC BASIC
- C
- C++
- C sharp
- Clojure
- Common Lisp
- D
- Delphi
- E
- EchoLisp
- Elena
- Erlang
- Factor
- Fantom
- Forth
- Fortran
- Go
- Groovy
- Haskell
- Icon
- Unicon
- J
- Java
- JavaScript
- Julia
- Kotlin
- Logo
- Mathematica
- Modula-3
- Nim
- OCaml
- Oforth
- OoRexx
- Pascal
- Perl
- Perl 6
- Perl 6 examples needing attention
- Examples needing attention
- Phix
- PicoLisp
- PL/I
- Pop11
- PureBasic
- Python
- Racket
- REXX
- Ruby
- Rust
- Scala
- Scheme
- Sidef
- Stata
- X86 Assembly
- Zkl