Doubly-linked list/Element removal: Difference between revisions
(Ada version) |
m (→{{header|Phix}}: added syntax colouring the hard way) |
||
Line 270: | Line 270: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
Extended copy of [[Doubly-linked_list/Traversal#Phix]] |
Extended copy of [[Doubly-linked_list/Traversal#Phix]] |
||
<lang Phix> |
<!--<lang Phix>(phixonline)--> |
||
<span style="color: #008080;">enum</span> <span style="color: #000000;">NEXT</span><span style="color: #0000FF;">,</span><span style="color: #000000;">PREV</span><span style="color: #0000FF;">,</span><span style="color: #000000;">DATA</span> |
|||
constant empty_dll = {{1,1}} |
|||
<span style="color: #008080;">constant</span> <span style="color: #000000;">empty_dll</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}}</span> |
|||
sequence dll = empty_dll |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">dll</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">empty_dll</span><span style="color: #0000FF;">)</span> |
|||
procedure remove_item(integer pos) |
|||
<span style="color: #008080;">procedure</span> <span style="color: #000000;">remove_item</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">pos</span><span style="color: #0000FF;">)</span> |
|||
if pos<=1 or pos>length(dll) then ?9/0 end if -- (sanity check) |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">pos</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">1</span> <span style="color: #008080;">or</span> <span style="color: #000000;">pos</span><span style="color: #0000FF;">></span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dll</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #0000FF;">?</span><span style="color: #000000;">9</span><span style="color: #0000FF;">/</span><span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #000080;font-style:italic;">-- (sanity check)</span> |
|||
integer {next,prev} = dll[pos] |
|||
<span style="color: #004080;">integer</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">next</span><span style="color: #0000FF;">,</span><span style="color: #000000;">prev</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pos</span><span style="color: #0000FF;">]</span> |
|||
dll[prev][NEXT] = next |
|||
<span style="color: #000000;">dll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">prev</span><span style="color: #0000FF;">][</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">next</span> |
|||
dll[next][PREV] = prev |
|||
<span style="color: #000000;">dll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">next</span><span style="color: #0000FF;">][</span><span style="color: #000000;">PREV</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">prev</span> |
|||
if pos<length(dll) then |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">pos</span><span style="color: #0000FF;"><</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dll</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> |
|||
dll[pos] = dll[$] |
|||
<span style="color: #000000;">dll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pos</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dll</span><span style="color: #0000FF;">[$]</span> |
|||
{next,prev} = dll[pos] |
|||
<span style="color: #0000FF;">{</span><span style="color: #000000;">next</span><span style="color: #0000FF;">,</span><span style="color: #000000;">prev</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pos</span><span style="color: #0000FF;">]</span> |
|||
dll[prev][NEXT] = pos |
|||
<span style="color: #000000;">dll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">prev</span><span style="color: #0000FF;">][</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">pos</span> |
|||
dll[next][PREV] = pos |
|||
<span style="color: #000000;">dll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">next</span><span style="color: #0000FF;">][</span><span style="color: #000000;">PREV</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">pos</span> |
|||
end if |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
dll = dll[1..-2] |
|||
<span style="color: #000000;">dll</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> |
|||
end procedure |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span> |
|||
procedure insert_after(object data, integer pos=1) |
|||
<span style="color: #008080;">procedure</span> <span style="color: #000000;">insert_after</span><span style="color: #0000FF;">(</span><span style="color: #004080;">object</span> <span style="color: #000000;">data</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">pos</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> |
|||
integer prv = dll[pos][PREV] |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">prv</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pos</span><span style="color: #0000FF;">][</span><span style="color: #000000;">PREV</span><span style="color: #0000FF;">]</span> |
|||
dll = append(dll,{pos,prv,data}) |
|||
<span style="color: #000000;">dll</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dll</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">pos</span><span style="color: #0000FF;">,</span><span style="color: #000000;">prv</span><span style="color: #0000FF;">,</span><span style="color: #000000;">data</span><span style="color: #0000FF;">})</span> |
|||
if prv!=0 then |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">prv</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> |
|||
dll[prv][NEXT] = length(dll) |
|||
<span style="color: #000000;">dll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">prv</span><span style="color: #0000FF;">][</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dll</span><span style="color: #0000FF;">)</span> |
|||
end if |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
dll[pos][PREV] = length(dll) |
|||
<span style="color: #000000;">dll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pos</span><span style="color: #0000FF;">][</span><span style="color: #000000;">PREV</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dll</span><span style="color: #0000FF;">)</span> |
|||
end procedure |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span> |
|||
insert_after("ONE") |
|||
<span style="color: #000000;">insert_after</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"ONE"</span><span style="color: #0000FF;">)</span> |
|||
insert_after("TWO") |
|||
<span style="color: #000000;">insert_after</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"TWO"</span><span style="color: #0000FF;">)</span> |
|||
insert_after("THREE") |
|||
<span style="color: #000000;">insert_after</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"THREE"</span><span style="color: #0000FF;">)</span> |
|||
?dll |
|||
<span style="color: #0000FF;">?</span><span style="color: #000000;">dll</span> |
|||
procedure show(integer d) |
|||
<span style="color: #008080;">procedure</span> <span style="color: #000000;">show</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">)</span> |
|||
integer idx = dll[1][d] |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">idx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">d</span><span style="color: #0000FF;">]</span> |
|||
while idx!=1 do |
|||
<span style="color: #008080;">while</span> <span style="color: #000000;">idx</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span> |
|||
?dll[idx][DATA] |
|||
<span style="color: #0000FF;">?</span><span style="color: #000000;">dll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">][</span><span style="color: #000000;">DATA</span><span style="color: #0000FF;">]</span> |
|||
idx = dll[idx][d] |
|||
<span style="color: #000000;">idx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">][</span><span style="color: #000000;">d</span><span style="color: #0000FF;">]</span> |
|||
end while |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
end procedure |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span> |
|||
show(NEXT) |
|||
<span style="color: #000000;">show</span><span style="color: #0000FF;">(</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">)</span> |
|||
?"==" |
|||
<span style="color: #0000FF;">?</span><span style="color: #008000;">"=="</span> |
|||
show(PREV) |
|||
<span style="color: #000000;">show</span><span style="color: #0000FF;">(</span><span style="color: #000000;">PREV</span><span style="color: #0000FF;">)</span> |
|||
while length(dll)>1 do |
|||
<span style="color: #008080;">while</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dll</span><span style="color: #0000FF;">)></span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span> |
|||
?"== removing one item ==" |
|||
<span style="color: #0000FF;">?</span><span style="color: #008000;">"== removing one item =="</span> |
|||
remove_item(rand(length(dll)-1)+1) |
|||
<span style="color: #000000;">remove_item</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">rand</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dll</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> |
|||
show(NEXT) |
|||
<span style="color: #000000;">show</span><span style="color: #0000FF;">(</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">)</span> |
|||
?"==" |
|||
<span style="color: #0000FF;">?</span><span style="color: #008000;">"=="</span> |
|||
show(PREV) |
|||
<span style="color: #000000;">show</span><span style="color: #0000FF;">(</span><span style="color: #000000;">PREV</span><span style="color: #0000FF;">)</span> |
|||
end while</lang> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
<!--</lang>--> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
Revision as of 14:11, 25 May 2021
- 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
<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
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
<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]