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.
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
Phix
Extended copy of Doubly-linked_list/Traversal#Phix <lang Phix>enum NEXT,PREV,DATA constant empty_dll = Template: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</lang>
- 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.