Doubly-linked list/Element insertion

Doubly-linked list/Element insertion
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: <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>

AutoHotkey

<lang AutoHotkey>a_prev = 0 a = 1 a_next = b b_prev = a b = 2 b_next = 0 c = 4

insert_between("c", "a", "b") ListVars return

insert_between(new, prev, next) {

 local temp
 %prev%_next := new
 %new%_prev := prev
 %new%_next := next
 %next%_prev := new

}</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>

Common Lisp

Code is on the Doubly-Linked List page, in function insert-between.

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>

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>

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>

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

1. let dl = dlink_of_list [A; B] in

 insert dl C;
 list_of_dlink dl ;;

- : t list = [A; C; B]</lang>

with nav_list

<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

1. let nl = nav_list_of_list [A; B] ;;

val nl : 'a list * t * t list = ([], A, [B])

1. insert nl C ;;

- : 'a list * t * t list = ([], A, [C; B])</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>

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>

Python

<lang python>def insert(anchor, new):

   new.next = anchor.next
   new.prev = anchor
   anchor.next.prev = new
   anchor.next = new</lang>

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.

Works with: Tcl version 8.6

<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>