I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

Doubly-linked list/Element insertion

From Rosetta Code
Task
Doubly-linked list/Element insertion
You are encouraged to solve this task according to the task description, using any language you may know.
Use the link structure defined in Doubly-Linked List (element) to define a procedure for inserting a link into a doubly-linked list. Call this procedure to insert element C into a list {A,B}, between elements A and B.

This is much like inserting into a Singly-Linked List, but with added assignments so that the backwards-pointing links remain correct.

See also

Action![edit]

The user must type in the monitor the following command after compilation and before running the program!
SET EndProg=*
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="5"
TYPE ListNode=[CHAR data PTR prv,nxt]
 
ListNode POINTER listBegin,listEnd
 
PROC AddBegin(CHAR v)
ListNode POINTER n
 
n=Alloc(NODE_SIZE)
n.data=v
n.prv=0
n.nxt=listBegin
IF listBegin THEN
listBegin.prv=n
ELSE
listEnd=n
FI
listBegin=n
RETURN
 
PROC AddEnd(CHAR v)
ListNode POINTER n
 
n=Alloc(NODE_SIZE)
n.data=v
n.prv=listEnd
n.nxt=0
IF listEnd THEN
listEnd.nxt=n
ELSE
listBegin=n
FI
listEnd=n
RETURN
 
PROC AddAfter(CHAR v ListNode POINTER node)
ListNode POINTER n,tmp
 
IF node=0 THEN
PrintE("The node is null!") Break()
ELSEIF node=listEnd THEN
AddEnd(v)
ELSE
n=Alloc(NODE_SIZE)
n.data=v
n.nxt=node.nxt
n.prv=node
tmp=node.nxt
tmp.prv=n
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
listEnd=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
listEnd=0
 
