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] ALGOL 68
#!/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;
[edit] AutoHotkey
see Doubly-linked list/AutoHotkey
[edit] BBC BASIC
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
[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] Clojure
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))
[edit] Common Lisp
Code is on the Doubly-Linked List page, in function insert-between.
[edit] D
import std.stdio;
struct Node(T) {
T data;
Node* prev, next;
this(T data_, Node* prev_=null, Node* next_=null) {
data = data_;
prev = prev_;
next = next_;
}
}
void show(T)(Node!(T)* list) {
while (list) {
write(list.data, " ");
list = list.next;
}
writeln();
}
/// If prev is null, prev gets to point to a new node
void insertAfter(T)(ref Node!(T)* prev, T item) {
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 main() {
Node!(string)* list;
insertAfter(list, "A");
show(list);
insertAfter(list, "B");
show(list);
insertAfter(list, "C");
show(list);
}
Output:
A A B A C B
[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] Go
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]
[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] Icon and Unicon
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
[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]
(* 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] 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] 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] 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] REXX
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
/*===========================subroutines================================*/
sy: say; say left('',30) "---" arg(1) '---'; return
p: return word(arg(1),1)
@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
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).
[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.
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
