I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

Doubly-linked list/Element removal

From Rosetta Code
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.

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]