Doubly-linked list/Element insertion: Difference between revisions
(Added Erlang) |
(Add Nimrod) |
||
Line 493: | Line 493: | ||
var list = createDoublyLinkedListFromArray(['A','B']); |
var list = createDoublyLinkedListFromArray(['A','B']); |
||
list.insertAfter('A', new DoublyLinkedList('C', null, null));</lang> |
list.insertAfter('A', new DoublyLinkedList('C', null, null));</lang> |
||
=={{header|Nimrod}}== |
|||
<lang nimrod>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</lang> |
|||
=={{header|OCaml}}== |
=={{header|OCaml}}== |
Revision as of 14:12, 13 July 2014
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
- Array
- Associative array: Creation, Iteration
- Collections
- Compound data type
- Doubly-linked list: Definition, Element definition, Element insertion, List Traversal, Element Removal
- Linked list
- Queue: Definition, Usage
- Set
- Singly-linked list: Element definition, Element insertion, List Traversal, Element Removal
- Stack
Ada
Define the procedure: <lang ada>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;</lang> Create links and form the list.
<lang ada>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;</lang>
Element insertion using the generic doubly linked list defined in the standard Ada containers library.
<lang ada>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;</lang>
ALGOL 68
<lang algol68>#!/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)
)</lang> Output:
1993: Clinton; 2001: Bush; 2004: Cheney; 2008: Obama;
AutoHotkey
see Doubly-linked list/AutoHotkey
BBC BASIC
<lang bbcbasic> 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
</lang>
C
Define the function: <lang c>void insert(link* anchor, link* newlink) {
newlink->next = anchor->next; newlink->prev = anchor; (newlink->next)->prev = newlink; anchor->next = newlink;
}</lang>
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: <lang c>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;</lang>
This list is now {a,b}, and c is separate.
Now call the function: <lang c>insert(&a, &c);</lang>
This function call changes the list from {a,b} to {a,b,c}.
C#
The function handles creation of nodes in addition to inserting them. <lang csharp>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 };
}</lang> Example use: <lang csharp>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);
}</lang>
Clojure
This sort of mutable structure is not idiomatic in Clojure. Doubly-linked list/Definition#Clojure or a finger tree implementation would be better.
<lang Clojure>(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))</lang>
Common Lisp
Code is on the Doubly-Linked List page, in function insert-between
.
D
<lang d>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;
}</lang>
- Output:
A A B A C B
E
<lang e>def insert(after, value) {
def newNode := makeElement(value, after, after.getNext()) after.getNext().setPrev(newNode) after.setNext(newNode)
}</lang>
<lang e>insert(A_node, C)</lang>
Erlang
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
In ISO Fortran 95 or later: <lang fortran>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</lang> Output: <lang fortran>1. 2. 4. 8. 16. 32. 64. 128. 256. 512. 1024. 2048. 4096. 8192. 16384. 32768. 65536. 131072. 262144. 524288. 1048576.</lang>
Go
<lang 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)
}</lang> Output:
<nil> [A B] [A C B]
Haskell
Using the algebraic data type and update functions from Doubly-Linked_List_(element)#Haskell.
<lang 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
</lang>
Icon and Unicon
Uses Unicon classes.
<lang Unicon> 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 </lang>
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.
JavaScript
See Doubly-Linked_List_(element)#JavaScript <lang 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));</lang>
Nimrod
<lang nimrod>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</lang>
OCaml
with dlink
<lang ocaml>(* 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";;</lang>
testing in the top level:
<lang ocaml># 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]</lang>
<lang ocaml>(* val insert : 'a nav_list -> 'a -> 'a nav_list *) let insert (prev, cur, next) v = (prev, cur, v::next)</lang>
testing in the top level: <lang ocaml># 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])</lang>
Oz
Warning: Do not use in real programs. <lang oz>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}</lang>
Pascal
<lang 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;</lang>
Actually, a more likely real world scenario is 'insert after A'. So...
<lang pascal>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;</lang>
Perl
<lang 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);</lang>
Perl 6
Using the generic definitions from Doubly-linked_list/Definition#Perl_6: <lang perl6>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</lang>
- Output:
A C B
PicoLisp
This works with the structures described in Doubly-linked list/Definition#PicoLisp and Doubly-linked list/Element definition#PicoLisp. <lang 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</lang> For output of the example data, see Doubly-linked list/Traversal#PicoLisp.
PL/I
<lang 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. */
</lang>
Pop11
<lang 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) -> _;</lang>
PureBasic
<lang 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</lang> Sample output:
A C B
Python
<lang python>def insert(anchor, new):
new.next = anchor.next new.prev = anchor anchor.next.prev = new anchor.next = new</lang>
Racket
Code is on the Doubly-Linked List page, in function insert-between
.
REXX
REXX doesn't have linked lists, as there are no pointers (or handles).
However, linked lists can be simulated with lists in REXX.
<lang 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</lang>
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
<lang 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)</lang>
Tcl
See Doubly-Linked List (element) for caveats about linked lists in Tcl.
<lang 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 }
}</lang> Demonstration: <lang tcl>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]]</lang>
Visual Basic .NET
<lang vbnet>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</lang>