Doubly-linked list/Element removal

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

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

SET EndProg=*

Library: Action! Tool Kit

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

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

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;

Output:

cat  dog  hen  horse
cat  dog  horse

ALGOL W[edit]

Uses the element type and insertion method as in the Doubly-Linked List (traversal) task.

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.

Output:

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

Go[edit]

Using the doubly-linked list from the container/list package and the Wren example:

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

Output:

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

Julia[edit]

Uses code from Doubly-Linked List (traversal)

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)

Output:

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

Nim[edit]

This is a simplified version of code from Doubly-Linked List (traversal)

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

Output:

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

Phix[edit]

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

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

Wren[edit]

Library: Wren-llist

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

Output:

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