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.


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

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

Phix[edit]

Extended copy of Doubly-linked_list/Traversal#Phix

enum NEXT,PREV,DATA
constant empty_dll = {{1,1}}
sequence dll = 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.