Rosetta Code

Doubly-linked list/Element removal: Difference between revisions

Page Discussion

Doubly-linked list/Element removal (view source)

Revision as of 18:22, 31 March 2024

19,290 bytes added ,  1 month ago
Added FreeBASIC
(Added FreeBASIC)
(11 intermediate revisions by 6 users not shown)
Line 7:
You may wish to use the list element defined in [[Doubly-Linked List (element)]] for the purposes of this task.
 
=={{header|Action!}}==
The user must type in the monitor the following command after compilation and before running the program!<pre>SET EndProg=*</pre>
{{libheader|Action! Tool Kit}}
<syntaxhighlight lang="action!">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</syntaxhighlight>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Doubly-linked_list_element_removal.png Screenshot from Atari 8-bit computer]
<pre>
(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":
()
</pre>
 
=={{header|Ada}}==
<syntaxhighlight 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;</syntaxhighlight>
{{out}}
<pre>cat dog hen horse
cat dog horse</pre>
 
=={{header|ALGOL W}}==
Uses the element type and insertion method as in the [[Doubly-Linked List (traversal)]] task.
<langsyntaxhighlight lang="algolw">begin
% record type to hold an element of a doubly linked list of integers %
record DListIElement ( reference(DListIElement) prev
Line 87 ⟶ 240:
end while_e_ne_null
end
end.</langsyntaxhighlight>
{{out}}
<pre>
Line 108 ⟶ 261:
90210
9000
</pre>
 
=={{header|FreeBASIC}}==
<syntaxhighlight lang="vbnet">Type Nodo
valor As String
sgte As Nodo Ptr
End Type
 
Sub MuestraLista(s As String, Byref cabeza As Nodo Ptr)
Dim As Nodo Ptr e = cabeza
Print s & ": { ";
While e <> 0
Print e->valor; " ";
e = e->sgte
Wend
Print "}"
End Sub
 
Sub Eliminar(Byref cabeza As Nodo Ptr, Byref objetivo As Nodo Ptr)
Dim As Nodo Ptr prev = 0
Dim As Nodo Ptr actual = cabeza
While actual <> objetivo And actual <> 0
prev = actual
actual = actual->sgte
Wend
If actual = objetivo Then
If prev = 0 Then ' cabeza node
cabeza = cabeza->sgte
Else
prev->sgte = actual->sgte
End If
Deallocate(actual)
End If
End Sub
 
Dim As Nodo Ptr dll = 0
Dim As Nodo Ptr e1 = Callocate(1, Sizeof(Nodo))
e1->valor = "dog"
e1->sgte = dll
dll = e1
 
Dim As Nodo Ptr e2 = Callocate(1, Sizeof(Nodo))
e2->valor = "cat"
e2->sgte = dll
dll = e2
 
Dim As Nodo Ptr e3 = Callocate(1, Sizeof(Nodo))
e3->valor = "bear"
e3->sgte = dll
dll = e3
 
MuestraLista("Before removals", dll)
Eliminar(dll, e2) ' remove "cat"
MuestraLista("After removal 1", dll)
Eliminar(dll, e1) ' remove "dog"
MuestraLista("After removal 2", dll)
 
Sleep</syntaxhighlight>
{{out}}
<pre>Before removals: { bear cat dog }
After removal 1: { bear dog }
After removal 2: { bear }</pre>
 
=={{header|Go}}==
Using the doubly-linked list from the container/list package and the Wren example:
<syntaxhighlight 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)
}</syntaxhighlight>
 
{{out}}
<pre>
Before removals: { dog cat bear }
After removal 1: { dog bear }
After removal 2: { bear }
</pre>
 
=={{header|Julia}}==
Uses code from [[Doubly-Linked List (traversal)]]
<langsyntaxhighlight lang="julia">mutable struct DLNode{T}
value::T
pred::Union{DLNode{T}, Nothing}
Line 183 ⟶ 433:
delete(node2)
println("Then deleting node2 yields: "); printconnected(node1)
</langsyntaxhighlight>{{out}}
<pre>
From beginning to end: 1 -> 2 -> 3 -> 4
Line 190 ⟶ 440:
Then deleting node2 yields:
1 -> 4
</pre>
 
=={{header|Nim}}==
This is a simplified version of code from [[Doubly-Linked List (traversal)]]
<syntaxhighlight lang="nim">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</syntaxhighlight>
 
{{out}}
<pre>12 -> 13 -> 14 -> 15
12 -> 14 -> 15
14 -> 15
14
 
</pre>
 
=={{header|Phix}}==
Extended copy of [[Doubly-linked_list/Traversal#Phix]]
<!--<syntaxhighlight 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>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<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>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<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>
<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>
<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>
<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>
<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>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</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> <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;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">insert_after</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"ONE"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">insert_after</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"TWO"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">insert_after</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"THREE"</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">dll</span>
<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>
<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>
<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>
<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>
<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>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<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>
<span style="color: #000000;">show</span><span style="color: #0000FF;">(</span><span style="color: #000000;">PREV</span><span style="color: #0000FF;">)</span>
<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>
<span style="color: #0000FF;">?</span><span style="color: #008000;">"== removing one item =="</span>
<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>
<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>
<span style="color: #000000;">show</span><span style="color: #0000FF;">(</span><span style="color: #000000;">PREV</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
{{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 =="
"=="
</pre>
 
=={{header|Raku}}==
Already implemented and demonstrated as part of [[Doubly-linked_list/Definition#Raku]]. Not going to duplicate the entire entry from there to here.
 
=={{header|Wren}}==
{{libheader|Wren-llist}}
<syntaxhighlight lang="wren">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)")</syntaxhighlight>
 
{{out}}
<pre>
Before removals: [dog <-> cat <-> bear]
After removal 1: [dog <-> bear]
After removal 2: [bear]
</pre>
Jjuanhdez
2,123

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/302542...363099"