Doubly-linked list/AutoHotkey

Doubly-Linked List solutions

discussion <lang AutoHotkey>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")</lang>