Doubly-linked list/AutoHotkey

From Rosetta Code
Doubly-linked list/AutoHotkey is part of Linked_List. You may find other members of Linked_List at Category: Linked_List.

Doubly-Linked List solutions[edit]

discussion

Build(D, L) { ; Double Linked list "D": D_{Head,Tail} = number>0 id of node
Local i ; D_%number%_{P,N,V}: Prev, Next, Value, D_%Free%: next free idx
Loop Parse, L, `,
i := A_Index
,%D%_%i%_P := i-1
,%D%_%i%_N := i+1
,%D%_%i%_V := A_LoopField
%D%_%i%_N:= 0, %D%_Free := i+1
%D%_Head := 1, %D%_Tail := i
}
Head(D) {
Return %D%_Head
}
Tail(D) {
Return %D%_Tail
}
Value(D,node) {
Return %D%_%node%_V
}
Next(D,node) {
Return %D%_%node%_N
}
Prev(D,node) {
Return %D%_%node%_P
}
Traverse(D,FW=1) {
Local i, t
i := (FW:=!InStr("B.BW.Back.Backward",FW) || FW=1) ? Head(D) : Tail(D)
While i
t .= Value(D,i) " ", i := FW ? Next(D,i) : Prev(D,i)
Return t
}
AddBefore(D,n,V) {
Local i, p
%D%_Free := 1 + i := %D%_Free, %D%_%i%_V := V
If (p := Prev(D,n)) ; n != head
%D%_%p%_N := i, %D%_%n%_P := i
,%D%_%i%_P := p, %D%_%i%_N := n
Else ; add before head
%D%_Head := i, %D%_%n%_P := i
,%D%_%i%_P := 0, %D%_%i%_N := n
Return i
}
AddAfter(D,n,V) {
Local i, t
%D%_Free := 1 + i := %D%_Free, %D%_%i%_V := V
If (t := Next(D,n)) ; n != tail
%D%_%t%_P := i, %D%_%n%_N := i
,%D%_%i%_P := n, %D%_%i%_N := t
Else ; add after tail
%D%_Tail := i, %D%_%n%_N := i
,%D%_%i%_P := n, %D%_%i%_N := 0
Return i
}
Delete(D,n) {
Local p, t
p := Prev(D,n), t := Next(D,n)
If (p && t) ; in the middle
%D%_%p%_N := t, %D%_%t%_P := p
Else If (p) ; tail
%D%_Tail := p, %D%_%p%_N := 0
Else If (t) ; head
%D%_Head := t, %D%_%t%_P := 0
Else ; -> empty list
%D%_Head := 0, %D%_Tail := 0
}
; TESTS ---------------------------------------------------------------
Build("D",3)
n := AddBefore("D",Head("D"),2)
AddBefore("D",n,1)
MsgBox % Traverse("D","FW") ; 1 2 3
 
Build("D",3)
AddAfter("D",Head("D"),2)
n := AddAfter("D",Head("D"),1)
MsgBox % Traverse("D") ; 3 1 2
 
Delete("D",n)
MsgBox % Traverse("D") ; 3 2
 
Delete("D",Head("D"))
MsgBox % Traverse("D") ; 2
 
Delete("D",Tail("D"))
MsgBox % Traverse("D") ; empty
 
L = a,bb,1,2,x-y,$
msgbox % "build: " L
Build("D", L)
MsgBox % "traverse forward: `n" Traverse("D","FW")
MsgBox % "traverse backward: `n" Traverse("D","Back")