Doubly-linked list/Element insertion
From Rosetta Code
You are encouraged to solve this task according to the task description, using any language you may know.
This is much like inserting into a Singly-Linked List, but with added assignments so that the backwards-pointing links remain correct.
Contents |
[edit] Ada
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;
[edit] AutoHotkey
see Doubly-linked list/AutoHotkey
[edit] C
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}.
[edit] C#
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);
}
[edit] Common Lisp
Code is on the Doubly-Linked List page, in function insert-between.
[edit] E
def insert(after, value) {
def newNode := makeElement(value, after, after.getNext())
after.getNext().setPrev(newNode)
after.setNext(newNode)
}
insert(A_node, C)
[edit] Fortran
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.
[edit] Haskell
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
[edit] J
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.
[edit] JavaScript
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));
[edit] OCaml
[edit] with dlink
(* 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]
[edit] with nav_list
(* 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])
[edit] Oz
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}
[edit] Pascal
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;
[edit] Perl
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);
[edit] PL/I
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. */
[edit] PicoLisp
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.
[edit] Pop11
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) -> _;
[edit] PureBasic
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
[edit] Python
def insert(anchor, new):
new.next = anchor.next
new.prev = anchor
anchor.next.prev = new
anchor.next = new
[edit] Ruby
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)
[edit] Tcl
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]]
[edit] Visual Basic .NET
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

