Doubly-Linked List (element insertion)

From Rosetta Code

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.

Contents 1 Ada 2 C 3 Fortran 4 Pascal 5 Pop11 6 Python 7 Ruby

[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] 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] 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] 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] 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] Python

def insert(anchor, new):
    new.next = anchor.next
    new.prev = anchor
    anchor.next.prev = new
    anchor.next = new

[edit] 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)