Use the link structure defined inDoubly-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 aSingly-Linked List, but with added assignments so that the backwards-pointing links remain correct.
The user must type in the monitor the following command after compilation and before running the program!
SET EndProg=*
CARD EndProg ;required for ALLOCATE.ACTINCLUDE "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,listEndPROC 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=nRETURNPROC 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=nRETURNPROC 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 FIRETURNPROC Clear() ListNode POINTER n,next n=listBegin WHILE n DO next=n.nxt Free(n,NODE_SIZE) n=next OD listBegin=0 listEnd=0RETURNPROC PrintList() ListNode POINTER n n=listBegin Print("(") WHILE n DO Put(n.data) IF n.nxt THEN Print(", ") FI n=n.nxt OD PrintE(")")RETURNPROC TestAddBegin(CHAR v) AddBegin(v) PrintF("Add '%C' at the begin:%E",v) PrintList()RETURNPROC TestAddAfter(CHAR v ListNode POINTER node) AddAfter(v,node) PrintF("Add '%C' after '%C':%E",v,node.data) PrintList()RETURNPROC TestClear() Clear() PrintE("Clear the list:") PrintList()RETURNPROC Main() Put(125) PutE() ;clear screen AllocInit(0) listBegin=0 listEnd=0 PrintList() TestAddBegin('A) TestAddAfter('B,listBegin) TestAddAfter('C,listBegin) TestClear()RETURNScreenshot 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:()
Define the procedure:
procedureInsert(Anchor:Link_Access;New_Link:Link_Access)isbeginifAnchor/=NullandNew_Link/=NullthenNew_Link.Next:=Anchor.Next;New_Link.Prev:=Anchor;ifNew_Link.Next/=NullthenNew_Link.Next.Prev:=New_Link;endif;Anchor.Next:=New_Link;endif;endInsert;
Create links and form the list.
procedureMake_ListisA,B,C:Link_Access;beginA:=newLink;B:=newLink;C:=newLink;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)endMake_List;
Element insertion using the generic doubly linked list defined in the standard Ada containers library.
withAda.Containers.Doubly_Linked_Lists;withAda.Text_Io;useAda.Text_Io;withAda.Strings.Unbounded;useAda.Strings.Unbounded;procedureList_InsertionispackageString_Listis newAda.Containers.Doubly_Linked_Lists(Unbounded_String);useString_List;procedurePrint(Position:Cursor)isbeginPut_Line(To_String(Element(Position)));endPrint;The_List:List;beginThe_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);endList_Insertion;
#!/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;
% 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 ;
seeDoubly-linked list/AutoHotkey
Lbl INSERT{r₁+2}ʳ→{r₂+2}ʳr₁→{r₂+4}ʳr₂→{{r₂+2}ʳ+4}ʳr₂→{r₁+2}ʳr₁ReturnDIMnode{pPrev%,pNext%,iData%}DIMa{}=node{},b{}=node{},c{}=node{}a.pNext%=b{}a.iData%=123b.pPrev%=a{}b.iData%=456c.iData%=789PROCinsert(a{},c{})ENDDEFPROCinsert(here{},new{})LOCALtemp{}:DIMtemp{}=node{}new.pNext%=here.pNext%new.pPrev%=here{}!(^temp{}+4)=new.pNext%temp.pPrev%=new{}here.pNext%=new{}ENDPROC
Define the function:
voidinsert(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:
linka,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}.
The function handles creation of nodes in addition to inserting them.
staticvoidInsertAfter(Linkprev,inti){if(prev.next!=null){prev.next.prev=newLink(){item=i,prev=prev,next=prev.next};prev.next=prev.next.prev;}elseprev.next=newLink(){item=i,prev=prev};}
Example use:
staticvoidMain(){//Create A(5)->B(7)varA=newLink(){item=5};InsertAfter(A,7);//Insert C(15) between A and BInsertAfter(A,15);}
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<typenameT>voidinsert_after(Node<T>*N,T&&data){autonode=newNode<T>{N,N->next,std::forward(data)};if(N->next!=nullptr)N->next->prev=node;N->next=node;}
This sort of mutable structure is not idiomatic in Clojure.Doubly-linked list/Definition#Clojure or a finger tree implementation would be better.
(defrecordNode[prevnextdata])(defnnew-node[prevnextdata](Node.(refprev)(refnext)data))(defnnew-list[headtail](List.(refhead)(reftail)))(defninsert-between[node1node2new-node](dosync(ref-set(:nextnode1)new-node)(ref-set(:prevnew-node)node1)(ref-set(:nextnew-node)node2)(ref-set(:prevnode2)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-nodenilnil:A)t(new-nodenilnil:B)](insert-betweenht(new-nodenilnil:C))(new-listht))
Code is on theDoubly-Linked List page, in functioninsert-between.
importstd.stdio;structNode(T){Tdata;typeof(this)*prev,next;}/// If prev is null, prev gets to point to a new node.voidinsertAfter(T)(refNode!T*prev,Titem)purenothrow{if(prev){autonewNode=newNode!T(item,prev,prev.next);prev.next=newNode;if(newNode.next)newNode.next.prev=newNode;}elseprev=newNode!T(item);}voidshow(T)(Node!T*list){while(list){write(list.data," ");list=list.next;}writeln;}voidmain(){Node!(string)*list;insertAfter(list,"A");list.show;insertAfter(list,"B");list.show;insertAfter(list,"C");list.show;}
A A B A C B
programElement_insertion;{$APPTYPE CONSOLE}usesSystem.SysUtils,Boost.LinkedList;varList:TLinkedList<Integer>;Node:TLinkedListNode<Integer>;beginList:=TLinkedList<Integer>.Create;Node:=List.Add(5);List.AddAfter(Node,7);List.AddAfter(Node,15);Writeln(List.ToString);List.Free;Readln;end.
[ 5, 15, 7]
See#Pascal for vanilla version.
def insert(after, value) { def newNode := makeElement(value, after, after.getNext()) after.getNext().setPrev(newNode) after.setNext(newNode)}insert(A_node, C)
Using the code inDoubly-linked_list/Definition.
2> doubly_linked_list:task().foreach_next aforeach_next cforeach_next bforeach_previous bforeach_previous cforeach_previous a
In ISO Fortran 95 or later:
moduledlListpublic::node,insertAfter,getNexttypenodereal::data type(node),pointer::next=>null()type(node),pointer::previous=>null()end typenodecontains subroutineinsertAfter(nodeBefore,value)type(node),intent(inout),target::nodeBeforetype(node),pointer::newNodereal,intent(in)::value allocate(newNode)newNode%data=valuenewNode%next=>nodeBefore%nextnewNode%previous=>nodeBeforeif(associated(newNode%next))thennewNode%next%previous=>newNodeend ifnewNode%previous%next=>newNodeend subroutineinsertAftersubroutinedelete(current)type(node),intent(inout),pointer::currentif(associated(current%next))current%next%previous=>current%previousif(associated(current%previous))current%previous%next=>current%nextdeallocate(current)end subroutinedeleteend moduledlListprogramdlListTestusedlListtype(node),target::headtype(node),pointer::current,nexthead%data=1.0current=>headdoi=1,20callinsertAfter(current,2.0**i)current=>current%nextend docurrent=>headdo while(associated(current))print*,current%datanext=>current%nextif(.not.associated(current,head))calldelete(current)current=>nextend doend programdlListTest
Output:
1.2.4.8.16.32.64.128.256.512.1024.2048.4096.8192.16384.32768.65536.131072.262144.524288.1048576.
#defineFIL1#defineDATO2#defineLPREV3#defineLNEXT4DimSharedAsIntegercountNodes,NodescountNodes=0Nodes=10DimSharedAsIntegerlist(Nodes,4)list(0,LNEXT)=1FunctionsearchNode(nodeAsInteger)AsIntegerDimAsIntegerNode11ForiAsInteger=0Tonode-1Node11=list(Node11,LNEXT)NextiReturnNode11EndFunctionSubinsertNode(nodeAsInteger,newNodeAsInteger)DimAsIntegerNode11,iIfcountNodes=0Thennode=2Fori=1ToNodesIfNotlist(i,FIL)ThenExitForNextlist(i,FIL)=Truelist(i,DATO)=newNodeNode11=searchNode(node)list(i,LPREV)=list(Node11,LPREV)list(list(i,LPREV),LNEXT)=iIfi<>Node11Thenlist(i,LNEXT)=Node11:list(Node11,LPREV)=icountNodes+=1IfcountNodes=NodesThenNodes+=10:Redimlist(Nodes,4)EndSubSubremoveNode(nAsInteger)DimAsIntegerNode11=searchNode(n)list(list(Node11,LPREV),LNEXT)=list(Node11,LNEXT)list(list(Node11,LNEXT),LPREV)=list(Node11,LPREV)list(Node11,LNEXT)=0list(Node11,LPREV)=0list(Node11,FIL)=FalsecountNodes-=1EndSubSubprintNode(nodeAsInteger)DimAsIntegerNode11=searchNode(node)Printlist(Node11,DATO);PrintEndSubSubtraverseList()ForiAsInteger=1TocountNodesprintNode(i)NextiEndSubinsertNode(1,1000)insertNode(2,2000)insertNode(2,3000)traverseList()removeNode(2)PrinttraverseList()Sleep
Igual que la entrada de Yabasic.
packagemainimport"fmt"typedlNodestruct{stringnext,prev*dlNode}typedlListstruct{head,tail*dlNode}func(list*dlList)String()string{iflist.head==nil{returnfmt.Sprint(list.head)}r:="["+list.head.stringforp:=list.head.next;p!=nil;p=p.next{r+=" "+p.string}returnr+"]"}func(list*dlList)insertTail(node*dlNode){iflist.tail==nil{list.head=node}else{list.tail.next=node}node.next=nilnode.prev=list.taillist.tail=node}func(list*dlList)insertAfter(existing,insert*dlNode){insert.prev=existinginsert.next=existing.nextexisting.next.prev=insertexisting.next=insertifexisting==list.tail{list.tail=insert}}funcmain(){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]
Using the algebraic data type and update functions fromDoubly-Linked_List_(element)#Haskell.
insert_Leaf=Leafinsertnvl@(Nodeplvr)=(\(Nodec__)->c)newwherenew=updateLeftleft.updateRightright$Nodelnvrleft=Nodeplvnewright=caserofLeaf->LeafNode_vr->Nodenewvr
Uses Unicon classes.
classDoubleLink(value,prev_link,next_link)# insert given node after this one, losing its existing connectionsmethodinsert_after(node)node.prev_link:=selfif(\next_link)thennext_link.prev_link:=nodenode.next_link:=next_linkself.next_link:=nodeendinitially(value,prev_link,next_link)self.value:=valueself.prev_link:=prev_link# links are 'null' if not givenself.next_link:=next_linkend
Using the list element definition atDoubly-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.
TheLinkedList<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 aAddAfter method. A class with this method inherting all methods from theLinkedList<T> class is shown below.
importjava.util.LinkedList;@SuppressWarnings("serial")publicclassDoublyLinkedListInsertion<T>extendsLinkedList<T>{publicstaticvoidmain(String[]args){DoublyLinkedListInsertion<String>list=newDoublyLinkedListInsertion<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. */publicvoidaddAfter(Tafter,Telement){intindex=indexOf(after);if(index>=0){add(index+1,element);}else{addLast(element);}}privatestaticvoidtraverseList(LinkedList<String>list){System.out.println("Traverse List:");for(inti=0;i<list.size();i++){System.out.printf("Element number %d - Element value = '%s'%n",i,list.get(i));}System.out.println();}}
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'
SeeDoubly-Linked_List_(element)#JavaScript
DoublyLinkedList.prototype.insertAfter=function(searchValue,nodeToInsert){if(this._value==searchValue){varafter=this.next();this.next(nodeToInsert);nodeToInsert.prev(this);nodeToInsert.next(after);after.prev(nodeToInsert);}elseif(this.next()==null)thrownewError(0,"value '"+searchValue+"' not found in linked list.")elsethis.next().insertAfter(searchValue,nodeToInsert);}varlist=createDoublyLinkedListFromArray(['A','B']);list.insertAfter('A',newDoublyLinkedList('C',null,null));
mutablestructDLNode{T}value::Tpred::Union{DLNode{T},Nothing}succ::Union{DLNode{T},Nothing}DLNode(v)=new{typeof(v)}(v,nothing,nothing)endfunctioninsertpost(prevnode,node)succ=prevnode.succprevnode.succ=nodenode.pred=prevnodenode.succ=succifsucc!=nothingsucc.pred=nodeendnodeendfunctionprintfromroot(root)print(root.value)whileroot.succ!=nothingroot=root.succprint(" ->$(root.value)")endprintln()endnode1=DLNode(1)printfromroot(node1)node2=DLNode(2)node3=DLNode(3)insertpost(node1,node2)printfromroot(node1)insertpost(node1,node3)printfromroot(node1)
11 -> 21 -> 3 -> 2
// version 1.1.2classNode<T:Number>(vardata:T,varprev:Node<T>?=null,varnext:Node<T>?=null){overridefuntoString():String{valsb=StringBuilder(this.data.toString())varnode=this.nextwhile(node!=null){sb.append(" -> ",node.data.toString())node=node.next}returnsb.toString()}}fun<T:Number>insert(after:Node<T>,new:Node<T>){new.next=after.nextif(after.next!=null)after.next!!.prev=newnew.prev=afterafter.next=new}funmain(args:Array<String>){vala=Node(1)valb=Node(3,a)a.next=bprintln("Before insertion : $a")valc=Node(2)insert(after=a,new=c)println("After insertion : $a")}
Before insertion : 1 -> 3After insertion : 1 -> 2 -> 3
seeDoubly-linked_list/Definition#Lua
ds=CreateDataStructure["DoublyLinkedList"];ds["Append","A"];ds["Append","B"];ds["Append","C"];ds["SwapPart",2,3];ds["Elements"]
{"A", "C", "B"}procinsertAfter[T](l:varList[T],r,n:Node[T])=n.prev=rn.next=r.nextn.next.prev=nr.next=nifr==l.tail:l.tail=n
PROCEDURE(dll:DLList)InsertAfter*(p:Node;o:Box.Object);VARn:Node;BEGINn:=NewNode(o);n.prev:=p;n.next:=p.next;IFp.next#NILTHENp.next.prev:=nEND;p.next:=n;IFp=dll.lastTHENdll.last:=nEND;INC(dll.size)ENDInsertAfter;
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; };}(* val _insert : 'a dlink -> 'a dlink -> unit *)let_insertanchornewlink=newlink.next<-anchor.next;newlink.prev<-Someanchor;beginmatchnewlink.nextwith|None->()|Somenext->next.prev<-Somenewlink;end;anchor.next<-Somenewlink;;(* val insert : 'a dlink option -> 'a -> unit *)letinsertdlv=matchdlwith|(Someanchor)->_insertanchor{data=v;prev=None;next=None}|None->invalid_arg"dlink empty";;
testing in the top level:
#typet=A|B|C;;typet=A|B|C#letdl=dlink_of_list[A;B]ininsertdlC;list_of_dlinkdl;;-:tlist=[A;C;B]
(* val insert : 'a nav_list -> 'a -> 'a nav_list *)letinsert(prev,cur,next)v=(prev,cur,v::next)
testing in the top level:
#typet=A|B|C;;typet=A|B|C#letnl=nav_list_of_list[A;B];;valnl:'alist*t*tlist=([],A,[B])#insertnlC;;-:'alist*t*tlist=([],A,[C;B])
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 ;>test .s[1] (DList) [A, C, B]
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}procedureinsert_link(a,b,c:link_ptr);begina^.next:=c;ifb<>nilthenb^.prev:=c;c^.next:=b;c^.prev:=a;end;
Actually, a more likely real world scenario is 'insert after A'. So...
procedurerealistic_insert_link(a,c:link_ptr);beginifa^.next<>nilthena^.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;
typeNode<T>=autoclassdata:T;prev,next:Node<T>;end;typeMyLinkedList<T>=classfirst,last:Node<T>;procedureAddLast(x:T);beginiffirst=nilthenbeginfirst:=newNode<T>(x,nil,nil);last:=firstendelsebeginvarp:=newNode<T>(x,last,nil);last.next:=p;last:=p;end;end;procedureAddAfter(p:Node<T>;x:T);beginiflast=pthenAddLast(x)elsebeginvarpp:=newNode<T>(x,p,p.next);p.next:=pp;pp.prev.next:=pp;endend;end;
my%node_model=(data=>'something',prev=>undef,next=>undef,);subinsert{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);
See alsoDoubly-linked_list/Traversal.
enumNEXT,PREV,DATAconstantempty_dll={{1,1}}sequencedll=deep_copy(empty_dll)procedureinsert_after(objectdata,integerpos=1)integerprv=dll[pos][PREV]dll=append(dll,{pos,prv,data})ifprv!=0thendll[prv][NEXT]=length(dll)endifdll[pos][PREV]=length(dll)endprocedureinsert_after("ONE")insert_after("TWO")insert_after("THREE")?dll
{{2,4},{3,1,"ONE"},{4,2,"TWO"},{1,3,"THREE"}}This works with the structures described inDoubly-linked list/Definition#PicoLisp andDoubly-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, seeDoubly-linked list/Traversal#PicoLisp.
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. */
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 Binsert_double(A, B) -> _;;;; insert C between A and binsert_double(A, C) -> _;
Structurenode*prev.node*next.nodevalue.c;usecharactertypeforelementsinthisexampleEndStructureProcedureinsertAfter(element.c,*c.node);insertnewnode*nafternode*candsetit's value to elementProtected*n.node=AllocateMemory(SizeOf(node))If*n*n\value=element*n\prev=*cIf*c*n\next=*c\next*c\next=*nEndIfEndIfProcedureReturn*nEndProcedureProceduredisplayList(*dl.node)Protected*n.node=*dlRepeatPrint(Chr(*n\Value)+" ")*n=*n\nextUntil*n=#NullEndProcedureIfOpenConsole()Definedl.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
definsert(anchor,new):new.next=anchor.nextnew.prev=anchoranchor.next.prev=newanchor.next=new
Code is on theDoubly-Linked List page, in functioninsert-between.
(formerly Perl 6)
Using the generic definitions fromDoubly-linked_list/Definition#Raku:
roleDLElem[::T] {hasDLElem[T]$.previsrw;hasDLElem[T]$.nextisrw;hasT$.payload =T;methodpre-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; }methodpost-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; }methoddelete {die"Can't delete a sentinel"unless$!prevand$!next;$!next.prev =$!prev;$!prev.next =$!next;# conveniently returns next element }}roleDLList[::DLE] {hasDLE$.first;hasDLE$.last;submethodBUILD {$!first =DLE.new;$!last =DLE.new;$!first.next =$!last;$!last.prev =$!first; }methodlist { ($!first.next, *.next ...^ !*.next).map: *.payload }methodreverse { ($!last.prev, *.prev ...^ !*.prev).map: *.payload }}classDLElem_StrdoesDLElem[Str] {}classDLList_StrdoesDLList[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
A C B
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. │└─┐ ┌─┘ └────────────────────────────────────────────────────────────────────┘*/callsy'initializing the list.';call@initcallsy'building list: Was it a cat I saw';call@put'Was it a cat I saw'callsy'displaying list size.';say'list size='@size()callsy'forward list';call@showcallsy'backward list';call@show,,-1callsy'showing 4th item';call@show4,1callsy'showing 6th & 6th items';call@show5,2callsy'adding item before item 4: black';call@put'black',4callsy'showing list';call@showcallsy'adding to tail: there, in the ...';call@put'there, in the shadows, stalking its prey (and next meal).'callsy'showing list';call@showcallsy'adding to head: Oy!';call@put'Oy!',0callsy'showing list';call@showexit/*stick a fork in it, we're done.*//*──────────────────────────────────subroutines─────────────────────────*/p:returnword(arg(1),1)sy:say;sayleft('',30)"───"arg(1)'───';return@hasopt:argo;returnpos(o,opt)\==0@size:return$.#@init:$.@='';$.#=0;return0@adjust:$.@=space($.@);$.#=words($.@);return0@parms:argoptif@hasopt('k')thenk=min($.#+1,max(1,p(k1)))if@hasopt('m')thenm=p(m1)if@hasopt('d')thendir=p(dir1)return@show:procedureexpose$.;parseargk,m,dirifdir==-1&k==''thenk=$.#m=p(m$.#);call@parms'kmd'say@get(k,m,dir);return0@get:procedureexpose$.;argk,m,dir,_call@parms'kmd'doj=kformbydirwhilej>0&j<=$.#_=_subword($.@,j,1)end/*j*/returnstrip(_)@put:procedureexpose$.;parseargx,kk=p(k$.#+1)call@parms'k'$.@=subword($.@,1,max(0,k-1))xsubword($.@,k)call@adjustreturn0@del:procedureexpose$.;argk,mcall@parms'km'_=subword($.@,k,k-1)subword($.@,k+m)$.@=_call@adjustreturn
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).
classDListNodedefinsert_after(search_value,new_value)ifsearch_value==valuenew_node=self.class.new(new_value,nil,nil)next_node=self.succself.succ=new_nodenew_node.prev=selfnew_node.succ=next_nodenext_node.prev=new_nodeelsifself.succ.nil?raiseStandardError,"value#{search_value} not found in list"elseself.succ.insert_after(search_value,new_value)endendendhead=DListNode.from_array([:a,:b])head.insert_after(:a,:c)
Doubly-linked list/Definition#Rust defines a method onLinkedList that inserts an element at an arbitrary index. The current task, however, asks us to insert aNode into the list which if you refer toDoubly-linked list/Element definition is not possible directly.
This is where we introduce the Cursor API. The cursor acts as a reference to anyNode that can also cycle around ourLinkedList by pointing to a sentinelNode located logically after the tail and before the head (represented byNone).
#![feature(linked_list_cursors)]pubstructCursor<'a,T:'a>{index:usize,current:Option<NonNull<Node<T>>>,list:&'aLinkedList<T>,}pubstructCursorMut<'a,T:'a>{index:usize,current:Option<NonNull<Node<T>>>,list:&'amutLinkedList<T>,}
We can write a function that moves the cursor up/down the list until it finds the first occurrence of a value, or until it reaches the sentinel if it doesn't find our value. Since for this example we're looking to insert a newNode, thus mutating the list, we'll only define the procedure forCursorMut.
#![feature(linked_list_cursors)]traitCursorExt<T>{fninsert_between(&mutself,l:&T,elt:T,r:&T);fnrinsert_between(&mutself,l:&T,elt:T,r:&T);}impl<T:PartialEq>CursorExt<T>forstd::collections::linked_list::CursorMut<'_,T>{fninsert_between(&mutself,l:&T,elt:T,r:&T){// Pointing at the sentinel, move to headifself.current().is_none(){self.move_next();}letnext=|cursor:&mutSelf|{letleft=cursor.current()?==a;letright=cursor.peek_next()?==b;Some(left&&right)};whileletSome(found)=next(self){iffound{self.insert_after(elt);return;}}}fnrinsert_between(&mutself,l:&T,elt:T,r:&T){// Pointing at the sentinel, move to tailifself.current().is_none(){self.move_prev();}letprev=|cursor:&mutSelf|{letleft=cursor.peek_prev()?==a;letright=cursor.current()?==b;Some(left&&right)};whileletSome(found)=prev(self){iffound{self.insert_before(elt);return;}}}}fnelement_insertion(){usestd::collections::LinkedList;letmutlist=LinkedList::from(['A','B']);list.cursor_front_mut().insert_between(&'A','C',&'B');// list.cursor_back_mut().rinsert_between(&'A', 'C', &'B');assert_eq!(list,['A','C','B'].into());}
typealiasNodePtr<T>=UnsafeMutablePointer<Node<T>>classNode<T>{varvalue:Tfileprivatevarprev:NodePtr<T>?fileprivatevarnext:NodePtr<T>?init(value:T,prev:NodePtr<T>?=nil,next:NodePtr<T>?=nil){self.value=valueself.prev=prevself.next=next}}@discardableResultfuncinsert<T>(_val:T,after:Node<T>?=nil,list:NodePtr<T>?=nil)->NodePtr<T>{letnode=NodePtr<T>.allocate(capacity:1)node.initialize(to:Node(value:val))varn=listwhilen!=nil{ifn?.pointee!==after{n=n?.pointee.nextcontinue}node.pointee.prev=nnode.pointee.next=n?.pointee.nextn?.pointee.next?.pointee.prev=noden?.pointee.next=nodebreak}returnnode}// [1]letlist=insert(1)// [1, 2]insert(2,after:list.pointee,list:list)// [1, 3, 2]insert(3,after:list.pointee,list:list)
SeeDoubly-Linked List (element) for caveats about linked lists in Tcl.
oo::defineList{methodinsertBefore{elem}{$elemnext[self]$elemprevious$previf{$prevne""}{$prevnext$elem}setprev$elem}methodinsertAfter{elem}{$elemprevious[self]$elemnext$nextif{$nextne""}{$nextprevious$elem}setnext$elem}}
Demonstration:
setB[Listnew3]setA[Listnew1$B]setC[Listnew2]$AinsertAfter$Cputs[format"{%d,%d,%d}"[$Avalue][[$Anext]value][[[$Anext]next]value]]
PublicSubInsert(ByValaAsNode(OfT),ByValbAsNode(OfT),ByValcAsT)DimnodeAsNewNode(OfT)(value)a.Next=nodenode.Previous=ab.Previous=nodenode.Next=bEndSub
import"./llist"forDLinkedListvardll=DLinkedList.new(["A","B"])dll.insertAfter("A","C")System.print(dll)
[A <-> C <-> B]
def \Node\ Prev, Data, Next; \Element (Node) definition proc Insert(NewNode, Node); \Insert NewNode after Node int NewNode, Node, NextNode; [NextNode:= Node(Next); NextNode(Prev):= NewNode; NewNode(Next):= NextNode; NewNode(Prev):= Node; Node(Next):= NewNode; ];int Node, A(3), B(3), C(3);[A(Next):= B;A(Data):= ^a;B(Prev):= A;B(Data):= ^b;B(Next):= 0;C(Data):= ^c;Insert(C, A);Node:= A;while Node # 0 do [ChOut(0, Node(Data)); Node:= Node(Next); ];]
acb
// Rosetta Code problem: http://rosettacode.org/wiki/Doubly-linked_list/Element_insertion & removal & traverse// by Galileo, 02/2022FIL = 1 : DATO = 2 : LPREV = 3 : LNEXT = 4countNodes = 0 : Nodes = 10dim list(Nodes, 4)list(0, LNEXT) = 1sub searchNode(node) local i, Node for i = 0 to node-1 Node = list(Node, LNEXT) next return Nodeend subsub 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 ifend subsub 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 - 1end subsub printNode(node) local Node Node = searchNode(node) print list(Node, DATO); printend subsub traverseList() local i for i = 1 to countNodes printNode(i) nextend subinsertNode(1, 1000)insertNode(2, 2000)insertNode(2, 3000)traverseList()removeNode(2)printtraverseList()
10003000200010002000---Program done, press RETURN---
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);a b c