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.

Action!

The user must type in the monitor the following command after compilation and before running the program!

SET EndProg=*

Library: Action! Tool Kit

<lang Action!>CARD EndProg ;required for ALLOCATE.ACT

INCLUDE "D2:ALLOCATE.ACT" ;from the Action! Tool Kit. You must type 'SET EndProg=*' from the monitor after compiling, but before running this program!

DEFINE PTR="CARD" DEFINE NODE_SIZE="6" TYPE ListNode=[PTR data,prv,nxt]

ListNode POINTER listBegin,listEnd

PROC Append(CHAR ARRAY v)

 ListNode POINTER n

 n=Alloc(NODE_SIZE)
 n.data=v
 n.prv=listEnd
 n.nxt=0
 IF listEnd THEN
   listEnd.nxt=n
 ELSE
   listBegin=n
 FI
 listEnd=n

RETURN

PROC Remove(ListNode POINTER n)

 ListNode POINTER prev,next
 
 IF n=0 THEN Break() FI

 prev=n.prv
 next=n.nxt
 
 IF prev THEN
   prev.nxt=next
 ELSE
   listBegin=next
 FI
 IF next THEN
   next.prv=prev
 ELSE
   listEnd=prev
 FI

 Free(n,NODE_SIZE)

RETURN

PROC PrintList()

 ListNode POINTER n

 n=listBegin
 Print("(")
 WHILE n
 DO
   Print(n.data)
   IF n.nxt THEN
     Print(", ")
   FI
   n=n.nxt
 OD
 PrintE(")") PutE()

RETURN

PROC TestRemove(ListNode POINTER n)

 PrintF("Remove ""%S"":%E",n.data)
 Remove(n)
 PrintList()

RETURN

PROC Main()

 Put(125) PutE() ;clear screen
 
 AllocInit(0)
 listBegin=0
 listEnd=0

 Append("First")
 Append("Second")
 Append("Third")
 Append("Fourth")
 Append("Fifth")
 PrintList()

 TestRemove(listBegin.nxt)
 TestRemove(listEnd.prv)
 TestRemove(listBegin)
 TestRemove(listEnd)
 TestRemove(listBegin)

RETURN</lang>

Output:

Screenshot from Atari 8-bit computer

(First, Second, Third, Fourth, Fifth)

Remove "Second":
(First, Third, Fourth, Fifth)

Remove "Fourth":
(First, Third, Fifth)

Remove "First":
(Third, Fifth)

Remove "Fifth":
(Third)

Remove "Third":
()

Ada

<lang Ada>with Ada.Containers.Indefinite_Doubly_Linked_Lists; with Ada.Text_Io;

procedure Element_Remove is

  package String_Lists is
    new Ada.Containers.Indefinite_Doubly_Linked_Lists
      (Element_Type => String);
  use String_Lists;

  procedure Print_List (List : String_Lists.List) is
     use Ada.Text_Io;
  begin
     for Element of List loop
        Put (Element); Put ("  ");
     end loop;
     New_Line;
  end Print_List;

  List : String_Lists.List;
  Cur  : String_Lists.Cursor;

begin

  List.Append ("cat");
  List.Append ("dog");
  List.Append ("hen");
  List.Append ("horse");

  Print_List (List);

  Cur := Find (List, "hen");
  List.Delete (Cur);

  Print_List (List);

end Element_Remove;</lang>

Output:

cat  dog  hen  horse
cat  dog  horse

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

Go

Using the doubly-linked list from the container/list package and the Wren example: <lang go>package main

import (

   "container/list"
   "fmt"

)

func printDll(s string, dll *list.List) {

   fmt.Printf("%s: { ", s)
   for e := dll.Front(); e != nil; e = e.Next() {
       fmt.Printf("%v ", e.Value)
   }
   fmt.Println("}")

}

func main() {

   dll := list.New()
   e1 := dll.PushBack("dog")
   e2 := dll.PushBack("cat")
   dll.PushBack("bear")
   printDll("Before removals", dll)
   dll.Remove(e2) // remove "cat"
   printDll("After removal 1", dll)
   dll.Remove(e1) // remove "dog"
   printDll("After removal 2", dll)

}</lang>

