Doubly linked list

[ezzetabi]

Ponterless programming, Fortran style.

Just pass two arrays to _ListActivate, inizialize a iterator to 0 that is the sentinel ending node and enjoy.

A little test program

Dim $a[1], $b[1]
Dim $i = 0;Zero is a sentinel node at the end of the list

_ListActivate($a, $b)
_AddNode(100, $i, $a, $b)
_AddNode(200, $i, $a, $b)
_AddNode(400, $i, $a, $b)
_BackUp($i, $a)
_AddNode(300, $i, $a, $b)

MsgBox(0,'', 'Add node test')
$i = 0
While 1
  _Advance($i, $a)
  If @error Then ExitLoop
    
  MsgBox(0,'', _Retrieve($i, $a))
WEnd

_Advance($i, $a);pointing to 100
_Advance($i, $a);pointing to 200
_DelNode($i, $a, $b)
MsgBox(0,'', 'Delete test')
$i = 0
While 1
  _Advance($i, $a)
  If @error Then ExitLoop
    
  MsgBox(0,'', _Retrieve($i, $a))
WEnd

Exit

The code itself:

expandcollapse popup

Func _ListActivate(ByRef $avList, ByRef $avSet)
  ReDim $avList[2][3], $avSet[3]

  $avList[0][0] = 0;Previous node
  $avList[0][1] = 0;Value of the node
  $avList[0][2] = -1;Next node, 0 is a dummy sentinel node

  $avSet[0] = 1;Logical size of the list
  $avSet[1] = 2;Real size
EndFunc

;_AddNode adds before the itrPos
Func _AddNode($vValue, $itrPos, ByRef $avList, ByRef $avSet)
  Local $iPos
  
  $iPos = $avSet[0]
 
  $avList[$iPos][1] = $vValue
  $avList[$iPos][2] = $itrPos
  $avList[$iPos][0] = $avList[$itrPos][0]
  $avList[ $avList[$itrPos][0] ][2]= $iPos
  $avList[$itrPos][0] = $iPos
  
  $avSet[0] = $avSet[0] + 1
  If $avSet[0] > $avSet[1] / 2 Then
    __Double($avList, $avSet)
  EndIf
EndFunc

Func _DelNode(ByRef $itrPos, ByRef $avList, ByRef $avSet)
  If $itrPos <> 0 Then
    Local $iPos = $itrPos
    $avSet[0] = $avSet[0] - 1
    _Advance($itrPos, $avList)
    
    $avList[$avList[$iPos][2]][0] = $avList[$iPos][0]
    $avList[$avList[$iPos][0]][2] = $avList[$iPos][2]
    
    If $avSet[0] > 1 Then
      $avList[$iPos][0] = $avList[ $avSet[0] ][0]
      $avList[$iPos][1] = $avList[ $avSet[0] ][1]
      $avList[$iPos][2] = $avList[ $avSet[0] ][2]
      $avList[$avSet[0]][1] = 0
    Else
      $avList[$iPos][1] = 0
      $avList[0][0] = 0
      $avList[0][1] = 0
      $avList[0][2] = -1
    EndIf
  
    $avList[$avList[$iPos][0]][2] = $iPos
    $avList[$avList[$iPos][2]][0] = $iPos
    
    If $avSet[0] < $avSet[1] / 2 Then
      __Half($avList, $avSet)
    EndIf
  Else
    SetError(1)
  EndIf
EndFunc

Func _Advance(ByRef $itrPos, ByRef $avList)
  $itrPos = $avList[ $itrPos ][2]
  If $itrPos = 0 Then SetError(1)
EndFunc

Func _BackUp(ByRef $itrPos, ByRef $avList)
  $itrPos = $avList[ $itrPos ][0]
  If $itrPos = 0 Then SetError(1)
EndFunc

Func _Retrieve(ByRef $itrPos, ByRef $avList)
  If $itrPos <> 0 Then
    Return $avList[$itrPos][1]
  Else
    SetError(1)
    Return 0
  EndIf 
EndFunc

Func __Double(ByRef $fst, ByRef $snd)
  $snd[1] = $snd[1] * 2
  ReDim $fst[ $snd[1] ][3]
EndFunc

Func __Half(ByRef $fst, ByRef $snd)
  $snd[1] = $snd[1] / 2
  ReDim $fst[ $snd[1] ][3]
EndFunc

Bug alert, not deeply tested.