Doubly-linked list/Element insertion: Difference between revisions

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

{{libheader|Action! Tool Kit}}

 

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

 

DEFINE NODE_SIZE="5"

 

ListNode POINTER listBegin,listEnd

TestAddAfter('C,listBegin)

TestClear()

{{out}}

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

 

Define the procedure:

begin

if Anchor /= Null and New_Link /= Null then

Anchor.Next := New_Link;

end if;

Create links and form the list.

 

A, B, C : Link_Access;

begin

Insert(Anchor => A, New_Link => B); -- The list is (A, B)

Insert(Anchor => A, New_Link => C); -- The list is (A, C, B)

 

Element insertion using the generic doubly linked list defined in the standard Ada containers library.

 

with Ada.Text_Io; use Ada.Text_Io;

with Ada.Strings.Unbounded; use Ada.Strings.Unbounded;

New_Item => To_Unbounded_String("C"));

The_List.Iterate(Print'access);

 

=={{header|ALGOL 68}}==

{{works with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-1.18.0/algol68g-1.18.0-9h.tiny.el5.centos.fc11.i386.rpm/download 1.18.0-9h.tiny].}}

{{wont work with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d] - due to extensive use of '''format'''[ted] ''transput''.}}

 

# SEMA do link OF splice = LEVEL 1 #

OD;

print(new line)

Output:

<pre>

 

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