Output:

Before removals: { dog cat bear }
After removal 1: { dog bear }
After removal 2: { bear }

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

Nim

This is a simplified version of code from Doubly-Linked List (traversal) <lang Nim>type

 DoublyLinkedList[T] = object
   head, tail: Node[T]

 Node[T] = ref TNode[T]

 TNode[T] = object
   next, prev: Node[T]
   data: T

proc initDoublyLinkedList[T](): DoublyLinkedList[T] = discard

proc newNode[T](data: T): Node[T] =

 new(result)
 result.data = data

proc append[T](list: var DoublyLinkedList[T]; node: Node[T]) =

 node.next = nil
 node.prev = list.tail
 if not list.tail.isNil: list.tail.next = node
 list.tail = node
 if list.head.isNil: list.head = node

proc remove[T](list: var DoublyLinkedList; node: Node[T]) =

 if node == list.tail: list.tail = node.prev
 if node == list.head: list.head = node.next
 if not node.next.isNil: node.next.prev = node.prev
 if not node.prev.isNil: node.prev.next = node.next
 node.prev = nil
 node.next = nil

proc `$`[T](list: DoublyLinkedList[T]): string =

 var node = list.head
 while not node.isNil:
   if result.len > 0: result.add(" -> ")
   result.add $node.data
   node = node.next

var l = initDoublyLinkedList[int]() let a = newNode(12) let b = newNode(13) let c = newNode(14) let d = newNode(15) l.append a l.append b l.append c l.append d echo l l.remove b echo l l.remove a echo l l.remove d echo l l.remove c echo l</lang>

Output:

12 -> 13 -> 14 -> 15
12 -> 14 -> 15
14 -> 15
14

Phix

Extended copy of Doubly-linked_list/Traversal#Phix

enum NEXT,PREV,DATA
constant empty_dll = {{1,1}}
sequence dll = deep_copy(empty_dll)
 
procedure remove_item(integer pos)
    if pos<=1 or pos>length(dll) then ?9/0 end if -- (sanity check)
    integer {next,prev} = dll[pos]
    dll[prev][NEXT] = next
    dll[next][PREV] = prev
    if pos<length(dll) then
        dll[pos] = dll[$]
        {next,prev} = dll[pos]
        dll[prev][NEXT] = pos
        dll[next][PREV] = pos
    end if
    dll = dll[1..-2]
end procedure
 
procedure insert_after(object data, integer pos=1)
    integer prv = dll[pos][PREV]
    dll = append(dll,{pos,prv,data})
    if prv!=0 then
        dll[prv][NEXT] = length(dll)
    end if
    dll[pos][PREV] = length(dll)
end procedure
 
insert_after("ONE")
insert_after("TWO")
insert_after("THREE")
 
?dll
 
procedure show(integer d)
integer idx = dll[1][d]
    while idx!=1 do
        ?dll[idx][DATA]
        idx = dll[idx][d]
    end while
end procedure
show(NEXT)
?"=="
show(PREV)
while length(dll)>1 do
    ?"== removing one item =="
    remove_item(rand(length(dll)-1)+1)
    show(NEXT)
    ?"=="
    show(PREV)
end while

Output:

{{2,4},{3,1,"ONE"},{4,2,"TWO"},{1,3,"THREE"}}
"ONE"
"TWO"
"THREE"
"=="
"THREE"
"TWO"
"ONE"
"== removing one item =="
"ONE"
"THREE"
"=="
"THREE"
"ONE"
"== removing one item =="
"THREE"
"=="
"THREE"
"== removing one item =="
"=="

Raku

Already implemented and demonstrated as part of Doubly-linked_list/Definition#Raku. Not going to duplicate the entire entry from there to here.

Wren

Library: Wren-llist

<lang ecmascript>import "/llist" for DLinkedList

var dll = DLinkedList.new(["dog", "cat", "bear"]) System.print("Before removals: %(dll)") dll.remove("cat") // remove by element System.print("After removal 1: %(dll)") dll.removeAt(0) // remove by index System.print("After removal 2: %(dll)")</lang>

Output:

Before removals: [dog <-> cat <-> bear]
After removal 1: [dog <-> bear]
After removal 2: [bear]