Doubly-linked list/Element insertion

From Rosetta Code

(Redirected from Doubly-Linked List (element insertion))

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.

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

see Doubly-linked list/AutoHotkey

[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] C#

The function handles creation of nodes in addition to inserting them.

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

Example use:

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);
}

[edit] Common Lisp

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

[edit] E

def insert(after, value) {
    def newNode := makeElement(value, after, after.getNext())
    after.getNext().setPrev(newNode)
    after.setNext(newNode)
}

insert(A_node, 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:

[edit] Haskell

Using the algebraic data type and update functions from Doubly-Linked_List_(element)#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

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

[edit] JavaScript

See Doubly-Linked_List_(element)#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));

[edit] OCaml

[edit] with dlink

(* 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";;

testing in the top level:

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

[edit] with nav_list

(* val insert : 'a nav_list -> 'a -> 'a nav_list *)
let insert (prev, cur, next) v = (prev, cur, v::next)

testing in the top level:

# 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])

[edit] Oz

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}

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

[edit] 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.         */

[edit] PicoLisp

This works with the structures described in Doubly-linked list/Definition#PicoLisp and Doubly-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, see Doubly-linked list/Traversal#PicoLisp.

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

Sample output:

A C B

[edit] Python

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

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

[edit] Tcl

See Doubly-Linked List (element) for caveats about linked lists in Tcl.
Works with: Tcl version 8.6

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

Demonstration:

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

[edit] Visual Basic .NET

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