record DListIElement ( reference(DListIElement) prev

; integer iValue

end if_e_ne_null ;

newElement

 

=={{header|AutoHotkey}}==

 

=={{header|Axe}}==

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

r₁→{r₂+4}ʳ

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

newlink->next = anchor->next;

newlink->prev = anchor;

(newlink->next)->prev = newlink;

anchor->next = newlink;

 

Production code should also include checks that the passed links are valid (e.g. not null pointers). There should also be code to handle special cases, such as when *anchor is the end of the existing list (i.e. anchor->next is a null pointer).

 

Create links, and form the list:

a.next = &b;

a.prev = null;

b.prev = &a;

b.data = 3;

 

This list is now {a,b}, and c is separate.

 

Now call the function:

 

This function call changes the list from {a,b} to {a,b,c}.

=={{header|C sharp|C#}}==

The function handles creation of nodes in addition to inserting them.

{

if (prev.next != null)

else

prev.next = new Link() { item = i, prev = prev };

Example use:

{

//Create A(5)->B(7)

//Insert C(15) between A and B

InsertAfter(A, 15);

 

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

C++ already has own linked list structure. If we were to roll our own linked list, we could implement function inserting new value after specific node like that:

void insert_after(Node<T>* N, T&& data)

{

N->next->prev = node;

N->next = node;

 

=={{header|Clojure}}==

This sort of mutable structure is not idiomatic in Clojure. [[../Definition#Clojure]] or a finger tree implementation would be better.

 

 

(defn new-node [prev next data]

t (new-node nil nil :B)]

(insert-between h t (new-node nil nil :C))

 

=={{header|Common Lisp}}==

 

=={{header|D}}==

 

struct Node(T) {

insertAfter(list, "C");

list.show;

{{out}}

<pre>A

{{libheader| System.SysUtils}}

{{libheader|Boost.LinkedList}}[https://github.com/MaiconSoft/DelphiBoostLib]

program Element_insertion;

 

List.Free;

Readln;

{{out}}

<pre>[ 5, 15, 7]</pre>

 

=={{header|E}}==

def newNode := makeElement(value, after, after.getNext())

after.getNext().setPrev(newNode)

after.setNext(newNode)

 

 

 

=={{header|Fortran}}==

In ISO Fortran 95 or later:

public :: node, insertAfter, getNext

current => next

end do

Output:

2.

4.

262144.

524288.

 

=={{header|Go}}==

 

import "fmt"

dll.insertAfter(a, &dlNode{string: "C"})

fmt.Println(dll)

Output:

<pre>

Using the algebraic data type and update functions from [[Doubly-Linked_List_(element)#Haskell]].

 

insert _ Leaf = Leaf

insert nv l@(Node pl v r) = (\(Node c _ _) -> c) new

Leaf -> Leaf

Node _ v r -> Node new v r

 

==Icon and {{header|Unicon}}==

Uses Unicon classes.

 

class DoubleLink (value, prev_link, next_link)

 

self.next_link := next_link

end

 

=={{header|J}}==

The Java implementation does not a method to add an element based on another element. However, we can use methods from the base class to create a <code>AddAfter</code> method. A class with this method inherting all methods from the <code>LinkedList<T></code> class is shown below.

 

import java.util.LinkedList;

 

}

 

{{out}}

=={{header|JavaScript}}==

See [[Doubly-Linked_List_(element)#JavaScript]]

if (this._value == searchValue) {

var after = this.next();

 

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

 

=={{header|Julia}}==

value::T

pred::Union{DLNode{T}, Nothing}

insertpost(node1, node3)

printfromroot(node1)

1

1 -> 2

 

=={{header|Kotlin}}==

 

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

insert(after = a, new = c)

println("After insertion : $a")

 

{{out}}

 

=={{header|Mathematica}}/{{header|Wolfram Language}}==

ds["Append", "A"];

ds["Append", "B"];

ds["Append", "C"];

ds["SwapPart", 2, 3];

{{out}}

<pre>{"A", "C", "B"}</pre>

 

=={{header|Nim}}==

n.prev = r

n.next = r.next

n.next.prev = n

r.next = n

 

=={{header|Oberon-2}}==

PROCEDURE (dll: DLList) InsertAfter*(p: Node; o: Box.Object);

VAR

INC(dll.size)

END InsertAfter;

 

=={{header|Objeck}}==

node := ListNode->New(value);

if(@head = Nil) {

@tail := node;

};

 

=={{header|OCaml}}==

===with dlink===

let _insert anchor newlink =

newlink.next <- anchor.next;

match dl with

| (Some anchor) -> _insert anchor {data=v; prev=None; next=None}

 

testing in the top level:

 

type t = A | B | C

 

insert dl C;

list_of_dlink dl ;;

 

===with nav_list===

 

 

testing in the top level:

type t = A | B | C

 

 

# insert nl C ;;

 

=={{header|Oforth}}==

Complete definition is here : [[../Definition#Oforth]]

 

| dl |

DList new ->dl

dl insertBack("B")

dl head insertAfter(DNode new("C", null , null))

 

{{out}}

=={{header|Oz}}==

Warning: Do not use in real programs.

fun {CreateNewNode Value}

node(prev:{NewCell nil}

in

{InsertAfter A B}

 

=={{header|Pascal}}==

 

begin

a^.next := c;

c^.next := b;

c^.prev := a;

 

Actually, a more likely real world scenario is 'insert after A'. So...

 

begin

if a^.next <> nil then a^.next^.prev := c; (* 'a^.next^' is another way of saying 'b', if b exists *)

a^.next := c;

c^.prev := a;

 

=={{header|Perl}}==

data => 'something',

prev => undef,

# insert element C into a list {A,B}, between elements A and B.

my $node_c = { %node_model };

 

=={{header|Phix}}==

See also [[Doubly-linked_list/Traversal#Phix|Doubly-linked_list/Traversal]].

<span style="color: #008080;">enum</span> <span style="color: #000000;">NEXT</span><span style="color: #0000FF;">,</span><span style="color: #000000;">PREV</span><span style="color: #0000FF;">,</span><span style="color: #000000;">DATA</span>

<span style="color: #008080;">constant</span> <span style="color: #000000;">empty_dll</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: #000000;">1</span><span style="color: #0000FF;">}}</span>

<span style="color: #0000FF;">?</span><span style="color: #000000;">dll</span>

{{out}}

<pre>

[[Doubly-linked list/Definition#PicoLisp]] and

[[Doubly-linked list/Element definition#PicoLisp]].

(de 2insert (X Pos DLst)

(let (Lst (nth (car DLst) (dec (* 2 Pos))) New (cons X (cadr Lst) Lst))

 

(setq *DL (2list 'A 'B)) # Build a two-element doubly-linked list

For output of the example data, see [[Doubly-linked list/Traversal#PicoLisp]].

 

=={{header|PL/I}}==

define structure

1 Node,

Q => back_pointer = P;

/* Points the next node to the new one. */

 

=={{header|Pop11}}==

lvars tmp;

if list == [] then

insert_double(A, B) -> _;

;;; insert C between A and b

 

=={{header|PureBasic}}==

*prev.node

*next.node

Input()

CloseConsole()

Sample output:

<pre>A C B</pre>

=={{header|Python}}==

 

new.next = anchor.next

new.prev = anchor

anchor.next.prev = new

 

=={{header|Racket}}==

 

Using the generic definitions from [[Doubly-linked_list/Definition#Raku]]:

has DLElem[T] $.prev is rw;

has DLElem[T] $.next is rw;

my $b = $sdll.first.post-insert('A').post-insert('B');

$b.pre-insert('C');

{{out}}

<pre>A C B</pre>

REXX doesn't have linked lists, as there are no pointers (or handles).

<br>However, linked lists can be simulated with lists in REXX.

/*┌────────────────────────────────────────────────────────────────────┐

┌─┘ Functions of the List Manager └─┐

$.@=_

call @adjust

'''output'''

<pre style="height:50ex;overflow:scroll">

 

=={{header|Ruby}}==

def insert_after(search_value, new_value)

if search_value == value

 

head = DListNode.from_array([:a, :b])

 

=={{header|Rust}}==

=== Simply using the standard library ===

fn main() {

let mut list = LinkedList::new();

list.push_front(8);

 

=== The behind-the-scenes implementation ===

This expands upon the implementation defined in [[Doubly-linked list/Element definition#The_behind-the-scenes_implementation]] and consists of the relevant lines from the LinkedList implementation in the Rust standard library.

 

fn new(v: T) -> Node<T> {

Node {value: v, next: None, prev: Rawlink::none()}

self.push_front_node(Box::new(Node::new(elt)));

}

 

=={{header|Swift}}==

 

 

class Node<T> {

 

// [1, 3, 2]

 

=={{header|Tcl}}==

<br>

{{works with|Tcl|8.6}}

method insertBefore {elem} {

$elem next [self]

set next $elem

}

Demonstration:

set A [List new 1 $B]

set C [List new 2]

$A insertAfter $C

 

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

 

Dim node As New Node(Of T)(value)

a.Next = node

b.Previous = node

node.Next = b

 

=={{header|Wren}}==

{{libheader|Wren-llist}}

 

var dll = DLinkedList.new(["A", "B"])

dll.insertAfter("A", "C")

 

{{out}}

[A <-> C <-> B]

</pre>

 

=={{header|zkl}}==

fcn init(_value,_prev=Void,_next=Void)

{ var value=_value, prev=_prev, next=_next; }

b

}

a.append("b").append("c");

{{out}}

<pre>