PrintList()
TestAddBegin('A)
TestAddAfter('B,listBegin)
TestAddAfter('C,listBegin)
TestClear()
RETURN
Output:

Screenshot from Atari 8-bit computer

()
Add 'A' at the begin:
(A)
Add 'B' after 'A':
(A, B)
Add 'C' after 'A':
(A, C, B)
Clear the list:
()

Ada[edit]

Define the procedure:

procedure Insert (Anchor : Link_Access; New_Link : Link_Access) is
begin
if Anchor /= Null and New_Link /= Null then
New_Link.Next := Anchor.Next;
New_Link.Prev := Anchor;
if New_Link.Next /= Null then
New_Link.Next.Prev := New_Link;
end if;
Anchor.Next := New_Link;
end if;
end Insert;

Create links and form the list.

procedure Make_List is 
A, B, C : Link_Access;
begin
A := new Link;
B := new Link;
C := new Link;
A.Data := 1;
B.Data := 2;
C.Data := 2;
Insert(Anchor => A, New_Link => B); -- The list is (A, B)
Insert(Anchor => A, New_Link => C); -- The list is (A, C, B)
end Make_List;

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

with Ada.Containers.Doubly_Linked_Lists;
with Ada.Text_Io; use Ada.Text_Io;
with Ada.Strings.Unbounded; use Ada.Strings.Unbounded;
 
procedure List_Insertion is
package String_List is new Ada.Containers.Doubly_Linked_Lists(Unbounded_String);
use String_List;
procedure Print(Position : Cursor) is
begin
Put_Line(To_String(Element(Position)));
end Print;
The_List : List;
begin
The_List.Append(To_Unbounded_String("A"));
The_List.Append(To_Unbounded_String("B"));
The_List.Insert(Before => The_List.Find(To_Unbounded_String("B")),
New_Item => To_Unbounded_String("C"));
The_List.Iterate(Print'access);
end List_Insertion;

ALGOL 68[edit]

Works with: ALGOL 68 version Revision 1 - no extensions to language used.
Works with: ALGOL 68G version Any - tested with release 1.18.0-9h.tiny.
#!/usr/local/bin/a68g --script #
 
# SEMA do link OF splice = LEVEL 1 #
MODE LINK = STRUCT (
REF LINK prev,
REF LINK next,
DATA value
);
 
# BEGIN rosettacode task specimen code:
can handle insert both before the first, and after the last link #

 
PROC insert after = (REF LINK #self,# prev, DATA new data)LINK: (
# DOWN do link OF splice OF self; to make thread safe #
REF LINK next = next OF prev;
HEAP LINK new link := LINK(prev, next, new data);
next OF prev := prev OF next := new link;
# UP do link OF splice OF self; #
new link
);
 
PROC insert before = (REF LINK #self,# next, DATA new data)LINK:
insert after(#self,# prev OF next, new data);
 
# END rosettacode task specimen code #
 
# Test case: #
MODE DATA = STRUCT(INT year elected, STRING name);
FORMAT data fmt = $dddd": "g"; "$;
 
test:(
 
# manually initialise the back splices #
LINK presidential splice;
presidential splice := (presidential splice, presidential splice, SKIP);
 
# manually build the chain #
LINK previous, incumbent, elect;
previous := (presidential splice, incumbent, DATA(1993, "Clinton"));
incumbent:= (previous, elect, DATA(2001, "Bush" ));
elect := (incumbent, presidential splice, DATA(2008, "Obama" ));
 
insert after(incumbent, LOC DATA := DATA(2004, "Cheney"));
 
REF LINK node := previous;
WHILE REF LINK(node) ISNT presidential splice DO
printf((data fmt, value OF node));
node := next OF node
OD;
print(new line)
)

Output:

1993: Clinton; 2001: Bush; 2004: Cheney; 2008: Obama; 

ALGOL W[edit]

    % record type to hold an element of a doubly linked list of integers      %
record DListIElement ( reference(DListIElement) prev
 ; integer iValue
 ; reference(DListIElement) next
);
 % additional record types would be required for other element types  %
 % inserts a new element into the list, before e  %
reference(DListIElement) procedure insertIntoDListIBefore( reference(DListIElement) value e
 ; integer value v
);
begin
reference(DListIElement) newElement;
newElement := DListIElement( null, v, e );
if e not = null then begin
 % the element we are inserting before is not null  %
reference(DListIElement) ePrev;
ePrev  := prev(e);
prev(newElement) := ePrev;
prev(e)  := newElement;
if ePrev not = null then next(ePrev) := newElement
end if_e_ne_null ;
newElement
end insertIntoDListiAfter ;

AutoHotkey[edit]

see Doubly-linked list/AutoHotkey

Axe[edit]

Lbl INSERT
{r₁+2}ʳ→{r₂+2}ʳ
r₁→{r₂+4}ʳ
r₂→{{r₂+2}ʳ+4}ʳ
r₂→{r₁+2}ʳ
r₁
Return

BBC BASIC[edit]

      DIM node{pPrev%, pNext%, iData%}
DIM a{} = node{}, b{} = node{}, c{} = node{}
 
a.pNext% = b{}
a.iData% = 123
b.pPrev% = a{}
b.iData% = 456
c.iData% = 789
 
PROCinsert(a{}, c{})
END
 
DEF PROCinsert(here{}, new{})
LOCAL temp{} : DIM temp{} = node{}
new.pNext% = here.pNext%
new.pPrev% = here{}
 !(^temp{}+4) = new.pNext%
temp.pPrev% = new{}
here.pNext% = new{}
ENDPROC
 

C[edit]

Define the function:

void insert(link* anchor, link* newlink) {
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).


To call the function:

Create links, and form the list:

link a, b, c;
a.next = &b;
a.prev = null;
a.data = 1;
b.next = null;
b.prev = &a;
b.data = 3;
c.data = 2;

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

Now call the function:

insert(&a, &c);

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

C#[edit]

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

static void InsertAfter(Link prev, int i)
{
if (prev.next != null)
{
prev.next.prev = new Link() { item = i, prev = prev, next = prev.next };
prev.next = prev.next.prev;
}
else
prev.next = new Link() { item = i, prev = prev };
}

Example use:

static void Main()
{
//Create A(5)->B(7)
var A = new Link() { item = 5 };
InsertAfter(A, 7);
//Insert C(15) between A and B
InsertAfter(A, 15);
}

C++[edit]

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:

template <typename T>
void insert_after(Node<T>* N, T&& data)
{
auto node = new Node<T>{N, N->next, std::forward(data)};
if(N->next != nullptr)
N->next->prev = node;
N->next = node;
}

Clojure[edit]

This sort of mutable structure is not idiomatic in Clojure. Doubly-linked list/Definition#Clojure or a finger tree implementation would be better.

(defrecord Node [prev next data])
 
(defn new-node [prev next data]
(Node. (ref prev) (ref next) data))
 
(defn new-list [head tail]
(List. (ref head) (ref tail)))
 
(defn insert-between [node1 node2 new-node]
(dosync
(ref-set (:next node1) new-node)
(ref-set (:prev new-node) node1)
(ref-set (:next new-node) node2)
(ref-set (:prev node2) new-node)))
 
(set! *print-level* 1)
 
;; warning: depending on the value of *print-level*
;; this could cause a stack overflow when printing
 
(let [h (new-node nil nil :A)
t (new-node nil nil :B)]
(insert-between h t (new-node nil nil :C))
(new-list h t))

Common Lisp[edit]

Code is on the Doubly-Linked List page, in function insert-between.

D[edit]

import std.stdio;
 
struct Node(T) {
T data;
typeof(this)* prev, next;
}
 
/// If prev is null, prev gets to point to a new node.
void insertAfter(T)(ref Node!T* prev, T item) pure nothrow {
if (prev) {
auto newNode = new Node!T(item, prev, prev.next);
prev.next = newNode;
if (newNode.next)
newNode.next.prev = newNode;
} else
prev = new Node!T(item);
}
 
void show(T)(Node!T* list) {
while (list) {
write(list.data, " ");
list = list.next;
}
writeln;
}
 
void main() {
Node!(string)* list;
insertAfter(list, "A");
list.show;
insertAfter(list, "B");
list.show;
insertAfter(list, "C");
list.show;
}
Output:
A 
A B 
A C B 

Delphi[edit]

[1]
 
program Element_insertion;
 
{$APPTYPE CONSOLE}
 
uses
System.SysUtils,Boost.LinkedList;
 
var
List:TLinkedList<Integer>;
Node:TLinkedListNode<Integer>;
begin
List := TLinkedList<Integer>.Create;
Node:= List.Add(5);
List.AddAfter(Node,7);
List.AddAfter(Node,15);
Writeln(List.ToString);
List.Free;
Readln;
end.
Output:
[ 5, 15, 7]

See #Pascal for vanilla version.

E[edit]

def insert(after, value) {
def newNode := makeElement(value, after, after.getNext())
after.getNext().setPrev(newNode)
after.setNext(newNode)
}
insert(A_node, C)


Erlang[edit]

Using the code in Doubly-linked_list/Definition.

Output:
2> doubly_linked_list:task().
foreach_next a
foreach_next c
foreach_next b
foreach_previous b
foreach_previous c
foreach_previous a

Fortran[edit]

In ISO Fortran 95 or later:

module dlList
public :: node, insertAfter, getNext
 
type node
real :: data
type( node ), pointer :: next => null()
type( node ), pointer :: previous => null()
end type node
 
contains
subroutine insertAfter(nodeBefore, value)
type( node ), intent(inout), target :: nodeBefore
type( node ), pointer :: newNode
real, intent(in) :: value
 
allocate( newNode )
newNode%data = value
newNode%next => nodeBefore%next
newNode%previous => nodeBefore
 
if (associated( newNode%next )) then
newNode%next%previous => newNode
end if
newNode%previous%next => newNode
end subroutine insertAfter
 
subroutine delete(current)
type( node ), intent(inout), pointer :: current
 
if (associated( current%next )) current%next%previous => current%previous
if (associated( current%previous )) current%previous%next => current%next
deallocate(current)
end subroutine delete
end module dlList
 
program dlListTest
use dlList
type( node ), target :: head
type( node ), pointer :: current, next
 
head%data = 1.0
current => head
do i = 1, 20
call insertAfter(current, 2.0**i)
current => current%next
end do
 
current => head
do while (associated(current))
print *, current%data
next => current%next
if (.not. associated(current, head)) call delete(current)
current => next
end do
end program dlListTest

Output:

1.
2.
4.
8.
16.
32.
64.
128.
256.
512.
1024.
2048.
4096.
8192.
16384.
32768.
65536.
131072.
262144.
524288.
1048576.


FreeBASIC[edit]

Translation of: Yabasic
#define FIL    1
#define DATO 2
#define LPREV 3
#define LNEXT 4
 
Dim Shared As Integer countNodes, Nodes
countNodes = 0
Nodes = 10
 
Dim Shared As Integer list(Nodes, 4)
list(0, LNEXT) = 1
 
Function searchNode(node As Integer) As Integer
Dim As Integer Node11
 
For i As Integer = 0 To node-1
Node11 = list(Node11, LNEXT)
Next i
Return Node11
End Function
 
Sub insertNode(node As Integer, newNode As Integer)
Dim As Integer Node11, i
 
If countNodes = 0 Then node = 2
 
For i = 1 To Nodes
If Not list(i, FIL) Then Exit For
Next
list(i, FIL) = True
list(i, DATO) = newNode
 
Node11 = searchNode(node)
 
list(i, LPREV) = list(Node11, LPREV)
list(list(i, LPREV), LNEXT) = i
If i <> Node11 Then list(i, LNEXT) = Node11 : list(Node11, LPREV) = i
 
countNodes += 1
If countNodes = Nodes Then Nodes += 10 : Redim list(Nodes, 4)
End Sub
 
Sub removeNode(n As Integer)
Dim As Integer Node11 = searchNode(n)
list(list(Node11, LPREV), LNEXT) = list(Node11, LNEXT)
list(list(Node11, LNEXT), LPREV) = list(Node11, LPREV)
list(Node11, LNEXT) = 0
list(Node11, LPREV) = 0
list(Node11, FIL) = False
countNodes -= 1
End Sub
 
Sub printNode(node As Integer)
Dim As Integer Node11 = searchNode(node)
Print list(Node11, DATO);
Print
End Sub
 
Sub traverseList()
For i As Integer = 1 To countNodes
printNode(i)
Next i
End Sub
 
insertNode(1, 1000)
insertNode(2, 2000)
insertNode(2, 3000)
 
traverseList()
 
removeNode(2)
 
Print
traverseList()
Sleep
Output:
Igual que la entrada de Yabasic.


Go[edit]

package main
 
import "fmt"
 
type dlNode struct {
string
next, prev *dlNode
}
 
type dlList struct {
head, tail *dlNode
}
 
func (list *dlList) String() string {
if list.head == nil {
return fmt.Sprint(list.head)
}
r := "[" + list.head.string
for p := list.head.next; p != nil; p = p.next {
r += " " + p.string
}
return r + "]"
}
 
func (list *dlList) insertTail(node *dlNode) {
if list.tail == nil {
list.head = node
} else {
list.tail.next = node
}
node.next = nil
node.prev = list.tail
list.tail = node
}
 
func (list *dlList) insertAfter(existing, insert *dlNode) {
insert.prev = existing
insert.next = existing.next
existing.next.prev = insert
existing.next = insert
if existing == list.tail {
list.tail = insert
}
}
 
func main() {
dll := &dlList{}
fmt.Println(dll)
a := &dlNode{string: "A"}
dll.insertTail(a)
dll.insertTail(&dlNode{string: "B"})
fmt.Println(dll)
dll.insertAfter(a, &dlNode{string: "C"})
fmt.Println(dll)
}

Output:

<nil>
[A B]
[A C B]

Haskell[edit]

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
where new = updateLeft left . updateRight right $ Node l nv r
left = Node pl v new
right = case r of
Leaf -> Leaf
Node _ v r -> Node new v r
 

Icon and Unicon[edit]

Uses Unicon classes.

 
class DoubleLink (value, prev_link, next_link)
 
# insert given node after this one, losing its existing connections
method insert_after (node)
node.prev_link := self
if (\next_link) then next_link.prev_link := node
node.next_link := next_link
self.next_link := node
end
 
initially (value, prev_link, next_link)
self.value := value
self.prev_link := prev_link # links are 'null' if not given
self.next_link := next_link
end
 

J[edit]

Using the list element definition at Doubly-linked_list/Element_definition#J

 (pred;succ;<data) conew 'DoublyLinkedListElement'

This creates a new node containing the specified data between the nodes pred and succ.

Java[edit]

The LinkedList<T> class is the Doubly-linked list implementation in Java. There are a large number of methods supporting the list.

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 AddAfter method. A class with this method inherting all methods from the LinkedList<T> class is shown below.

 
import java.util.LinkedList;
 
@SuppressWarnings("serial")
public class DoublyLinkedListInsertion<T> extends LinkedList<T> {
 
public static void main(String[] args) {
DoublyLinkedListInsertion<String> list = new DoublyLinkedListInsertion<String>();
list.addFirst("Add First 1");
list.addFirst("Add First 2");
list.addFirst("Add First 3");
list.addFirst("Add First 4");
list.addFirst("Add First 5");
traverseList(list);
 
list.addAfter("Add First 3", "Add New");
traverseList(list);
}
 
/*
* Add after indicated node. If not in the list, added as the last node.
*/

public void addAfter(T after, T element) {
int index = indexOf(after);
if ( index >= 0 ) {
add(index + 1, element);
}
else {
addLast(element);
}
}
 
private static void traverseList(LinkedList<String> list) {
System.out.println("Traverse List:");
for ( int i = 0 ; i < list.size() ; i++ ) {
System.out.printf("Element number %d - Element value = '%s'%n", i, list.get(i));
}
System.out.println();
}
 
}
 
Output:
Traverse List:
Element number 0 - Element value = 'Add First 5'
Element number 1 - Element value = 'Add First 4'
Element number 2 - Element value = 'Add First 3'
Element number 3 - Element value = 'Add First 2'
Element number 4 - Element value = 'Add First 1'

Traverse List:
Element number 0 - Element value = 'Add First 5'
Element number 1 - Element value = 'Add First 4'
Element number 2 - Element value = 'Add First 3'
Element number 3 - Element value = 'Add New'
Element number 4 - Element value = 'Add First 2'
Element number 5 - Element value = 'Add First 1'

JavaScript[edit]

See Doubly-Linked_List_(element)#JavaScript

DoublyLinkedList.prototype.insertAfter = function(searchValue, nodeToInsert) {
if (this._value == searchValue) {
var after = this.next();
this.next(nodeToInsert);
nodeToInsert.prev(this);
nodeToInsert.next(after);
after.prev(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 = createDoublyLinkedListFromArray(['A','B']);
list.insertAfter('A', new DoublyLinkedList('C', null, null));

Julia[edit]

mutable struct DLNode{T}
value::T
pred::Union{DLNode{T}, Nothing}
succ::Union{DLNode{T}, Nothing}
DLNode(v) = new{typeof(v)}(v, nothing, nothing)
end
 
function insertpost(prevnode, node)
succ = prevnode.succ
prevnode.succ = node
node.pred = prevnode
node.succ = succ
if succ != nothing
succ.pred = node
end
node
end
 
function printfromroot(root)
print(root.value)
while root.succ != nothing
root = root.succ
print(" -> $(root.value)")
end
println()
end
 
node1 = DLNode(1)
printfromroot(node1)
node2 = DLNode(2)
node3 = DLNode(3)
insertpost(node1, node2)
printfromroot(node1)
insertpost(node1, node3)
printfromroot(node1)
 
Output:

1 1 -> 2 1 -> 3 -> 2

Kotlin[edit]

// version 1.1.2
 
class Node<T: Number>(var data: T, var prev: Node<T>? = null, 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> insert(after: Node<T>, new: Node<T>) {
new.next = after.next
if (after.next != null) after.next!!.prev = new
new.prev = after
after.next = new
}
 
fun main(args: Array<String>) {
val a = Node(1)
val b = Node(3, a)
a.next = b
println("Before insertion : $a")
val c = Node(2)
insert(after = a, new = c)
println("After insertion : $a")
}
Output:
Before insertion : 1 -> 3
After  insertion : 1 -> 2 -> 3

Lua[edit]

see Doubly-linked_list/Definition#Lua

Mathematica/Wolfram Language[edit]

ds = CreateDataStructure["DoublyLinkedList"];
ds["Append", "A"];
ds["Append", "B"];
ds["Append", "C"];
ds["SwapPart", 2, 3];
ds["Elements"]
Output:
{"A", "C", "B"}

Nim[edit]

proc insertAfter[T](l: var List[T], r, n: Node[T]) =
n.prev = r
n.next = r.next
n.next.prev = n
r.next = n
if r == l.tail: l.tail = n

Oberon-2[edit]

 
PROCEDURE (dll: DLList) InsertAfter*(p: Node; o: Box.Object);
VAR
n: Node;
BEGIN
n := NewNode(o);
n.prev := p;
n.next := p.next;
IF p.next # NIL THEN p.next.prev := n END;
p.next := n;
IF p = dll.last THEN dll.last := n END;
INC(dll.size)
END InsertAfter;
 

Objeck[edit]

method : public : native : AddBack(value : Base) ~ Nil {
node := ListNode->New(value);
if(@head = Nil) {
@head := node;
@tail := @head;
}
else {
@tail->SetNext(node);
node->SetPrevious(@tail);
@tail := node;
};
}

OCaml[edit]

with dlink[edit]

(* val _insert : 'a dlink -> 'a dlink -> unit *)
let _insert anchor newlink =
newlink.next <- anchor.next;
newlink.prev <- Some anchor;
begin match newlink.next with
| None -> ()
| Some next ->
next.prev <-Some newlink;
end;
anchor.next <- Some newlink;;
 
(* val insert : 'a dlink option -> 'a -> unit *)
let insert dl v =
match dl with
| (Some anchor) -> _insert anchor {data=v; prev=None; next=None}
| None -> invalid_arg "dlink empty";;

testing in the top level:

# type t = A | B | C ;;
type t = A | B | C
 
# let dl = dlink_of_list [A; B] in
insert dl C;
list_of_dlink dl ;;
- : t list = [A; C; B]

with nav_list[edit]

(* val insert : 'a nav_list -> 'a -> 'a nav_list *)
let insert (prev, cur, next) v = (prev, cur, v::next)

testing in the top level:

# type t = A | B | C ;;
type t = A | B | C
 
# let nl = nav_list_of_list [A; B] ;;
val nl : 'a list * t * t list = ([], A, [B])
 
# insert nl C ;;
- : 'a list * t * t list = ([], A, [C; B])

Oforth[edit]

Complete definition is here : Doubly-linked list/Definition#Oforth

: test      // ( -- aDList )
| dl |
DList new ->dl
dl insertFront("A")
dl insertBack("B")
dl head insertAfter(DNode new("C", null , null))
dl ;
Output:
>test .s
[1] (DList) [A, C, B]

Oz[edit]

Warning: Do not use in real programs.

declare
fun {CreateNewNode Value}
node(prev:{NewCell nil}
next:{NewCell nil}
value:Value)
end
 
proc {InsertAfter Node NewNode}
Next = Node.next
in
(NewNode.next) := @Next
(NewNode.prev) := Node
case @Next of nil then skip
[] node(prev:NextPrev ...) then
NextPrev := NewNode
end
Next := NewNode
end
 
A = {CreateNewNode a}
B = {CreateNewNode b}
C = {CreateNewNode c}
in
{InsertAfter A B}
{InsertAfter A C}

Pascal[edit]

procedure insert_link( a, b, c: link_ptr );
begin
a^.next := c;
if b <> nil then b^.prev := c;
c^.next := b;
c^.prev := a;
end;

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

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

Perl[edit]

my %node_model = (
data => 'something',
prev => undef,
next => undef,
);
 
sub insert
{
my ($anchor, $newlink) = @_;
$newlink->{next} = $anchor->{next};
$newlink->{prev} = $anchor;
$newlink->{next}->{prev} = $newlink;
$anchor->{next} = $newlink;
}
 
# create the list {A,B}
my $node_a = { %node_model };
my $node_b = { %node_model };
 
$node_a->{next} = $node_b;
$node_b->{prev} = $node_a;
 
# insert element C into a list {A,B}, between elements A and B.
my $node_c = { %node_model };
insert($node_a, $node_c);

Phix[edit]

See also Doubly-linked_list/Traversal.

enum NEXT,PREV,DATA
constant empty_dll = {{1,1}}
sequence dll = deep_copy(empty_dll)
 
procedure insert_after(object data, integer pos=1)
    integer prv = dll[pos][PREV]
    dll = append(dll,{pos,prv,data})
    if prv!=0 then
        dll[prv][NEXT] = length(dll)
    end if
    dll[pos][PREV] = length(dll)
end procedure
 
insert_after("ONE")
insert_after("TWO")
insert_after("THREE")
 
?dll
Output:
{{2,4},{3,1,"ONE"},{4,2,"TWO"},{1,3,"THREE"}}

PicoLisp[edit]

This works with the structures described in Doubly-linked list/Definition#PicoLisp and Doubly-linked list/Element definition#PicoLisp.

# Insert an element X at position Pos
(de 2insert (X Pos DLst)
(let (Lst (nth (car DLst) (dec (* 2 Pos))) New (cons X (cadr Lst) Lst))
(if (cadr Lst)
(con (cdr @) New)
(set DLst New) )
(if (cdr Lst)
(set @ New)
(con DLst New) ) ) )
 
(setq *DL (2list 'A 'B)) # Build a two-element doubly-linked list
(2insert 'C 2 *DL) # Insert C at position 2

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

PL/I[edit]

 
define structure
1 Node,
2 value fixed decimal,
2 back_pointer handle(Node),
2 fwd_pointer handle(Node);
 
/* Given that 'Current" points at some node in the linked list : */
 
P = NEW (: Node :); /* Create a node. */
get (P => value);
P => fwd_pointer = Current => fwd_pointer;
/* Points the new node at the next one. */
Current => fwd_pinter = P;
/* Points the current node at the new one. */
P => back_pointer = Current;
/* Points the new node back at the current one. */
Q = P => fwd_pointer;
Q => back_pointer = P;
/* Points the next node to the new one. */
 

Pop11[edit]

define insert_double(list, element);
lvars tmp;
if list == [] then
 ;;; Insertion into empty list, return element
element
else
next(list) -> tmp;
list -> prev(element);
tmp -> next(element);
element -> next(list);
if tmp /= [] then
element -> prev(tmp)
endif;
 ;;; return original list
list
endif;
enddefine;
 
lvars A = newLink(), B = newLink(), C = newLink();
;;; Build the list of A and B
insert_double(A, B) -> _;
;;; insert C between A and b
insert_double(A, C) -> _;

PureBasic[edit]

Structure node
*prev.node
*next.node
value.c ;use character type for elements in this example
EndStructure
 
Procedure insertAfter(element.c, *c.node)
;insert new node *n after node *c and set it's value to element
Protected *n.node = AllocateMemory(SizeOf(node))
If *n
*n\value = element
*n\prev = *c
If *c
*n\next = *c\next
*c\next = *n
EndIf
EndIf
ProcedureReturn *n
EndProcedure
 
Procedure displayList(*dl.node)
Protected *n.node = *dl
Repeat
Print(Chr(*n\Value) + " ")
*n = *n\next
Until *n = #Null
EndProcedure
 
If OpenConsole()
Define dl.node, *n.node
 
*n = insertAfter('A',dl)
insertAfter('B',*n)
insertAfter('C',*n)
 
displayList(dl)
 
Print(#CRLF$ + #CRLF$ + "Press ENTER to exit")
Input()
CloseConsole()
EndIf

Sample output:

A C B

Python[edit]

def insert(anchor, new):
new.next = anchor.next
new.prev = anchor
anchor.next.prev = new
anchor.next = new

Racket[edit]

Code is on the Doubly-Linked List page, in function insert-between.

Raku[edit]

(formerly Perl 6)

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

role DLElem[::T] {
has DLElem[T] $.prev is rw;
has DLElem[T] $.next is rw;
has T $.payload = T;
 
method pre-insert(T $payload) {
die "Can't insert before beginning" unless $!prev;
my $elem = ::?CLASS.new(:$payload);
$!prev.next = $elem;
$elem.prev = $!prev;
$elem.next = self;
$!prev = $elem;
$elem;
}
 
method post-insert(T $payload) {
die "Can't insert after end" unless $!next;
my $elem = ::?CLASS.new(:$payload);
$!next.prev = $elem;
$elem.next = $!next;
$elem.prev = self;
$!next = $elem;
$elem;
}
 
method delete {
die "Can't delete a sentinel" unless $!prev and $!next;
$!next.prev = $!prev;
$!prev.next = $!next; # conveniently returns next element
}
}
 
role DLList[::DLE] {
has DLE $.first;
has DLE $.last;
 
submethod BUILD {
$!first = DLE.new;
$!last = DLE.new;
$!first.next = $!last;
$!last.prev = $!first;
}
 
method list { ($!first.next, *.next ...^ !*.next).map: *.payload }
method reverse { ($!last.prev, *.prev ...^ !*.prev).map: *.payload }
}
 
class DLElem_Str does DLElem[Str] {}
class DLList_Str does DLList[DLElem_Str] {}
 
my $sdll = DLList_Str.new;
my $b = $sdll.first.post-insert('A').post-insert('B');
$b.pre-insert('C');
say $sdll.list; # A C B
Output:
A C B

REXX[edit]

REXX doesn't have linked lists, as there are no pointers (or handles).
However, linked lists can be simulated with lists in REXX.

/*REXX program that implements various   List Manager   functions.      */
/*┌────────────────────────────────────────────────────────────────────┐
┌─┘ Functions of the List Manager └─┐
│ │
│ @init ─── initializes the List. │
│ │
│ @size ─── returns the size of the List [could be 0 (zero)]. │
│ │
│ @show ─── shows (displays) the complete List. │
│ @show k,1 ─── shows (displays) the Kth item. │
│ @show k,m ─── shows (displays) M items, starting with Kth item. │
│ @show ,,─1 ─── shows (displays) the complete List backwards. │
│ │
│ @get k ─── returns the Kth item. │
│ @get k,m ─── returns the M items starting with the Kth item. │
│ │
│ @put x ─── adds the X items to the end (tail) of the List. │
│ @put x,0 ─── adds the X items to the start (head) of the List. │
│ @put x,k ─── adds the X items to before of the Kth item. │
│ │
│ @del k ─── deletes the item K. │
│ @del k,m ─── deletes the M items starting with item K. │
└─┐ ┌─┘
└────────────────────────────────────────────────────────────────────┘*/

call sy 'initializing the list.'  ; call @init
call sy 'building list: Was it a cat I saw'; call @put 'Was it a cat I saw'
call sy 'displaying list size.'  ; say 'list size='@size()
call sy 'forward list'  ; call @show
call sy 'backward list'  ; call @show ,,-1
call sy 'showing 4th item'  ; call @show 4,1
call sy 'showing 6th & 6th items'  ; call @show 5,2
call sy 'adding item before item 4: black' ; call @put 'black',4
call sy 'showing list'  ; call @show
call sy 'adding to tail: there, in the ...'; call @put 'there, in the shadows, stalking its prey (and next meal).'
call sy 'showing list'  ; call @show
call sy 'adding to head: Oy!'  ; call @put 'Oy!',0
call sy 'showing list'  ; call @show
exit /*stick a fork in it, we're done.*/
/*──────────────────────────────────subroutines─────────────────────────*/
p: return word(arg(1),1)
sy: say; say left('',30) "───" arg(1) '───'; return
@hasopt: arg o; return pos(o,opt)\==0
@size: return $.#
@init: $.@=''; $.#=0; return 0
@adjust: $.@=space($.@); $.#=words($.@); return 0
 
@parms: arg opt
if @hasopt('k') then k=min($.#+1,max(1,p(k 1)))
if @hasopt('m') then m=p(m 1)
if @hasopt('d') then dir=p(dir 1)
return
 
@show: procedure expose $.; parse arg k,m,dir
if dir==-1 & k=='' then k=$.#
m=p(m $.#);
call @parms 'kmd'
say @get(k,m,dir);
return 0
 
@get: procedure expose $.; arg k,m,dir,_
call @parms 'kmd'
do j=k for m by dir while j>0 & j<=$.#
_=_ subword($.@,j,1)
end /*j*/
return strip(_)
 
@put: procedure expose $.; parse arg x,k
k=p(k $.#+1)
call @parms 'k'
$.@=subword($.@,1,max(0,k-1)) x subword($.@,k)
call @adjust
return 0
 
@del: procedure expose $.; arg k,m
call @parms 'km'
_=subword($.@,k,k-1) subword($.@,k+m)
$.@=_
call @adjust
return

output

                               ─── initializing the list. ───

                               ─── building list: Was it a cat I saw ───

                               ─── displaying list size. ───
list size=6

                               ─── forward list ───
Was it a cat I saw

                               ─── backward list ───
saw I cat a it Was

                               ─── showing 4th item ───
cat

                               ─── showing 6th & 6th items ───
I saw

                               ─── adding item before item 4: black ───

                               ─── showing list ───
Was it a black cat I saw

                               ─── adding to tail: there, in the ... ───

                               ─── showing list ───
Was it a black cat I saw there, in the shadows, stalking its prey (and next meal).

                               ─── adding to head: Oy! ───

                               ─── showing list ───
Oy! Was it a black cat I saw there, in the shadows, stalking its prey (and next meal).

Ruby[edit]

class DListNode
def insert_after(search_value, new_value)
if search_value == value
new_node = self.class.new(new_value, nil, nil)
next_node = self.succ
self.succ = new_node
new_node.prev = self
new_node.succ = next_node
next_node.prev = new_node
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
 
head = DListNode.from_array([:a, :b])
head.insert_after(:a, :c)

Rust[edit]

Simply using the standard library[edit]

use std::collections::LinkedList;
fn main() {
let mut list = LinkedList::new();
list.push_front(8);
}

The behind-the-scenes implementation[edit]

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.

impl<T> Node<T> {
fn new(v: T) -> Node<T> {
Node {value: v, next: None, prev: Rawlink::none()}
}
}
 
impl<T> Rawlink<T> {
fn none() -> Self {
Rawlink {p: ptr::null_mut()}
}
 
fn some(n: &mut T) -> Rawlink<T> {
Rawlink{p: n}
}
}
 
impl<'a, T> From<&'a mut Link<T>> for Rawlink<Node<T>> {
fn from(node: &'a mut Link<T>) -> Self {
match node.as_mut() {
None => Rawlink::none(),
Some(ptr) => Rawlink::some(ptr)
}
}
}
 
 
fn link_no_prev<T>(mut next: Box<Node<T>>) -> Link<T> {
next.prev = Rawlink::none();
Some(next)
}
 
impl<T> LinkedList<T> {
#[inline]
fn push_front_node(&mut self, mut new_head: Box<Node<T>>) {
match self.list_head {
None => {
self.list_head = link_no_prev(new_head);
self.list_tail = Rawlink::from(&mut self.list_head);
}
Some(ref mut head) => {
new_head.prev = Rawlink::none();
head.prev = Rawlink::some(&mut *new_head);
mem::swap(head, &mut new_head);
head.next = Some(new_head);
}
}
self.length += 1;
}
pub fn push_front(&mut self, elt: T) {
self.push_front_node(Box::new(Node::new(elt)));
}
}

Swift[edit]

typealias NodePtr<T> = UnsafeMutablePointer<Node<T>>
 
class Node<T> {
var value: T
fileprivate var prev: NodePtr<T>?
fileprivate var next: NodePtr<T>?
 
init(value: T, prev: NodePtr<T>? = nil, next: NodePtr<T>? = nil) {
self.value = value
self.prev = prev
self.next = next
}
}
 
@discardableResult
func insert<T>(_ val: T, after: Node<T>? = nil, list: NodePtr<T>? = nil) -> NodePtr<T> {
let node = NodePtr<T>.allocate(capacity: 1)
 
node.initialize(to: Node(value: val))
 
var n = list
 
while n != nil {
if n?.pointee !== after {
n = n?.pointee.next
 
continue
}
 
node.pointee.prev = n
node.pointee.next = n?.pointee.next
n?.pointee.next?.pointee.prev = node
n?.pointee.next = node
 
break
}
 
return node
}
 
// [1]
let list = insert(1)
 
// [1, 2]
insert(2, after: list.pointee, list: list)
 
// [1, 3, 2]
insert(3, after: list.pointee, list: list)

Tcl[edit]

See Doubly-Linked List (element) for caveats about linked lists in Tcl.

Works with: Tcl version 8.6
oo::define List {
method insertBefore {elem} {
$elem next [self]
$elem previous $prev
if {$prev ne ""} {
$prev next $elem
}
set prev $elem
}
method insertAfter {elem} {
$elem previous [self]
$elem next $next
if {$next ne ""} {
$next previous $elem
}
set next $elem
}
}

Demonstration:

set B [List new 3]
set A [List new 1 $B]
set C [List new 2]
$A insertAfter $C
puts [format "{%d,%d,%d}" [$A value] [[$A next] value] [[[$A next] next] value]]

Visual Basic .NET[edit]

Public Sub Insert(ByVal a As Node(Of T), ByVal b As Node(Of T), ByVal c As T)
Dim node As New Node(Of T)(value)
a.Next = node
node.Previous = a
b.Previous = node
node.Next = b
End Sub

Wren[edit]

Library: Wren-llist
import "/llist" for DLinkedList
 
var dll = DLinkedList.new(["A", "B"])
dll.insertAfter("A", "C")
System.print(dll)
Output:
[A <-> C <-> B]

Yabasic[edit]

// Rosetta Code problem: http://rosettacode.org/wiki/Doubly-linked_list/Element_insertion & removal & traverse
// by Galileo, 02/2022
 
FIL = 1 : DATO = 2 : LPREV = 3 : LNEXT = 4
countNodes = 0 : Nodes = 10
 
dim list(Nodes, 4)
 
list(0, LNEXT) = 1
 
 
sub searchNode(node)
local i, Node
 
for i = 0 to node-1
Node = list(Node, LNEXT)
next
return Node
end sub
 
sub insertNode(node, newNode)
local Node, i
 
if not countNodes node = 2
 
for i = 1 to Nodes
if not list(i, FIL) break
next
list(i, FIL) = true
list(i, DATO) = newNode
 
Node = searchNode(node)
 
list(i, LPREV) = list(Node, LPREV) : list(list(i, LPREV), LNEXT) = i
if i <> Node list(i, LNEXT) = Node : list(Node, LPREV) = i
 
countNodes = countNodes + 1
if countNodes = Nodes then Nodes = Nodes + 10 : redim list(Nodes, 4) : end if
end sub
 
 
sub removeNode(n)
local Node
 
Node = searchNode(n)
list(list(Node, LPREV), LNEXT) = list(Node, LNEXT)
list(list(Node, LNEXT), LPREV) = list(Node, LPREV)
list(Node, LNEXT) = 0 : list(Node, LPREV) = 0
list(Node, FIL) = false
countNodes = countNodes - 1
end sub
 
 
sub printNode(node)
local Node
 
Node = searchNode(node)
print list(Node, DATO);
print
end sub
 
 
sub traverseList()
local i
 
for i = 1 to countNodes
printNode(i)
next
end sub
 
 
insertNode(1, 1000)
insertNode(2, 2000)
insertNode(2, 3000)
 
traverseList()
 
removeNode(2)
 
print
traverseList()
Output:
1000
3000
2000

1000
2000
---Program done, press RETURN---

zkl[edit]

class Node{
fcn init(_value,_prev=Void,_next=Void)
{ var value=_value, prev=_prev, next=_next; }
fcn toString{ value.toString() }
fcn append(value){
b,c := Node(value,self,next),next;
next=b;
if(c) c.prev=b;
b
}
}
a:=Node("a"); 
a.append("b").append("c");
println(a," ",a.next," ",a.next.next);
Output:
a  b  c