CloudFlare suffered a massive security issue affecting all of its customers, including Rosetta Code. All passwords not changed since February 19th 2017 have been expired, and session cookie longevity will be reduced until late March.--Michael Mol (talk) 05:15, 25 February 2017 (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

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 
Link_Access : A, B, C;
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; 

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]

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;
}


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);
}

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 

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.

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.

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));

Kotlin[edit]

// version 1.1.1
 
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

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);

Perl 6[edit]

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

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

Phix[edit]

See also Doubly-linked_list/Traversal.

enum NEXT,PREV,DATA
constant empty_dll = {{1,1}}
sequence dll = 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.


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)));
}
}

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

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