Doubly-linked list/Element removal

Doubly-linked list/Element removal is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Task

Define a method to remove an element from a doubly-linked list and demonstrate its use.

You may wish to use the list element defined in Doubly-Linked List (element) for the purposes of this task.

ALGOL W

Uses the element type and insertion method as in the Doubly-Linked List (traversal) task. <lang algolw>begin

   % 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 ;
   % removes an element e of a doubly linked list                            %
   procedure removeDListIElement( reference(DListIElement) value e );
       if e not = null then begin
           % have an element to remove                                       %
           reference(DListIElement) ePrev, eNext;
           ePrev            := prev(e);
           eNext            := next(e);
           if ePrev not = null then next(ePrev) := eNext;
           if eNext not = null then prev(eNext) := ePrev
       end removeDListIElement ;

   begin
       reference(DListIElement) head, e, toRemove, last;
       head     := null;
       head     := insertIntoDListIBefore( head,        1701 );
       head     := insertIntoDListIBefore( head,        9000 );
       e        := insertIntoDListIBefore( next(head), 90210 );
       toRemove := insertIntoDListIBefore( next(e),     4077 );
       e        := head;
       last     := null;
       write( "Before: Forward:" );
       while e not = null do begin
           write( i_w := 1, s_w := 0, " ", iValue(e) );
           last := e;
           e    := next(e)
       end while_e_ne_null ;
       write( "Before: Backward:" );
       e := last;
       while e not = null do begin
           write( i_w := 1, s_w := 0, " ", iValue(e) );
           last := e;
           e    := prev(e)
       end while_e_ne_null ;
       e        := head;
       last     := null;

       % remove an element                                                   %
       removeDListIElement( toRemove );

       write( "After: Forward:" );
       while e not = null do begin
           write( i_w := 1, s_w := 0, " ", iValue(e) );
           last := e;
           e    := next(e)
       end while_e_ne_null ;
       write( "After: Backward:" );
       e := last;
       while e not = null do begin
           write( i_w := 1, s_w := 0, " ", iValue(e) );
           last := e;
           e    := prev(e)
       end while_e_ne_null
   end

end.</lang>

Output:

Before: Forward:
 9000
 90210
 4077
 1701
Before: Backward:
 1701
 4077
 90210
 9000
After: Forward:
 9000
 90210
 1701
After: Backward:
 1701
 90210
 9000

Julia

Uses code from Doubly-Linked List (traversal) <lang julia>mutable struct DLNode{T}

   value::T
   pred::Union{DLNode{T}, Nothing}
   succ::Union{DLNode{T}, Nothing}
   DLNode(v) = new{typeof(v)}(v, nothing, nothing)

end

function insertpost(prevnode, node)

   succ = prevnode.succ
   prevnode.succ = node
   node.pred = prevnode
   node.succ = succ
   if succ != nothing
       succ.pred =  node
   end
   return node

end

function delete(node)

   succ = node.succ
   pred = node.pred
   succ != nothing && (succ.pred = pred)
   pred != nothing && (pred.succ = succ)
   return node

end

first(nd) = (while nd.pred != nothing nd = nd.prev end; nd) last(nd) = (while nd.succ != nothing nd = nd.succ end; nd)

function atindex(nd, idx)

   nd = first(nd)
   while idx > 1 && nd != nothing
       nd = nd.succ
       idx -= 1
   end
   return nd

end

function printconnected(nd; fromtail = false)

   if fromtail
       nd = last(nd)
       print(nd.value)
       while nd.pred != nothing
           nd = nd.pred
           print(" -> $(nd.value)")
       end
   else
       nd = first(nd)
       print(nd.value)
       while nd.succ != nothing
           nd = nd.succ
           print(" -> $(nd.value)")
       end
   end
   println()

end

node1 = DLNode(1) node2 = DLNode(2) node3 = DLNode(3) node4 = DLNode(4)

insertpost(node1, node2) insertpost(node2, node3) insertpost(node3, node4)

print("From beginning to end: "); printconnected(node1) delete(atindex(node1, 3)) println("Deleting third node yields: "); printconnected(node1) delete(node2) println("Then deleting node2 yields: "); printconnected(node1)

</lang>

Output:

From beginning to end: 1 -> 2 -> 3 -> 4
Deleting third node yields:
1 -> 2 -> 4
Then deleting node2 yields:
1 -> 4