Doubly-linked list/Element removal: Difference between revisions
(Added solution for Action!) |
No edit summary |
||
(4 intermediate revisions by 4 users not shown) | |||
Line 10: | Line 10: | ||
The user must type in the monitor the following command after compilation and before running the program!<pre>SET EndProg=*</pre> |
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}} |
{{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! |
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" |
DEFINE NODE_SIZE="6" |
||
TYPE ListNode=[ |
TYPE ListNode=[PTR data,prv,nxt] |
||
ListNode POINTER listBegin,listEnd |
ListNode POINTER listBegin,listEnd |
||
Line 97: | Line 98: | ||
TestRemove(listEnd) |
TestRemove(listEnd) |
||
TestRemove(listBegin) |
TestRemove(listBegin) |
||
RETURN</ |
RETURN</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Doubly-linked_list_element_removal.png Screenshot from Atari 8-bit computer] |
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Doubly-linked_list_element_removal.png Screenshot from Atari 8-bit computer] |
||
Line 120: | Line 121: | ||
=={{header|Ada}}== |
=={{header|Ada}}== |
||
< |
<syntaxhighlight lang="ada">with Ada.Containers.Indefinite_Doubly_Linked_Lists; |
||
with Ada.Text_Io; |
with Ada.Text_Io; |
||
Line 155: | Line 156: | ||
Print_List (List); |
Print_List (List); |
||
end Element_Remove;</ |
end Element_Remove;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>cat dog hen horse |
<pre>cat dog hen horse |
||
Line 162: | Line 163: | ||
=={{header|ALGOL W}}== |
=={{header|ALGOL W}}== |
||
Uses the element type and insertion method as in the [[Doubly-Linked List (traversal)]] task. |
Uses the element type and insertion method as in the [[Doubly-Linked List (traversal)]] task. |
||
< |
<syntaxhighlight lang="algolw">begin |
||
% record type to hold an element of a doubly linked list of integers % |
% record type to hold an element of a doubly linked list of integers % |
||
record DListIElement ( reference(DListIElement) prev |
record DListIElement ( reference(DListIElement) prev |
||
Line 239: | Line 240: | ||
end while_e_ne_null |
end while_e_ne_null |
||
end |
end |
||
end.</ |
end.</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 261: | Line 262: | ||
9000 |
9000 |
||
</pre> |
</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}}== |
=={{header|Go}}== |
||
Using the doubly-linked list from the container/list package and the Wren example: |
Using the doubly-linked list from the container/list package and the Wren example: |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 289: | Line 351: | ||
dll.Remove(e1) // remove "dog" |
dll.Remove(e1) // remove "dog" |
||
printDll("After removal 2", dll) |
printDll("After removal 2", dll) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 300: | Line 362: | ||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
Uses code from [[Doubly-Linked List (traversal)]] |
Uses code from [[Doubly-Linked List (traversal)]] |
||
< |
<syntaxhighlight lang="julia">mutable struct DLNode{T} |
||
value::T |
value::T |
||
pred::Union{DLNode{T}, Nothing} |
pred::Union{DLNode{T}, Nothing} |
||
Line 371: | Line 433: | ||
delete(node2) |
delete(node2) |
||
println("Then deleting node2 yields: "); printconnected(node1) |
println("Then deleting node2 yields: "); printconnected(node1) |
||
</ |
</syntaxhighlight>{{out}} |
||
<pre> |
<pre> |
||
From beginning to end: 1 -> 2 -> 3 -> 4 |
From beginning to end: 1 -> 2 -> 3 -> 4 |
||
Line 382: | Line 444: | ||
=={{header|Nim}}== |
=={{header|Nim}}== |
||
This is a simplified version of code from [[Doubly-Linked List (traversal)]] |
This is a simplified version of code from [[Doubly-Linked List (traversal)]] |
||
< |
<syntaxhighlight lang="nim">type |
||
DoublyLinkedList[T] = object |
DoublyLinkedList[T] = object |
||
Line 438: | Line 500: | ||
echo l |
echo l |
||
l.remove c |
l.remove c |
||
echo l</ |
echo l</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 446: | Line 508: | ||
14 |
14 |
||
</pre> |
|||
=={{header|Pascal}}== |
|||
==={{header|Free Pascal}}=== |
|||
<syntaxhighlight lang="pascal"> |
|||
program doublylinkedlist; |
|||
type |
|||
pDbllist = ^tDbllist; |
|||
tDbllist = record |
|||
data: integer; |
|||
prev, next: pDbllist; |
|||
end; |
|||
procedure add(var tail: pDbllist; data: integer); |
|||
var |
|||
cur: pDbllist; |
|||
begin |
|||
new(cur); |
|||
cur^.data := data; |
|||
cur^.prev := tail; |
|||
cur^.next := nil; |
|||
if tail <> nil then |
|||
tail^.next := cur; |
|||
tail := cur; |
|||
end; |
|||
procedure delete(var head, tail: pDbllist; data: integer); |
|||
var |
|||
cur: pDbllist; |
|||
begin |
|||
cur := head; |
|||
while (cur <> nil) and (cur^.data <> data) do |
|||
cur := cur^.next; |
|||
if cur = nil then |
|||
exit; // data not found |
|||
if cur^.prev = nil then // cur is the head |
|||
begin |
|||
head := cur^.next; |
|||
if head <> nil then |
|||
head^.prev := nil |
|||
else |
|||
tail := nil; // list becomes empty |
|||
end |
|||
else if cur^.next = nil then // cur is the tail |
|||
begin |
|||
tail := cur^.prev; |
|||
tail^.next := nil; |
|||
end |
|||
else // cur is in the middle |
|||
begin |
|||
cur^.prev^.next := cur^.next; |
|||
cur^.next^.prev := cur^.prev; |
|||
end; |
|||
dispose(cur); |
|||
end; |
|||
procedure destroyList(var head: pDbllist); |
|||
var |
|||
cur, next: pDbllist; |
|||
begin |
|||
cur := head; |
|||
while cur <> nil do |
|||
begin |
|||
next := cur^.next; |
|||
dispose(cur); |
|||
cur := next; |
|||
end; |
|||
head := nil; |
|||
end; |
|||
procedure display(head: pDbllist); |
|||
var |
|||
cur: pDbllist; |
|||
begin |
|||
cur := head; |
|||
while cur <> nil do |
|||
begin |
|||
writeln(cur^.data); |
|||
cur := cur^.next; |
|||
end; |
|||
end; |
|||
var |
|||
head, tail: pDbllist; |
|||
i: integer; |
|||
begin |
|||
head := nil; |
|||
tail := nil; |
|||
// Initial list setup |
|||
for i := 1 to 5 do |
|||
begin |
|||
if tail = nil then |
|||
begin |
|||
new(head); |
|||
head^.data := i; |
|||
head^.prev := nil; |
|||
head^.next := nil; |
|||
tail := head; |
|||
end |
|||
else |
|||
begin |
|||
add(tail, i); |
|||
end; |
|||
end; |
|||
writeln('Original list:'); |
|||
display(head); |
|||
writeln('Deleting 3:'); |
|||
delete(head, tail, 3); |
|||
display(head); |
|||
writeln('Deleting 1 (head):'); |
|||
delete(head, tail, 1); |
|||
display(head); |
|||
writeln('Deleting 5 (tail):'); |
|||
delete(head, tail, 5); |
|||
display(head); |
|||
writeln('Destroying list!'); |
|||
destroyList(head); |
|||
display(head); // should display nothing as the list is destroyed |
|||
end. |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Original list: |
|||
1 |
|||
2 |
|||
3 |
|||
4 |
|||
5 |
|||
Deleting 3: |
|||
1 |
|||
2 |
|||
4 |
|||
5 |
|||
Deleting 1 (head): |
|||
2 |
|||
4 |
|||
5 |
|||
Deleting 5 (tail): |
|||
2 |
|||
4 |
|||
Destroying list! |
|||
</pre> |
</pre> |
||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
Extended copy of [[Doubly-linked_list/Traversal#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;">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: #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> |
||
Line 501: | Line 715: | ||
<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: #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> |
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 531: | Line 745: | ||
=={{header|Wren}}== |
=={{header|Wren}}== |
||
{{libheader|Wren-llist}} |
{{libheader|Wren-llist}} |
||
< |
<syntaxhighlight lang="wren">import "./llist" for DLinkedList |
||
var dll = DLinkedList.new(["dog", "cat", "bear"]) |
var dll = DLinkedList.new(["dog", "cat", "bear"]) |
||
Line 538: | Line 752: | ||
System.print("After removal 1: %(dll)") |
System.print("After removal 1: %(dll)") |
||
dll.removeAt(0) // remove by index |
dll.removeAt(0) // remove by index |
||
System.print("After removal 2: %(dll)")</ |
System.print("After removal 2: %(dll)")</syntaxhighlight> |
||
{{out}} |
{{out}} |
Latest revision as of 10:55, 18 May 2024
- 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.
Action!
The user must type in the monitor the following command after compilation and before running the program!
SET EndProg=*
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
- Output:
Screenshot from Atari 8-bit computer
(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": ()
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;
- 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.
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
FreeBASIC
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
- Output:
Before removals: { bear cat dog } After removal 1: { bear dog } After removal 2: { bear }
Go
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
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
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
Pascal
Free Pascal
program doublylinkedlist;
type
pDbllist = ^tDbllist;
tDbllist = record
data: integer;
prev, next: pDbllist;
end;
procedure add(var tail: pDbllist; data: integer);
var
cur: pDbllist;
begin
new(cur);
cur^.data := data;
cur^.prev := tail;
cur^.next := nil;
if tail <> nil then
tail^.next := cur;
tail := cur;
end;
procedure delete(var head, tail: pDbllist; data: integer);
var
cur: pDbllist;
begin
cur := head;
while (cur <> nil) and (cur^.data <> data) do
cur := cur^.next;
if cur = nil then
exit; // data not found
if cur^.prev = nil then // cur is the head
begin
head := cur^.next;
if head <> nil then
head^.prev := nil
else
tail := nil; // list becomes empty
end
else if cur^.next = nil then // cur is the tail
begin
tail := cur^.prev;
tail^.next := nil;
end
else // cur is in the middle
begin
cur^.prev^.next := cur^.next;
cur^.next^.prev := cur^.prev;
end;
dispose(cur);
end;
procedure destroyList(var head: pDbllist);
var
cur, next: pDbllist;
begin
cur := head;
while cur <> nil do
begin
next := cur^.next;
dispose(cur);
cur := next;
end;
head := nil;
end;
procedure display(head: pDbllist);
var
cur: pDbllist;
begin
cur := head;
while cur <> nil do
begin
writeln(cur^.data);
cur := cur^.next;
end;
end;
var
head, tail: pDbllist;
i: integer;
begin
head := nil;
tail := nil;
// Initial list setup
for i := 1 to 5 do
begin
if tail = nil then
begin
new(head);
head^.data := i;
head^.prev := nil;
head^.next := nil;
tail := head;
end
else
begin
add(tail, i);
end;
end;
writeln('Original list:');
display(head);
writeln('Deleting 3:');
delete(head, tail, 3);
display(head);
writeln('Deleting 1 (head):');
delete(head, tail, 1);
display(head);
writeln('Deleting 5 (tail):');
delete(head, tail, 5);
display(head);
writeln('Destroying list!');
destroyList(head);
display(head); // should display nothing as the list is destroyed
end.
- Output:
Original list: 1 2 3 4 5 Deleting 3: 1 2 4 5 Deleting 1 (head): 2 4 5 Deleting 5 (tail): 2 4 Destroying list!
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
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]