Doubly-linked list/Element insertion: Difference between revisions
Line 166: | Line 166: | ||
=={{header|OCaml}}== |
=={{header|OCaml}}== |
||
===with dlink=== |
|||
<ocaml>(* val _insert : 'a dlink -> 'a dlink -> unit *) |
<ocaml>(* val _insert : 'a dlink -> 'a dlink -> unit *) |
||
let _insert anchor newlink = |
let _insert anchor newlink = |
||
Line 194: | Line 194: | ||
- : t list = [A; C; B] |
- : t list = [A; C; B] |
||
</ocaml> |
</ocaml> |
||
===with nav_list=== |
|||
<ocaml>(* val insert : 'a nav_list -> 'a -> 'a nav_list *) |
|||
let insert (prev, cur, next) v = (prev, cur, v::next)</ocaml> |
|||
testing in the top level: |
|||
<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])</ocaml> |
|||
=={{header|Pascal}}== |
=={{header|Pascal}}== |
Revision as of 18:26, 18 November 2008
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.
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;
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}.
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.
OCaml
with dlink
<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";;</ocaml>
testing in the top level:
<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] </ocaml>
<ocaml>(* val insert : 'a nav_list -> 'a -> 'a nav_list *) let insert (prev, cur, next) v = (prev, cur, v::next)</ocaml>
testing in the top level: <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])</ocaml>
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;
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) -> _;
Python
def insert(anchor, new): new.next = anchor.next new.prev = anchor anchor.next.prev = new anchor.next = new
Ruby
class ListNode def insertAt(ind,newEl) # where ind > 0 if ind==1 ListNode.new(newEl,self,nxt) elsif ind > 1 && nxt nxt.insertAt(ind-1,newEl) else fail "cannot insert at index #{ind}" end end end
a=ListNode.new(:a) b=ListNode.new(:b,a)
a.insertAt(1,:c)