Singly-linked list/Element insertion: Difference between revisions

 

{{Template:See also lists}}

=={{header|360 Assembly}}==

The program uses one ASSIST macro (XPRNT) to keep the code as short as possible.

LISTSINA CSECT

USING LISTSINA,R13 base register

NEXT DS A

YREGS

{{out}}

<pre>

C

</pre>

 

=={{header|ACL2}}==

(cond ((endp xs)

nil)

(cons e (rest xs))))

(t (cons (first xs)

 

Example:

<pre>&gt;(insert-after 'A 'C '(A B))

(A C B)</pre>

 

=={{header|ActionScript}}==

Insertion method:

{

public class Node

}

}

Usage:

 

var A:Node = new Node(1);

var C:Node = new Node(3);

A.insert(B);

 

=={{header|Ada}}==

We must create a context clause making the predefined generic procedure Ada.Unchecked_Deallocation visible to this program.

-- Define the link type

procedure Singly_Linked is

Free(B);

Free(C);

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

 

STRINGLIST list := ("Big",

node := next OF node

OD;

Output:<pre>Big fjords vex VERY quick waltz nymph </pre>

 

=={{header|ALGOL W}}==

procedure insert( reference(ListI) value list

; integer value newValue

 

% insert a new value into the list %

 

=={{header|AutoHotkey}}==

a_next = b

b = 2

%old%_next := new

%new%_next := temp

 

=={{header|Axe}}==

{r₁+2}ʳ→{r₂+2}ʳ

r₂→{r₁+2}ʳ

r₁

 

=={{header|BBC BASIC}}==

{{works with|BBC BASIC for Windows}}

DIM a{} = node{}, b{} = node{}, c{} = node{}

here.pNext% = new{}

ENDPROC

 

=={{header|C}}==

Define the method:

 

newlink->next = anchor->next;

anchor->next = newlink;

 

Note that in a production implementation, one should check anchor and newlink to ensure they're valid values. (I.e., not NULL.)

 

Create our links.

a = malloc(sizeof(link));

b = malloc(sizeof(link));

a->data = 1;

b->data = 2;

 

Prepare our initial list

 

Insert element c after element a

 

Remember to free the memory once we're done.

free (b);

 

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

This uses the generic version of the link node. Of course, normally this would be just some implementation detail inside some list class, not to be used directly by client code.

 

{

new_node->next = list_node->next;

list_node->next = new_node;

 

Here's the example code using that method:

 

The following code creates the links. As numeric values I've just taken the corresponding character values.

 

Now insert c after a:

 

Finally destroy the list:

{

link<int>* tmp = a;

a = a->next;

delete tmp;

 

=={{header|Clojure}}==

 

(cond (empty? ls) ls

(= (first ls) old) (cons old (cons new (rest ls)))

 

And the test:

 

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

 

"Return a list like list, but with new-element appearing after the

first occurence of old-element. If old-element does not appear in

((or (null next) (funcall test old-element (car prev)))

(rplacd prev (cons new-element next))

 

A simpler implementation that traverses the list a bit more can also be written. This takes advantage of the fact that member returns the tail of the list beginning with the first occurrence of an item, and that ldiff copies as much of its list argument as necessary.

 

(let ((tail (rest (member old-element list :test test))))

(nconc (ldiff list tail)

 

Lastly, here is a recursive version. Case 3 could be optimized by only doing the rplacd operation when the recursive call returns a tail whose first cell is now different compared to that of the previous tail. (I.e. the recursive call has immediately hit case 1 or 2 which allocate new structure.)

 

"Insert item new into list, before existing, or at the end if existing

is not present. The default comparison test function is EQL. This

;; and make that list the new rest.

(t (rplacd list (insert-before (cdr list) new existing :test test))

 

=={{header|D}}==

T data;

typeof(this)* next;

 

// The GC will collect the memory.

 

=={{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 (* ... *).

 

 

Type

CurrentNode.Next := result ;

end;

 

=={{header|E}}==

 

new :LinkedList ? (new.next().null())) {

new.setNext(head.next())

println(x.value())

x := x.next()

 

=={{header|EchoLisp}}==

Lists are mutable, and we use the destructive - and dangerous - set-cdr! operator which modifies the 'rest' part of a list or sub-list.

(define (insert-after lst target item)

(when (null? lst) (error "cannot insert in" null))

(insert-after L 'x 'y)

L → (a c b y)

 

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

-module( singly_linked_list ).

 

loop_foreach( _Fun, nonext ) -> ok;

loop_foreach( Fun, Next ) -> Next ! {foreach, Fun}.

{{out}}

<pre>

 

=={{header|Factor}}==

[ swap next>> >>next drop ] [ >>next drop ] 2bi ;

 

[ C <linked-list> list-append ] keep

[ B <linked-list> list-append ] keep

Output:

<pre>

Extending Node class from [[Singly-Linked_List_(element)]]:

 

class Node

{

}

}

 

Output:

 

Using the linked list concept described in the [[Singly-Linked_List_(element)]] topic:

create A 0 , char A ,

create B 0 , char B ,

 

Now insert b after a and c after b, giving a->b->c

 

Here is an abbreviated version of the definition of 'chain' from the other article:

 

=={{header|Fortran}}==

In ISO Fortran 95 or later:

type (node), intent(inout) :: nodeBefore

real, intent(in) :: value

newNode%next => nodeBefore%next

nodeBefore%next => newNode

 

=={{header|Go}}==

 

import "fmt"

h.insert("C")

h.printList()

Output:

<pre>

=={{header|Groovy}}==

Solution (uses ListNode from [[Singly-Linked List (element)#Groovy]]):

private enum Flag { FRONT }

private ListNode head

}

String toString() { "${head}" }

 

Test:

list.insert('B')

list.insert('A')

 

list.insert('C', 'A')

 

Output:

=={{header|Haskell}}==

This kind of list manipulation is [[unidiomatic]] Haskell. But you can try the following:

| otherwise = c : insertAfter a b cs

 

==Icon and Unicon==

==={{header|Icon}}===

 

record Node (value, successor)

 

node.successor := newNode

end

 

==={{header|Unicon}}===

 

class Node (value, successor)

 

self.successor := successor

end

 

=={{header|J}}==

 

A=:0 NB. reference into list

B=:1 NB. reference into list

localNewNode=: (localOldLinkRef { localListValue), localNewValue

(localListName)=: (localNewLinkRef localOldLinkRef} localListValue), localNewNode

 

With these definitions:

=={{header|Java}}==

Extending [[Singly-Linked_List_(element)#Java]]

{

new_node.next = anchor_node.next;

anchor_node.next = new_node;

{{works with|Java|1.5+}}

Java allows the use of generics to allow the data type to be determined at compile time. This will only work on reference types, not primitive types like int or float (wrapper classes like Integer and Float are available).

=={{header|JavaScript}}==

Extending [[Singly-Linked_List_(element)#JavaScript]]

if (this._value == searchValue) {

nodeToInsert.next(this.next());

}

var list = createLinkedListFromArray(['A','B']);

 

=={{header|Kotlin}}==

 

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

insertAfter(a, c)

println("After insertion : $a")

 

{{out}}

 

=={{header|Logo}}==

localmake "tail member :after :list

if not empty? :tail [.setbf :tail fput :value bf :tail]

end

 

[3 5 2 1 8]

 

 

=={{header|Modula-3}}==

 

TYPE

InsertAppend(a, b);

InsertAppend(a, c)

 

=={{header|Nim}}==

next: Node[T]

data: T

 

a.insertAppend(b)

 

=={{header|OCaml}}==

This kind of list manipulation is unidiomatic OCaml. But you can try the following:

c :: cs when a = c -> a :: b :: cs

| c :: cs -> c :: insert_after a b cs

 

 

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

 

 

LinkedList method: initialize := next := data ;

: testLink LinkedList new($A, null) dup add($B) dup add($C) ;

 

 

{{out}}

=={{header|ooRexx}}==

See [[Singly-linked_list/Element_definition#ooRexx|Single-linked list/Element definition]] for full class definition.

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"

 

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

 

pCharNode = ^CharNode;

CharNode = record

newnode^.next := listnode^.next;

listnode^.next := newnode;

Usage example:

A, B: pCharNode;

begin

dispose(B);

end

 

=={{header|Perl}}==

If you don't really need the constant-time insertion property of singly linked lists, just use an array. You can traverse and splice it any way.

However, if you really need a linked list, or all you got is an algorithm in a foreign language, you can use references to accomplish the translation.

# first argument: node to insert after

# second argument: node to insert

data => 2,

);

Note that you don't have to name your new nodes. The following works just as well:

Note the curly braces instead of round parentheses.

 

It is straightforward to extend the function to take an arbitrary number of list nodes to insert:

my $node = $_[0];

my $next = $node->{next};

}

$node->{next} = $next;

With this, it's rather easy to build a list:

List handling is simplified if the variables themselves contain references. For example:

 

# create a new list ('A'. 'B', 'C') and store it in $list2

 

# append new nodes ('A2a', 'A2b') after the second element (which now is 'A2')

 

=={{header|Phix}}==

{{out}}

<pre>

=={{header|PicoLisp}}==

Destructive operation

(when (member Item Lst)

(con @ (cons New (cdr @))) )

Non-destructive operation

(if (index Item Lst)

(conc (cut @ 'Lst) (cons New Lst))

Output in both cases:

<pre>: (insertAfter 'A '(A B) 'C)

 

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

node.value = V;

H->p = Q; /* Break the list at H, and point it at the new node. */

 

=={{header|Pop11}}==

In Pop11 one normally uses built-in lists:

 

cons(x, back(anchor)) -> back(anchor);

enddefine;

insert_into_list(l1, "b");

;;; insert c

 

If one wants one can use user-defined list node (for convenience we repeat definition of list node):

 

define :class ListNode;

slot value = [];

insert_into_List(l2, "b");

;;; insert c

 

Note that user-defined case differs from built-in case only because of names.

=={{header|PureBasic}}==

Protected *newNode.MyData = AllocateMemory(SizeOf(MyData))

If *newNode

*SL_List = insertAfter(a) ;start the list

insertAfter(b, *SL_List) ;insert after head of list

 

=={{header|Python}}==

while lst is not None:

if lst[0] == at:

chain = ['A', ['B', None]]

chain_insert(chain, 'A', 'C')

Output:

 

=={{header|Racket}}==

 

#lang racket

 

(insert-after! l 2 2.5)

l ; -> (mcons 1 (mcons 2 (mcons 2.5 (mcons 3))))

 

=={{header|REXX}}==

'''output'''

<pre>

 

 

 

=={{header|Ruby}}==

def insert_after(search_value, new_value)

if search_value == value

 

list = ListNode.new(:a, ListNode.new(:b))

 

=={{header|Rust}}==

 

Extending [[Singly-Linked List (element)#Rust]]. Please see that page for the Linked List struct declarations.

pub fn new() -> Self {

List { head: None }

});

self.head = Some(new_node);

 

=={{header|Scala}}==

}

 

=={{header|Scheme}}==

Non-mutating:

(if (null? lst)

lst ; This should be an error, but we will just return the list untouched

(if (equal? a c)

(cons a (cons b cs))

 

Mutating:

(let ((pos (member a lst)))

(if pos

 

=={{header|Sidef}}==

b{:next} = a{:next};

a{:next} = b;

);

 

 

=={{header|Tcl}}==

 

 

=={{header|X86 Assembly}}==

; x86_64 Linux NASM

; Linked_List_Insert.asm

 

%endif

 

=={{header|zkl}}==

In place:

Create a new list: