PureBasic Forums - English

Code: Select all

; -----------------------------------------------------------------------------------------------------------------------------------------------------
; TITLE:
; Educational Experiments of Linked List with full Function and including 15 Example Test Routine Lesson Ex.0.01
; Full documented and well commented code
;
; Experiment lesson 1
; Revision v 0.01
; My own linked List experiments 
; Written by : Uncle Ben (A.K.A William) 
;
; Educational purpose     : to learn & test the link-list theory and/or possibly implement on other programing language when needed
;
; Compiler Language : Purebasic 5.42 LTS DEMO
;
; Lesson Description :
;   To 'create / hold / manipulation / review' a chain List of LONG value (4byte)
;   Each function Return a current position pointer, you may store in a temperately VAR to use it later as entry pointer
;   Use a VAR_name for your chain list when create, this variable always contain the 1st Node entry point, use it as valid pointer to enter the chain   
;   To access a node , a valid entry pointer is required , (eg. curr_position is a pointer of the curr node)
;   NODE index is 1 base, the top most node has a index of 1, second node is 2 ... and so on
;   To access a node by index from any ENTRY pointer, function will traveling to the TOP of chain and then traveling to the desire node
;   If Insert/Delete at first Node , first node pointer will be change and return by Function ,
;   To get the first node pointer if necessary, use SelectNode function to Index 1 , ' eg. chain_name=SelectNode(curr_pos,1) '
;   No head design, the first node is a head(all value zero) when chain empty , it become a node when ADD/Insert a new node first time
;
; Chained Node Structure :  Each-node = [ DATA (LONG value=4byte) ]  [ Previous Pointer(LONG value=4byte) ]  [ Next Pointer(LONG value=4byte) ]
;
; list structure:  
; [Data 1, Pre-pointer=0,  Next-pointer =(Data2)] --> [Data 2, Pre-pointer=(Data1),  Next-pointer=(Data3)] --> [Data 3, Pre-pointer,  Next-pointer =0]
;
; Usage :   yourVARname = CreateNewList() ; initial your list 
;           yourVARname_curr_position = AddNode(yourVARname , yourLongDATA)  ; Append/Add a new node at the end of chain    
;           yourVARname_curr_position = InsertNode(yourVARname_curr_position , yourLongDATA)  ; Insert a new node infront of current node    
;           yourVARname_curr_position = DeleteNode(yourVARname_curr_position )  ; Delete the current node , return the next node as current node    
;
;
; *note: 'Pre-pointer = 0 and Next-pointer=0' is empty list ,  Pre-pointer = 'curr position' is at first element , Next-pointer = '0'  is at last element
;
;       
;
; (most of the time program just need to travel 'Linked List' and/or adding new node to it , other feature like insert/delete maybe  minimalist)
; -----------------------------------------------------------------------------------------------------------------------------------------------------

Procedure.l CreateNewList()   ; so your list name contain the address of the first element/head
    ProcedureReturn AllocateMemory(12)      ; create head node with null value (no element yet)
EndProcedure

Procedure.l IsLastNode(ListName); reture the next node pointer
  If PeekL(ListName+4)>0 And PeekL(ListName+8)=0 
    ProcedureReturn 1 ; return true if not empty and last position
  Else 
    ProcedureReturn 0 ; return false if empty or not at last
  EndIf
EndProcedure

Procedure.l IsFirstNode(ListName); reture the next node pointer
  If PeekL(ListName+4)=ListName ; previous position = curr position , no more previous
    ProcedureReturn 1 ; return true if this first position
  Else 
    ProcedureReturn 0 ; return false 
  EndIf
EndProcedure

Procedure.l IsEmptyList(ListName); reture the next node pointer
  If PeekL(ListName+4)=0 And PeekL(ListName+8)=0 
    ProcedureReturn 1 ; return true if empty
  Else 
    ProcedureReturn 0 ; return false if not empty
  EndIf
EndProcedure

Procedure.l AddNode(ListName,NodeData)    ; add a node element and return the current/latest address of New node
  Protected FirstNode.l,NextNodeAddress.l
  FirstNode=ListName
  ; *** If chain is empty , Head become first node
  If PeekL(FirstNode+4)=0 And PeekL(FirstNode+8)=0   ; check is head of chain , (pre-pointer=0 and next-pointer=0)
    PokeL(ListName,NodeData)
    PokeL(ListName+4,FirstNode)  ; first element :=( Data , Pre=-1 , Next =0)  ; no element :=( Data=0, Pre=0 . Next=0)
    NewNode=ListName
  Else          ; *** if ( first element ) exist ( eg. chain not empty )
    NextNodeAddress=PeekL(FirstNode+8)
    OldNodeAddress=FirstNode
    ; *** traveling to the end of the chain
    While NextNodeAddress>0     
      OldNodeAddress=NextNodeAddress ; store curr node address
      NextNodeAddress=PeekL(oldNodeAddress+8)  ; get the next pointer of this element after goto
    Wend
    ; *** so now is at the last node element
    NewNode=AllocateMemory(12)      ; crete new node element
    If NewNode=0: MessageRequester("Memory ERROR","")  :ProcedureReturn 0: EndIf ; if system memory error 
    PokeL(NewNode,NodeData)                                                      ; store Data to newly created node
    PokeL(NewNode+4,OldNodeAddress)                                              ; Store the Previous Note Pointer
    ;    PokeL(NewNode+8,0)                                                    ; Next =0 (not set) , save this step when memory is Allocated as zero 
    PokeL(OldNodeAddress+8,NewNode)                                              ; store the curr node pointer on the (previous node next pointer)
  EndIf
  ProcedureReturn NewNode
EndProcedure

Procedure.l GetNodeData(ListName); return current node data
  ProcedureReturn PeekL(ListName)
EndProcedure

Procedure.l GetNextPointer(ListName); return the next node pointer
  ProcedureReturn PeekL(ListName+8)
EndProcedure

Procedure.l GetPreviousPointer(ListName); return the previous node pointer
  ProcedureReturn PeekL(ListName+4)
EndProcedure

Procedure.l DeleteNode(CurrNodePointer)
  del=CurrNodePointer
  If IsEmptyList(CurrNodePointer) ; do nothing if link list is empty
    ProcedureReturn CurrNodePointer
  ElseIf IsFirstNode(CurrNodePointer) And IsLastNode(CurrNodePointer)   ; only 1 element in list
    FillMemory(del, 12)                                                 ; clear the list and remain the head node (only 1 node in list to del)
    ProcedureReturn CurrNodePointer                                     ; return the same head pointer 
  ElseIf IsFirstNode(CurrNodePointer)                                   ; more than 1 element , and delete the first
    curr=GetNextPointer(CurrNodePointer)
;          MessageRequester("enter","")      
    PokeL(curr+4,curr) ; make the next node become first node
    FreeMemory(del)    ; delete the old one 
    ProcedureReturn curr ; return the new current position after delete
  ElseIf IsLastNode(CurrNodePointer)
    curr=GetPreviousPointer(CurrNodePointer)
    PokeL(curr+8,0) ; previous node become last node
    FreeMemory(del)
    ProcedureReturn curr
  Else ; everything in between
    curr=GetNextPointer(CurrNodePointer)
    pre=GetPreviousPointer(CurrNodePointer)
    PokeL(curr+4,pre)  ; set the next node ref to previous node (skipping the one in between 'del')
    PokeL(pre+8,curr)  ; set the previous node ref to next node (skip the 'del' node)
    ProcedureReturn curr
  EndIf  
EndProcedure

Procedure.l InsertNode(CurrNodePointer,NodeData)
;      MessageRequester("enter","")      
  If IsEmptyList(CurrNodePointer); Or IsLastNode(CurrNodePointer)
    *Insert= AddNode(CurrNodePointer,NodeData)
  Else
    pre=PeekL(CurrNodePointer+4)
    *Insert=AllocateMemory(12)    ; create new node
    PokeL(*Insert,NodeData)       ; store data
                                  ; change pointer
    PokeL(*Insert+8,CurrNodePointer)          ; new node [next] point to old node (currNode become old node)
    
    If IsFirstNode(CurrNodePointer)   ; if insert at the top
      PokeL(*Insert+4,*Insert) ; new node [pre] point to self node if this is first node
    Else
      ;    CopyMemory(CurrNodePointer+4,*Insert+4,4)  ; new node copy the previous pointer
      PokeL(*Insert+4,PeekL(CurrNodePointer+4)) ; new node [pre] point to before node
      
      ; change old node pointer
      PokeL(pre+8,*Insert)             ; change before node pointer
    EndIf
    PokeL(CurrNodePointer+4,*Insert) ; change the [pre] of 'existing node' (become next node) point to inserted node(become node before)
  EndIf
  ProcedureReturn *Insert
EndProcedure

Procedure.l SelectNode(ListName, Index)  ; goto the selected node , if index is > total item , then select the last node , resetlist() is simply goto 1st-node
  If IsEmptyList(ListName)
    ProcedureReturn ListName  ; do nothing if link list is empty
  Else
  pos=ListName
  While IsFirstNode(pos)=0             ; if not at the first node and not empty list, go back to the first node
    pos=GetPreviousPointer(pos)
  Wend
  HeadPointer=pos ; now is at Head/1st Node position
  ; go to the request positon
  nextpointer=HeadPointer ; start travel from the Head position to the request Index
    For i=1 To Index
      currPos=nextpointer
      nextpointer=GetNextPointer(nextpointer)
      If nextpointer=0 :Break  : EndIf   ; stop at last  if index too large
    Next
    ProcedureReturn currPos
  EndIf
  
EndProcedure

;
;----------------------------------------------------------------------------------------------------------------------------------------------------
;
; *******  Test Function   ********
;   --------------------------------------------------------
;       <  >
;  Test 1:  Test Head Node
;  Test 2:  Test Delete on empty list
;  Test 3:  Test Traveling on empty list
;  Test 4:  Test Insert on empty list
;  Test 5:  Test Delete on 1st Node when there is only 1 Node at the chain
;  Test 6:  Test Add/Append New Node on empty chain
;  Test 7:  Test Traveling Entire Chain
;  Test 8:  Test Select Node by Index
;  Test 9:  Test Select Node by 'WRONG' Index
;  Test 10:  Test Insert at last position
;  Test 11:  Test Insert at Middle position
;  Test 12:  Test Insert at Top position with many node at the chain
;  Test 13:  Test Delete at Last Position
;  Test 14:  Test Delete at Middle Position
;  Test 15:  Test Delete at Top Position with many node at the chain
;
;
;--------------------------------------------------------------------------------------------------------------------------------------------------
;
OpenConsole("LinkedList Experiment")

; Create/Initial chain list
myList=CreateNewList()  ; myList = Head pointer   


; ===========================
;  Test 1:  Test Head Node
Print("---Test 1:  Test Head Node-----------"+Chr(10))
; traveling and  display the linked list
travellist=myList
Gosub SubTravel

; ===========================
;  Test 2:  Test Delete on empty list
Print("---Test 2:  Test Delelet on empty list--------"+Chr(10))
DeleteNode(myList)
; traveling and  display the linked list
travellist=myList
Gosub SubTravel

; ===========================
;  Test 3:  Test Traveling on empty list
Print("---Test 3:  Test Traveling on empty list--------"+Chr(10))
; traveling and  display the linked list
travellist=myList
Gosub SubTravel


; ===========================
;  Test 4:  Test Insert on empty list
Print("---Test 4:  Test Insert on empty list--------"+Chr(10))
userData=222
InsertNode(myList,userData)
; traveling and  display the linked list
travellist=myList
Gosub SubTravel

; ===========================
;  Test 5:  Test Delete on 1st Node when there is only 1 Node at the chain
Print("--Test 5:  Test Delete on 1st Node when there is only 1 Node at the chain--"+Chr(10))
DeleteNode(myList)  ; myList only have 1 element after the previous test , after delete , the list is empty
; traveling and  display the linked list
travellist=myList
Gosub SubTravel



; ===========================
;  Test 6:  Test Add/Append New Node
Print("---Test 6:  Test Add/Append New Node------"+Chr(10))
AddNode(myList,1234)  ; add 1 node
For i=100 To 20 Step -27  ; add 3 more node 
  AddNode(myList,i)
Next 
; traveling and  display the linked list
travellist=myList
Gosub SubTravel


; ===========================
;  Test 7:  Test Traveling Entire Chain
Print("--Test 7:  Test Traveling Entire Chain----"+Chr(10))
; just show the traveling , it should have 4 element after previous test
; traveling and  display the linked list
travellist=myList
Gosub SubTravel


; ===========================
;  Test 8:  Test Select Node by Index
Print("--Test 8:  Test Select Node by Index---"+Chr(10))
Print("Get the Node DATA of INDEX 3 :"+Chr(10))
index=3
curr_pointer=SelectNode(myList, index)
Print("Select Index : "+StrU(index)+Chr(10))
Print("Node Data    = "+GetNodeData(curr_pointer)+Chr(10))
Print("Function return the Selected valid node ! "+Chr(10)+Chr(10))

; ===========================
;  Test 9:  Test Select Node by 'WRONG' Index
Print("--Test 9:  Test Select Node by 'WRONG' Index--"+Chr(10))
Print("Get the Node DATA of INDEX 19 :"+Chr(10))
index=19
curr_pointer=SelectNode(myList, index)
Print("Select Index : "+StrU(index)+Chr(10))
Print("Node Data    = "+GetNodeData(curr_pointer)+Chr(10))
Print("Function return the last valid node ! "+Chr(10)+Chr(10))

; ===========================
;  Test 10:  Test Insert at last position
Print("--Test 10:  Test Insert at last position--"+Chr(10))
Print(" Select INDEX 4 and INSERT '999'"+Chr(10))
Print(" [curr_pointer] is at last position after previous test"+Chr(10))
Print("Data inserted , Function return the New Pointer "+Chr(10))
curr_pointer=InsertNode(curr_pointer,999) ; return the new pointer to curr_pointer
; traveling and  display the linked list
travellist=myList
Gosub SubTravel


; ===========================
;  Test 11:  Test Insert at Middle position
Print("--Test 11:  Test Insert at Middle position--"+Chr(10))
Print(" Select INDEX 3 and INSERT '333'"+Chr(10))
Print("Data inserted , Function return the New Pointer, chain contain 6 Node now "+Chr(10))
curr_pointer=SelectNode(myList,3)
curr_pointer=InsertNode(curr_pointer,333) ; return the new pointer to curr_pointer
; traveling and  display the linked list
travellist=myList
Gosub SubTravel

; ===========================
;  Test 12:  Test Insert at Top position with many node at the chain
Print("--Test 12:  Test Insert at Top position with many node at the chain--"+Chr(10))
curr_pointer=InsertNode(myList,7777) ; myList contain the first node/head pointer , after insert , the head pointer was change
myList=SelectNode(curr_pointer,1)    ; goto the first node at get the new head pointer 
Print("Data inserted , Function return the top most Pointer, your initial head pointer was changed "+Chr(10))
Print("Chain has total 7 Node now "+Chr(10))
; in this case , curr_pointer is 1st node pointer , so '  myList=curr_pointer ' also will work as head (first node is actual head)
; traveling and  display the linked list
travellist=myList
Gosub SubTravel


; ===========================
;  Test 13:  Test Delete at Last Position
Print("--Test 13:  Test Delete at Last Position--"+Chr(10))
curr_pointer=SelectNode(curr_pointer,7)  ; select the last node , there was 7 node in total after the previous test 
curr_pointer=DeleteNode(curr_pointer)
Print("Data Deleted , Function return the last node Pointer "+Chr(10))
Print("Chain has total 6 Node now "+Chr(10))
; traveling and  display the linked list
travellist=myList
Gosub SubTravel

;MessageRequester("Debug curr pointer", StrU(curr_pointer))

; ===========================
;  Test 14:  Test Delete at Middle Position
Print("--Test 14:  Test Delete at Middle Position--"+Chr(10))
Print("Try to delete at Position INDEX 3 "+Chr(10))

curr_pointer=SelectNode(curr_pointer,3)  ; select the 3rd node ,Index=3 , there was 6 node in total after the previous test 
;MessageRequester("Debug 3rd pointer", StrU(curr_pointer))

curr_pointer=DeleteNode(curr_pointer)
Print("Data Deleted , Function return the replaced 3rd node Pointer "+Chr(10))
Print("Chain has total 5 Node now "+Chr(10))
; traveling and  display the linked list
travellist=myList
Gosub SubTravel


; ===========================
;  Test 15:  Test Delete at Top Position with many node at the chain
Print("--Test 15:  Test Delete at Top Position with many node at the chain--"+Chr(10))
;curr_pointer=myList;SelectNode(curr_pointer,1)  ; select the 1st node ,Index=1 , there was 5 node in total after the previous test 
curr_pointer=DeleteNode(myList)  ;myList is the 1st node poiter , same as SelectNode(myList, 1)
 ; first node pointer has been release and replaced by the following pointer , so remenber to restore it to 'myList' list name
myList=SelectNode(curr_pointer,1)  ; get the replaced 1st node pointer 
Print("Data Deleted , Function return the replaced 1st node Pointer "+Chr(10))
Print("Chain has total 4 Node now "+Chr(10))
; traveling and  display the linked list
travellist=myList
Gosub SubTravel


; ***********
; ** CAUTION **:  If any 'add/delete/insert' was perform at 1st node position , the Head entry pointer will be change , old Head entry point was invalid  
; ** remember to restore the Head (1st node) pointer to your list name , so can be use to access the chain by ref to 'myList' Head entry pointer  
; ** InsertNode() always insert INTO before the current position 
;
; ************


; ******* End TEST ***************
Print(Chr(10)+">> Press ENTER to Exit <<")
String$ = Input()
End 

; ----------- sub routine to travel list and display all node -------
SubTravel:
Repeat
  myData=GetNodeData(travellist);PeekL(myList)
  getNext=GetNextPointer(travellist);PeekL(myList+8)
  getPre=GetPreviousPointer(travellist);PeekL(myList+4)
  Print("Data = "+RSet(StrU(myData),9)+" |   Pre Pointer = "+StrU(getPre)+"  |  Next Pointer = "+StrU(getNext)+Chr(10))
  travellist  =GetNextPointer(travellist)
Until getNext=0 
Print(Chr(10))
Return

Code: Select all

OpenConsole("Array Seek Time Test")

StartTime = ElapsedMilliseconds()            

Dim a(1000) ;    zero base , 1001 element
For t=1 To 1000
  a(t)=t      ; initial assign value
Next 

For t = 1 To 200000
  a(Random(1000,1))=5544    ; random asign value 
Next
For t = 1 To 200000
  b=a(Random(1000,1))       ;random retrieve value
Next                        

ElapsedTime = ElapsedMilliseconds()-StartTime 

LF$=Chr(10)
Print("-------------------------------------------------------"+lf$)
Print("Elaspse Time to test array() performance : "+lf$)
Print("array size = 1001"+lf$)
Print("randomly asign value 200,000 loops"+lf$)
Print("randomly retrieve value 200,000 loops"+lf$)
Print("Total time use == :  "+ StrU(ElapsedTime)+" ms"+lf$)
Print("-------------------------------------------------------"+lf$)

String$ = Input()
END

Code: Select all

OpenConsole("PB LinkedList Seek Time Test")
StartTime = ElapsedMilliseconds()            

NewList test()

For t=0 To 1000   ;    zero base , 1001 element
  AddElement(test()) : test()=t      ; initial assign value
Next 

For t = 1 To 200000
  SelectElement(test(),Random(1000,1))
  test()=5544     ; random asign value 
Next
For t = 1 To 200000
  SelectElement(test(),Random(1000,1))
  b=test()       ;random retrieve value
Next                        

ElapsedTime = ElapsedMilliseconds()-StartTime 


Print("-------------------------------------------------------"+lf$)
Print("Elapse Time to test Purebasic Linklist performance : "+lf$)
Print("List size = 1001"+lf$)
Print("randomly assign value 200,000 loops"+lf$)
Print("randomly retrieve value 200,000 loops"+lf$)
Print("Total time use == :  "+ StrU(ElapsedTime)+" ms"+lf$)
Print("-------------------------------------------------------"+lf$)
String$ = Input()
END

Code: Select all

Procedure.l CreateNewList()   ; so your list name contain the address of the first element/head
    ProcedureReturn AllocateMemory(12)      ; create head node with null value (no element yet)
EndProcedure

Procedure.l IsLastNode(ListName); reture the next node pointer
  If PeekL(ListName+4)>0 And PeekL(ListName+8)=0 
    ProcedureReturn 1 ; return true if not empty and last position
  Else 
    ProcedureReturn 0 ; return false if empty or not at last
  EndIf
EndProcedure

Procedure.l IsFirstNode(ListName); reture the next node pointer
  If PeekL(ListName+4)=ListName ; previous position = curr position , no more previous
    ProcedureReturn 1 ; return true if this first position
  Else 
    ProcedureReturn 0 ; return false 
  EndIf
EndProcedure

Procedure.l IsEmptyList(ListName); reture the next node pointer
  If PeekL(ListName+4)=0 And PeekL(ListName+8)=0 
    ProcedureReturn 1 ; return true if empty
  Else 
    ProcedureReturn 0 ; return false if not empty
  EndIf
EndProcedure

Procedure.l AddNode(ListName,NodeData)    ; add a node element and return the current/latest address of New node
  Protected FirstNode.l,NextNodeAddress.l
  FirstNode=ListName
  ; *** If chain is empty , Head become first node
  If PeekL(FirstNode+4)=0 And PeekL(FirstNode+8)=0   ; check is head of chain , (pre-pointer=0 and next-pointer=0)
    PokeL(ListName,NodeData)
    PokeL(ListName+4,FirstNode)  ; first element :=( Data , Pre=-1 , Next =0)  ; no element :=( Data=0, Pre=0 . Next=0)
    NewNode=ListName
  Else          ; *** if ( first element ) exist ( eg. chain not empty )
    NextNodeAddress=PeekL(FirstNode+8)
    OldNodeAddress=FirstNode
    ; *** traveling to the end of the chain
    While NextNodeAddress>0     
      OldNodeAddress=NextNodeAddress ; store curr node address
      NextNodeAddress=PeekL(oldNodeAddress+8)  ; get the next pointer of this element after goto
    Wend
    ; *** so now is at the last node element
    NewNode=AllocateMemory(12)      ; crete new node element
    If NewNode=0: MessageRequester("Memory ERROR","")  :ProcedureReturn 0: EndIf ; if system memory error 
    PokeL(NewNode,NodeData)                                                      ; store Data to newly created node
    PokeL(NewNode+4,OldNodeAddress)                                              ; Store the Previous Note Pointer
    ;    PokeL(NewNode+8,0)                     ; Next =0 (not set) , save this step when memory is Allocated as zero 
    PokeL(OldNodeAddress+8,NewNode)              ; store the curr node pointer on the (previous node next pointer)
  EndIf
  ProcedureReturn NewNode
EndProcedure

Procedure.l GetNodeData(ListName); return current node data
  ProcedureReturn PeekL(ListName)
EndProcedure
Procedure SetNodeData(ListName,NodeData); asign current node data
   PokeL(ListName,NodeData)
EndProcedure

Procedure.l GetNextPointer(ListName); return the next node pointer
  ProcedureReturn PeekL(ListName+8)
EndProcedure

Procedure.l GetPreviousPointer(ListName); return the previous node pointer
  ProcedureReturn PeekL(ListName+4)
EndProcedure

Procedure.l DeleteNode(CurrNodePointer)
  del=CurrNodePointer
  If IsEmptyList(CurrNodePointer) ; do nothing if link list is empty
    ProcedureReturn CurrNodePointer
  ElseIf IsFirstNode(CurrNodePointer) And IsLastNode(CurrNodePointer)   ; only 1 element in list
    FillMemory(del, 12)                       ; clear the list and remain the head node (only 1 node in list to del)
    ProcedureReturn CurrNodePointer                                     ; return the same head pointer 
  ElseIf IsFirstNode(CurrNodePointer)                                   ; more than 1 element , and delete the first
    curr=GetNextPointer(CurrNodePointer)
;          MessageRequester("enter","")      
    PokeL(curr+4,curr) ; make the next node become first node
    FreeMemory(del)    ; delete the old one 
    ProcedureReturn curr ; return the new current position after delete
  ElseIf IsLastNode(CurrNodePointer)
    curr=GetPreviousPointer(CurrNodePointer)
    PokeL(curr+8,0) ; previous node become last node
    FreeMemory(del)
    ProcedureReturn curr
  Else ; everything in between
    curr=GetNextPointer(CurrNodePointer)
    pre=GetPreviousPointer(CurrNodePointer)
    PokeL(curr+4,pre)  ; set the next node ref to previous node (skipping the one in between 'del')
    PokeL(pre+8,curr)  ; set the previous node ref to next node (skip the 'del' node)
    ProcedureReturn curr
  EndIf  
EndProcedure

Procedure.l InsertNode(CurrNodePointer,NodeData)
;      MessageRequester("enter","")      
  If IsEmptyList(CurrNodePointer); Or IsLastNode(CurrNodePointer)
    *Insert= AddNode(CurrNodePointer,NodeData)
  Else
    pre=PeekL(CurrNodePointer+4)
    *Insert=AllocateMemory(12)    ; create new node
    PokeL(*Insert,NodeData)       ; store data
                                  ; change pointer
    PokeL(*Insert+8,CurrNodePointer)          ; new node [next] point to old node (currNode become old node)
    
    If IsFirstNode(CurrNodePointer)   ; if insert at the top
      PokeL(*Insert+4,*Insert) ; new node [pre] point to self node if this is first node
    Else
      ;    CopyMemory(CurrNodePointer+4,*Insert+4,4)  ; new node copy the previous pointer
      PokeL(*Insert+4,PeekL(CurrNodePointer+4)) ; new node [pre] point to before node
      
      ; change old node pointer
      PokeL(pre+8,*Insert)             ; change before node pointer
    EndIf
    PokeL(CurrNodePointer+4,*Insert) 
    ; change the [pre] of 'existing node' (become next node) point to inserted node(become node before)
  EndIf
  ProcedureReturn *Insert
EndProcedure

; goto the selected node , if index is > total item ,select the last node , resetlist() is simply goto 1st-node
Procedure.l SelectNode(ListName, Index) 
  If IsEmptyList(ListName)
    ProcedureReturn ListName  ; do nothing if link list is empty
  Else
  pos=ListName
  While IsFirstNode(pos)=0             ; if not at the first node and not empty list, go back to the first node
    pos=GetPreviousPointer(pos)
  Wend
  HeadPointer=pos ; now is at Head/1st Node position
  ; go to the request positon
  nextpointer=HeadPointer ; start travel from the Head position to the request Index
    For i=1 To Index
      currPos=nextpointer
      nextpointer=GetNextPointer(nextpointer)
      If nextpointer=0 :Break  : EndIf   ; stop at last  if index too large
    Next
    ProcedureReturn currPos
  EndIf
  
EndProcedure

OpenConsole("CUSTOM LinkedList Seek Time Test")
StartTime = ElapsedMilliseconds()            

test=CreateNewList()

For t=0 To 1000   ;    zero base , 1001 element
  AddNode(test,t)       ; initial assign value
Next 

For t = 1 To 200000
  pos=SelectNode(test,Random(1000,1))
  SetNodeData(pos,5544)     ; random asign value 
Next
For t = 1 To 200000
  pos=SelectNode(test,Random(1000,1))
  b=GetNodeData(pos)       ;random retrieve value
Next                        

ElapsedTime = ElapsedMilliseconds()-StartTime 


Print("-------------------------------------------------------"+lf$)
Print("Elapse Time to test CUSTOM LinkedList performance : "+lf$)
Print("List size = 1001"+lf$)
Print("randomly assign value 200,000 loops"+lf$)
Print("randomly retrieve value 200,000 loops"+lf$)
Print("Total time use == :  "+ StrU(ElapsedTime)+" ms"+lf$)
Print("-------------------------------------------------------"+lf$)
String$ = Input()
END

Code: Select all

; -----------------------------------------------------------------------------------------------------------------------------------------------------
; TITLE:
; Educational Experiments of Doubly Linked List with "Head" segment and including 18 Test Routines Lesson EP1.RV.2
; Full documented and well commented code
;
; My own linked List experiments 
; Written by : Uncle Ben (A.K.A William) 
;
; Experiment 1 :   EP1
; Revision Ref :  RV2
;
; Educational purpose     : to learn & test the doubly linked list theory ,With "Head" segment
;                           And/Or possibly implement on other programing language when needed
;
; Compiler Language : Purebasic 5.4x 
;
; Lesson Description :
;  *To 'create / hold / manipulation / review' a doubly linked chain list of LONG value (4byte)
;
;  * Maintained Head segment with content of : 
;                   [Current Index][Self-PTR][1st Pointer][Last Pointer][Curr Pointer][Total Node][Data Type] ; 28byte (4byte each)   
;
;  * [VAR yourListName] holds content of a pointer point to [Head] segment for later manipulation referencing use
;
;  * Improve searching algorithm : by HEAD/TAIL/CURRENT referencing to find shortest path  
;
;  * Program Basic Functional routine to :
;                 Create List , Add Nodes , Delete Nodes , Select Node By Index , Insert Nodes in between ,  Check Index and Total nodes
;   
;   * NODE index is 1 base, the top most node has a index of 1, second node is 2 ... and so on
;   * Test all program routines with a empty list (without nodes) and test again with many nodes added
;   * Every function routine need to keep track on [Head] segment , and set/unset accordingly
;
;   * Head Structure : 
;            [Current Index][Self-PTR][1st Pointer][Last Pointer][Curr Pointer][Total Node][Data Type]   ; 28byte in total (4byte each) 
;
;   * Standard Node Structure :   12 byte in total
;            Each Node = [ Data/StringPtr (LONG value=4byte) ]  [ Previous Pointer(LONG value=4byte) ]  [ Next Pointer(LONG value=4byte) ]
;
;   * First Node Structure :   12 byte in total
;          Node =   [ Data/StringPtr (LONG value=4byte) ]  [ HEAD Pointer (LONG value=4byte) ]  [ Next Pointer(LONG value=4byte) ]
;
;   * Last Node Structure  :   12 byte in total
;            Each Node = [ Data/StringPtr (LONG value=4byte) ]  [ Previous Pointer(LONG value=4byte) ]  [ 0 (Null) (LONG value=4byte) ]
;
;   * List structure:  
;           [Head] <--> [Node] <--> [Node] <--> [Node] <--> [Node] <--> [Node] <--> [Node] <--> [Node] <--> [Node] <--> [Node]
;
;   * List Data Type : 
;             32bit LONG value          = 4 byte stored inside node
;             Variable length STRING    = 4 byte memory pointer stored inside node
;
;
; Usage :   your_List_name = CreateNewList() ; initial your list 
;           your_curr_position = AddNode( your_List_Name , yourLongDATA )     ; Append/Add a new node at the end of chain    
;           your_curr_position = InsertNode( your_List_name , yourLongDATA )  ; Insert a new node in front of current node    
;           your_curr_position = DeleteNode( your_List_name )                 ; Delete the current node , return the next node as current node    
;           Flag = FreeLinkedList( your_List_name )                           ; Delete the entire list and free the memory    
;           your_curr_position = SelectNode( your_List_name , Index )         ; GOTO or Select a node by it's Index ,return the selected node pointer   
;
;
; *note: when manipulation with curr pointer, you need to search the HEAD for update Head information
; **** optimize for speed :: don't use many call's , try to solve locally with faster routine
; **** for better speed , code may be use reference from table/array , and try perform less intensive operation/instruction's; 
; checking invalid syntax is on compiler level , run time will not check any ERROR , checking syntax ERROR in run-time is a interpreter 
; ** InsertNode() always insert INTO the current position and push node backward 
;       
;
; (most of the time program just need to travel 'Linked List' and/or adding new node to it , other feature like insert/delete may be  minimanist)
; -----------------------------------------------------------------------------------------------------------------------------------------------------

; LINK Stucture : very fast to 1st node , last node , travel can be start from either end of link or from current index position
;[Current Index][Self-PTR][1st Pointer][Last Pointer][Curr Pointer][Total Node][Data Type] ; 28byte (4byte each)
; +0              +4,        8           +12            +16          +20        +24
Procedure.l CreateNewList()   ;* so your list name contain the address of the first element/head
  Head=AllocateMemory(28)    
  If Head 
    PokeL(Head+4,Head)  ; [Self-PTR] , self referencing means this is HEAD
    ProcedureReturn Head      ; create head node with null value (no element yet)
  Else
    ProcedureReturn 0   ; fail
  EndIf
EndProcedure
Procedure.l IsHeadNode(ListName)
  If PeekL(ListName+4)= ListName ; pointer to self (SELF referencing) is Head
    ProcedureReturn 1            ; return true 
  Else 
    ProcedureReturn 0 ; return false 
  EndIf
EndProcedure
Procedure.l IsEmptyList(ListName);* deprecate , if ListSize()=0 means empty list
  If IsHeadNode(ListName)
    If PeekL(ListName+20)=0    ; [Total Node]=0 
      ProcedureReturn 1        ; return true if empty
    Else 
      ProcedureReturn 0 ; return false 
    EndIf
  Else
    ProcedureReturn 0 ; false, if any node other then HEAD node
  EndIf
EndProcedure
Procedure.l IsLastNode(ListName);* check if curr is last index
  If IsHeadNode(ListName)
    If PeekL(ListName+20)= PeekL(ListName) ; check the [Total Node] = [Current Index]
      ProcedureReturn 1                    ; return true if not empty and last position
    Else 
      ProcedureReturn 0 ; return false if empty or not at last
    EndIf
  Else  ; any node place
    If PeekL(ListName+8)=0 ; [Node][Pre][Next] = Next=0
      ProcedureReturn 1    ; return true 
    Else 
      ProcedureReturn 0 ; return false 
    EndIf
  EndIf
EndProcedure

Procedure.l IsFirstNode(ListName) ; * check if curr index is 1st index                             
                                  ; Check the current index , index=PeekL(ListName) , index=1 means curr is first node
  If IsHeadNode(ListName)  And PeekL(ListName)=1      
    ProcedureReturn 1
  Else
    ProcedureReturn 0 ; return No
  EndIf
EndProcedure

Procedure.l GetNodeData(ListName);* return current node data
    ProcedureReturn PeekL(PeekL(ListName+16))
EndProcedure
Procedure.l FastGetNodeData(*Curr)   ; no ERROR checking , for performance test
  ProcedureReturn PeekL(*Curr)
EndProcedure

Procedure.l FastSetNodeData(*Curr,NodeData)   ; Directly set assign data value to node pointer "caution" no ERROR checking , for performance test
  ProcedureReturn PokeL(*Curr,NodeData)
EndProcedure

Procedure SetNodeData(ListName,NodeData)    ; set data value to "ListName" current index position
  curr=PeekL(ListName+16)
  PokeL(curr,NodeData)
EndProcedure

Procedure.l GetNextPointer(ListName);* return the next node pointer
    If IsHeadNode(ListName)
      ProcedureReturn PeekL(PeekL(ListName+16)+8)
    Else  
      ProcedureReturn PeekL(ListName+8)
    EndIf
EndProcedure

Procedure.l GetPreviousPointer(ListName);* return the previous node pointer
  If IsHeadNode(ListName)
    ProcedureReturn PeekL(PeekL(ListName+4))
  Else  
    ProcedureReturn PeekL(ListName+4)
  EndIf
EndProcedure

Procedure.l SearchHeadNode(pos)
  ;  While IsFirstNode(pos)=0             ; if not at the first node and not empty list, go back to the first node
 While PeekL(pos+4)<> pos ; Check [Self-PTR] = Head pointer then this is head here
    pos = PeekL(pos+4)   ; GetPreviousPointer(pos) ; this faster
  Wend
  ProcedureReturn pos ; return [Head] pointer
EndProcedure

Procedure.l GotoFirstElement(ListName);*   Same as   "  FirstElement()  " 
  head=ListName
  PokeL(Head,1) ; change curr IDX
  curr_pointer=PeekL(Head+8)
  PokeL(Head+16, curr_pointer ) ; change curr PTR copy from [head 1st pointer]
  ProcedureReturn curr_pointer
EndProcedure

Procedure.l GotoLastElement(ListName);*  same as   "  LastElement()  " 
  head=ListName
  lastIndex= PeekL(ListName+20) ; total element
  PokeL(Head,lastIndex) ; change curr IDX
  curr_pointer=PeekL(Head+12) ; last pointer
  PokeL(Head+16, curr_pointer ) ; change curr PTR copy from [head last pointer]
  ProcedureReturn curr_pointer
EndProcedure

Procedure.l GetListIndex(ListName)  ; same as  "  ListIndex()  "
  ProcedureReturn PeekL(ListName)
EndProcedure
Procedure.l GetTotalElement(ListName)  ; same as " ListSize() ; CountList()  "
  ProcedureReturn PeekL(ListName+20)
EndProcedure

Procedure.l AddNode(ListName,NodeData)    ; * add a node element and return the New node memory pointer
 ;[Current Index][Self-PTR][1st Pointer][Last Pointer][Curr Pointer][Total Node][Data Type] ; 28byte (4byte each)
 ; +0              +4,        8           +12            +16          +20        +24
  
  ; *** If chain is empty , add first node
  If PeekL(ListName+20)=0    ; [Total Node]=0   ; is empty     
    NewLast=AllocateMemory(12); node only need 12 byte [DATA][PRE][NEXT]
    PokeL(NewLast,NodeData)   ; DATA
    PokeL(NewLast+4,ListName) ; [PRE] = [SELF-Ptr] at head , because this is 1st element  
                              ; [next] is not set=0
                              ; update Head *** Do NOT Change [Self-PTR] , it is permanent
    PokeL(ListName,1)         ; current index =+1
    PokeL(ListName+8,NewLast) ; this is 1st pointer also last node
    PokeL(ListName+12,NewLast); this Last pointer
    PokeL(ListName+16,NewLast); Curr position pointer (curr is 1st node)
    PokeL(ListName+20,1)      ; total element =1
  Else                        ; If not empty then get the last node ref and add after it)   
;   If PeekL(ListName+4)= ListName ; pointer to self (SELF referencing) is Head ; if IsHeadNode()
      Head=ListName
;    Else
;      Head=SearchHeadNode(ListName) ; get the HEAD ,and no need to travel to last any more
;    EndIf
    PreLastNode=PeekL(Head+12) ; get the last pointer and mark as "Previous Last"
    
    ; *** so now is at the last node element
    NewLast=AllocateMemory(12)      ; crete new node element
                                    ;    If NewNode=0: MessageRequester("Memory ERROR","")  :ProcedureReturn 0: EndIf ; if system memory error 
                                    ;    LastNode=PeekL(ListName+8)
    PokeL(NewLast,NodeData)         ; store Data to newly created node
    PokeL(NewLast+4,PreLastNode)    ; Store the Previous Note Pointer
                                    ;    PokeL(NewNode+8,0)         ; Next =0 (not set) , save this step when memory is Allocated as zero 
    PokeL(PreLastNode+8,NewLast)    ; store the curr node pointer on the (previous node next pointer)
                                    ; ***** update Head  *****
    total=PeekL(Head+20)+1
    PokeL(Head+20,total)  ; total element =+1 
    
    PokeL(Head,total) ; current index = total count
                      ; *** Do NOT Change [Self-PTR] , it is permanent
                      ;   PokeL(Head+8,NewNode) ; this is 1st pointer no change
    PokeL(Head+12,NewLast)   ; this curr Last pointer
    PokeL(Head+16,NewLast)   ; Curr position pointer (curr is 1st node)
  EndIf
  ProcedureReturn NewLast
EndProcedure

Procedure.l DeleteNode(ListName)    ; Delete the current node
    Head=ListName
  
;  If IsEmptyList(Head) ;=========== do nothing if link list is empty
  If PeekL(ListName+20)=0    ; [Total Node]=0   ; is empty
    ProcedureReturn 0   ; not success
  Else  ;---------------- Not empty -----------
    
    head_curr= PeekL(Head+16)
    del=head_curr ; pending delete the curr
    head_total =  PeekL(head+20)-1 ; the new total will be minus one after delete any way
    head_index = PeekL(head)    
    head_last = PeekL(head+12)
    head_first = PeekL(head+8)
    
    If PeekL(Head+20)=1 ;****** total = 1 element , so empty after deleted
      head_index=0
      head_curr=0
      head_first=0
      head_last=0
      head_total=0
    Else     ;*********    ; more than 1 element , and delete the curr
             ; store the head data before process ; don't change the [self_PTR] , this is Head Mark
      
      ;      head_total = head_total decrease 1   
      If IsLastNode(Head)   ; at last position , set previous [NEXT] =0
        head_curr=GetPreviousPointer(head_curr)   ; get the one node before the curr node
        head_index = head_total  ; head_total already per-calcalate
        head_last = head_curr
        PokeL(head_curr+8,0)    ; set last [NEXT]=0 at previous , delete the curr (later after endif) 
      ElseIf IsFirstNode(Head)
        old_curr=head_curr
        New_curr  =  GetNextPointer(old_curr)
        PokeL(new_curr+4,head) ; new first node , so [Pre]= head
        head_first  = New_curr
        head_curr  =  New_curr    ; curr pointer change at HEAD
      Else
        ; every thing in between , join the front and back , del the center (Curr)
        ; head total ; no change
        ; head index ; no change ; curr index no change
        old_curr=head_curr
        New_curr  =  GetNextPointer(old_curr) 
        pre_node=GetPreviousPointer(old_curr)
        PokeL(new_curr+4,pre_node)  ; set the next node ref to previous node (skipping the one in between 'del')
        PokeL(pre_node+8,New_curr)  ; set the previous node ref to next node (skip the 'del' node)
        head_curr=New_curr    ; curr pointer change at HEAD
        ;  head_last ; no change
        ; head first ; no change
      EndIf 
      
    EndIf   ; *************  End more than one element 
    PokeL(Head,head_index)
    PokeL(Head+8,head_first);first
    PokeL(Head+12,head_last) ;last
    PokeL(Head+16,head_curr)  ; curr 
    PokeL(Head+20,head_total)  ; total 
    
    FreeMemory(del)    ; delete the old one 
    ProcedureReturn 1 ;head_curr  ; Function Delete success
    
  EndIf ; --------- END not empty ---------
  
EndProcedure
  
Procedure.l InsertNode(ListName,NodeData) ; *** Insert Into , curr node become after
    Head=ListName 
  If PeekL(ListName+20)=0    ; [Total Node]=0   ; is empty
    *InsertNew= AddNode(Head,NodeData)
  Else
    total=PeekL(Head+20)+1
    curr = PeekL(Head+16)  ; get the curr buffet
    Old_pre_store = PeekL(curr+4)
    *InsertNew = AllocateMemory(12)    ; create new node
    PokeL(*InsertNew,NodeData)       ; store data
    ; change pointer new node
    PokeL(*InsertNew+4,Old_pre_store) ; new node [pre] point to before node
    PokeL(*InsertNew+8,curr)          ; new node [next] point to old node (currNode become old node)
    
    ; link the NEW NODE to Infront and After , [infront] [New] [After]
    infront = Old_pre_store+8
    PokeL(infront,*InsertNew)             ; update the node infront of the NEW NODE
    PokeL(curr+4,*InsertNew)              ; Update the node after this NEW NODE
    
    ;*** update Head ***
    PokeL(Head+20,total)    ; total increase
    PokeL(Head+16,*InsertNew)  ; curr become new
  EndIf
  ProcedureReturn *InsertNew
EndProcedure

Global total_travel_distance , best_case, worst_case
Procedure.l SelectNode(ListName, Index)  ;** goto the selected node , if index is > total item , then select the last node , resetlist() is simply goto 1st-node
;If ListName  ; >0  , means is a pointer , else , pointer=0
    Head=ListName
    temp=total_travel_distance  ; temp compute best case
  If PeekL(ListName+20)=0    ; [Total Node]=0   ; is empty
    ProcedureReturn ListName ; do nothing if link list is empty
  Else  ; ******** not empty ********
    
    ; go to the request positon
    total=PeekL(Head+20)
    half=total >> 1         ;total/2  ;= shift 1 bit left is divide , faster  
  ;  half=total /2         ;total/2  ;= shift 1 bit left is divide , faster  
    curr_index=PeekL(Head)
    If Index > 0 And Index <= total  ; ********** valid index **************
;      dis_from_first_node=Index - 1  ; request destiny distance from first node
;      dis_from_last_node=total - Index  ;request distance from first node
      dis_from_curr_node=Abs(curr_index - Index)  ;request distance from first node
      curr_pointer=PeekL(Head+16)
      
      If Index <= half ; ------- seek to the upper half  ---------
                       ; ##**### forward ##**#####
                       ; ##====== Backward ====
      dis_from_first_node=Index - 1  ; request destiny distance from first node (first node = Index 1)
        If dis_from_curr_node < dis_from_first_node  ; ==== travel from current position is shorter then from 1st Node
          If curr_index < Index                      ; **  travel forward to request Index position
            For i = 1 To dis_from_curr_node
              curr_pointer = PeekL(curr_pointer+8)  ; fast get next pointer
            Next
          Else    ; ** If curr_index > Index ; travel backward to request Index position
            For i = 1 To dis_from_curr_node ; travel the difference distance only (curr pos to Destination position)  
              curr_pointer = PeekL(curr_pointer+4)   ; fast get previous pointer
            Next 
          EndIf
          temp=dis_from_curr_node     ; Benchmark check
        Else ; ==== travel form 1st Node is shorter path
          curr_pointer=PeekL(Head+8)  ; start from first node pointer
          For i = 1 To Index-1  ; travel from first pointer to index-1 (1 base ,total travel distance = minus 1)
            curr_pointer = PeekL(curr_pointer+8)  ; get Next node pointer
          Next
        temp= dis_from_first_node     ; Benchmark check
        EndIf
      Else   ; ------- seek to the lower half  ---------
       dis_from_last_node=total - Index  ;request distance from first node
       
        If dis_from_curr_node < dis_from_last_node  ; ** travel from current NODE is shorter then from last NODE
          If curr_index < Index                     ; travel Forward 
            For i = 1 To dis_from_curr_node
            curr_pointer = PeekL(Curr_pointer+8)  ; fast get next pointer
            Next
          Else;If curr_index > Index ; travel backward shorter from curr pos
            For i = 1 To dis_from_curr_node
              curr_pointer = PeekL(curr_pointer+4)   ; fast get previous pointer
            Next 
          EndIf
          temp= dis_from_curr_node    ; Benchmark check
        Else ; travel form first pos is shorter
          curr_pointer=PeekL(Head+12)  ; start from last node pointer and go back
          For i = Index To total-1  ; seek travel from index to last-1 (1 base ,total tavel diff= minus 1)
               curr_pointer = PeekL(curr_pointer+4)   ; fast get previous pointer
          Next
          temp= dis_from_last_node   ; Benchmark check
        EndIf         
      EndIf   ; ---- End  seeking ----
      PokeL(Head,index)
      PokeL(Head+16,curr_pointer) 
      ;temp=total_travel_distance-temp
      total_travel_distance+temp
      If temp>worst_case : worst_case=temp : EndIf : If  temp<best_case:best_case=temp : EndIf   ; compute best case 
;      If worst_case>900
;        MessageRequester("Warning","worst case ="+StrU(worst_case)+Chr(10)+"curr Index = "+StrU(curr_index)+Chr(10)+"Select Index = "+StrU(index)+Chr(10)+"curr travel = "+StrU(temp))
;      EndIf
      
      ProcedureReturn curr_pointer
    Else 
    ;EndIf  ; ***** END VALID request **********
    
      ; **** EEROR ******
      If index > total  ; invalid greater , return last
        last=PeekL(Head+12)
        PokeL(Head,total)   ; set Head to last index
        PokeL(Head+16,last) ; set curr = last
        ProcedureReturn last;PeekL(head+12) ; return last pointer
      ElseIf index <=0
        first=PeekL(Head+8)
        PokeL(Head,1)   ; set head to 1st index
        PokeL(Head+16,first)   ; set curr = first
        ProcedureReturn first  ;PeekL(head+8) ; return 1st pointer
      EndIf
    
    EndIf ; ********END All Request ********
    
  EndIf  ; ******* END check empty *****
  
EndProcedure

Procedure.l FreeLinkedList(ListName)  
  last=PeekL(ListName+12)  ; get last node
  Repeat
    pre=PeekL(last+4)
    FreeMemory(last)
    last=pre
  Until pre=ListName  ; travel delete from the last node backward until we found the head
  ProcedureReturn 0 ; clear the ListName pointer
EndProcedure

Procedure.s DebugHead(ListName,node)
  head=ListName
  DebugH$="DEBUG MSG :"+Chr(10)
;  If IsHeadNode(ListName)  
;    head=ListName
;  Else
;    head=SearchHeadNode(ListName)
;  EndIf
  If head  
;    DebugH$+"DEBUG MSG :"+Chr(10)
    DebugH$+"---HEAD -----"+Chr(10)
    DebugH$+"Index    = "+StrU(PeekL(head))+Chr(10)
    DebugH$+"SELF     = "+StrU(PeekL(head+4))+Chr(10)
    DebugH$+"1st Node = "+StrU(PeekL(head+8))+Chr(10)
    DebugH$+"Last     = "+StrU(PeekL(head+12))+Chr(10)
    DebugH$+" Curr    = "+StrU(PeekL(head+16))+Chr(10)
    DebugH$+"Total    = "+StrU(PeekL(head+20))+Chr(10)
    
    DebugH$+"-------------"+Chr(10)+"NODE ="+Chr(10)
    If node
      DebugH$+"DATA    = "+StrU(PeekL(node))+Chr(10)
      DebugH$+" PRE    = "+StrU(PeekL(node+4))+Chr(10)
      DebugH$+" NEXT   = "+StrU(PeekL(node+8))+Chr(10)
    Else
      DebugH$+" Node info not available !"+Chr(10)
    EndIf
    
  Else
    DebugH$+" No linked list found !!!"+Chr(10)
  EndIf
  DebugH$+Chr(10)
;MessageRequester("HEAD",DebugH$)
ProcedureReturn DebugH$
EndProcedure

;
;----------------------------------------------------------------------------------------------------------------------------------------------------
;
; *******  Test Function   ********
;   --------------------------------------------------------
;       <  >
;  Test 1:  Creat 'myList' And Test Head Node
;  Test 2:  Test Delete on empty list
;  Test 3:  Test Traveling on empty list
;  Test 4:  Test Insert on empty list
;  Test 5:  Test Delete on 1st Node when there is only 1 Node at the chain
;  Test 6:  Test Add/Append New Node on empty chain
;  Test 7:  Test Traveling Entire Chain
;  Test 8:  Test Select Node by Index
;  Test 9:  Test Select Node by 'WRONG' Index
;  Test 10:  Test Insert at last position
;  Test 11:  Test Insert at Middle position
;  Test 12:  Test Insert at Top position with many node at the chain
;  Test 13:  Test Delete at Last Position
;  Test 14:  Test Delete at Middle Position
;  Test 15:  Test Delete at Top Position with many node at the chain
;  Test 16:  Debug [Head] info
;  Test 17 : Free linked list from memory resource
;  Test 18 : Benchmark and Perfomance Test
;
;--------------------------------------------------------------------------------------------------------------------------------------------------
;


;DebugHead(myList,0)




OpenConsole("Doubly Linked List Experiment EP1.RV2")

; Create/Initial chain list
myList=CreateNewList()  ; myList = Head pointer   



; ===========================
;  Test 1:  Creat 'myList' and Test Head Node
Print("-----------------------------------------------------------------"+Chr(10))
Print("---Test 1:  Creat 'myList' And Test Head Node-----------"+Chr(10))
Print("Command:  myList = CreateNewList()"+Chr(10))
Print("          Print( DebugHead(myList,0) )"+Chr(10))
Print("Result :"+Chr(10))
; traveling and  display the linked list
Print(DebugHead(myList,0))    ; display [HEAD] segment
travellist=myList
Gosub SubTravel

;DebugHead(myList,n)


;GuiWait()

; ===========================
;  Test 2:  Test Delete on empty list
Print("-----------------------------------------------------------------"+Chr(10))
Print("---Test 2:  Test Delele with empty list--------"+Chr(10))
Print("Command: (myList is the previous created list , see test 1)"+Chr(10))
Print("          DeleteNode(myList)"+Chr(10))
Print("Result :"+Chr(10))
Print(Chr(10))
Print("(Result is empty list with no elements)"+Chr(10))
DeleteNode(myList)
; traveling and  display the linked list
travellist=myList
Gosub SubTravel



; ===========================
;  Test 3:  Test Traveling on empty list
Print("-----------------------------------------------------------------"+Chr(10))
Print("---Test 3:  Test Traveling on empty list--------"+Chr(10))
Print("Result :"+Chr(10))
Print(Chr(10))
Print("(Result is empty list with no elements)"+Chr(10))
; traveling and  display the linked list
travellist=myList
Gosub SubTravel


; ===========================
Print("-----------------------------------------------------------------"+Chr(10))
;  Test 4:  Test Insert on empty list
Print("---Test 4:  Test Insert on empty list--------"+Chr(10))
Print("Command: (myList is the previous created list , see test 3)"+Chr(10))
Print("          InsertNode(myList,222)"+Chr(10))
Print("Result :"+Chr(10))
Print(Chr(10))
userData=222
InsertNode(myList,userData)
; traveling and  display the linked list
travellist=myList
Gosub SubTravel


; ===========================
;  Test 5:  Test Delete on 1st Node when there is only 1 Node at the chain
Print("-----------------------------------------------------------------"+Chr(10))
Print("--Test 5:  Test Delete on 1st Node when there is only 1 Node at the chain--"+Chr(10))
Print("Command:  (myList is the previous created list , see test 4)"+Chr(10))
Print("          DeleteNode(myList)"+Chr(10))
Print("Result :"+Chr(10))
Print(Chr(10))
Print("(Result is empty list with no outputs)"+Chr(10))
DeleteNode(myList)  ; myList only have 1 element after the previous test , after delete , the list is empty
; traveling and  display the linked list
travellist=myList
Gosub SubTravel



; ===========================
;  Test 6:  Test Add/Append New Node
Print("-----------------------------------------------------------------"+Chr(10))
Print("---Test 6:  Test Add/Append New Node------"+Chr(10))
Print("Command: (myList is the previous created list , see test 5)"+Chr(10))
Print("          AddNode(myList,1234)"+Chr(10))
Print("          For i=100 To 20 Step -27"+Chr(10))
Print("            AddNode(myList,i)"+Chr(10))
Print("          Next "+Chr(10))
Print("Result :"+Chr(10))
AddNode(myList,1234)  ; add 1 node
For i=100 To 20 Step -27  ; add 3 more node 
  AddNode(myList,i)
Next 
; traveling and  display the linked list
travellist=myList
Gosub SubTravel


; ===========================
;  Test 7:  Test Traveling Entire Chain
Print("-----------------------------------------------------------------"+Chr(10))
Print("--Test 7:  Test Traveling Entire Chain----"+Chr(10))
; just show the traveling , it should have 4 element after previous test
; traveling and  display the linked list
travellist=myList
Gosub SubTravel


; ===========================
;  Test 8:  Test Select Node by Index
Print("-----------------------------------------------------------------"+Chr(10))
Print("--Test 8:  Test Select Node by Index---"+Chr(10))
Print("Get the Node DATA of INDEX 3 :"+Chr(10))
Print("Command:  SelectNode(myList, 3)"+Chr(10))
index=3
curr_pointer=SelectNode(myList, index)
Print("Select Index : "+StrU(index)+Chr(10))
Print("Result :"+Chr(10))
Print("Node Data    = "+GetNodeData(myList)+Chr(10))
Print("Function return the Selected valid node ! "+Chr(10)+Chr(10))


; ===========================
;  Test 9:  Test Select Node by 'WRONG' Index
Print("-----------------------------------------------------------------"+Chr(10))
Print("--Test 9:  Test Select Node by 'WRONG' Index--"+Chr(10))
Print("Get the Node DATA of INDEX 19 :"+Chr(10))
Print("Command:  SelectNode(myList, 19)"+Chr(10))
index=19
SelectNode(myList, index)
Print("Select Index : "+StrU(index)+Chr(10))
Print("Result :"+Chr(10))
Print("Node Data    = "+GetNodeData(myList)+Chr(10))
Print("Function return the last traveled valid node ! "+Chr(10)+Chr(10))

;SelectNode(myList,4)
;curr_pointer=InsertNode(curr_pointer,999) ; return the new pointer for curr inserted node
;DebugHead(myList,curr_pointer)

; ===========================
;  Test 10:  Test Insert at last position
Print("-----------------------------------------------------------------"+Chr(10))
Print("--Test 10:  Test Insert at last position--"+Chr(10))
Print(" Select INDEX 4 and INSERT '999'"+Chr(10))
Print(" [curr_pointer] is at last position after previous test"+Chr(10))
Print("Data inserted , Function return the New Pointer "+Chr(10))
Print("Result :"+Chr(10))
curr_pointer=InsertNode(myList,999) ; return the new pointer to curr_pointer
; traveling and  display the linked list
travellist=myList
Gosub SubTravel



; ===========================
;  Test 11:  Test Insert at Middle position
Print("-----------------------------------------------------------------"+Chr(10))
Print("--Test 11:  Test Insert at Middle position--"+Chr(10))
Print(" Select INDEX 3 and INSERT '33333'"+Chr(10))
Print("Data inserted , Function return the New Pointer, chain contain 6 Node now "+Chr(10))
Print("Result :"+Chr(10))
SelectNode(myList,3)
curr_pointer=InsertNode(myList,33333) ; return the new pointer to curr_pointer
; traveling and  display the linked list
travellist=myList
Gosub SubTravel




; ===========================
;  Test 12:  Test Insert at Top position with many node at the chain
Print("-----------------------------------------------------------------"+Chr(10))
Print("--Test 12:  Test Insert at Top position with many node at the chain--"+Chr(10))
Print(" Select INDEX 1 and INSERT '7777'"+Chr(10))
;SelectNode(curr_pointer,1)    ; goto the first node and insert data 
SelectNode(myList,1)    ; goto the first node and insert data 
curr_pointer=InsertNode(myList,7777) ; myList contain the first node/head pointer , after insert , the head pointer was change
Print("Data inserted , Function return the top most Pointer, your initial head pointer was changed "+Chr(10))
Print("Chain has total 7 Node now "+Chr(10))
; in this case , curr_pointer is 1st node pointer , so '  myList=curr_pointer ' also will work as head (first node is actual head)
; traveling and  display the linked list
travellist=myList
Gosub SubTravel


; ===========================
;  Test 13:  Test Delete at Last Position
Print("-----------------------------------------------------------------"+Chr(10))
Print("--Test 13:  Test Delete at Last Position--"+Chr(10))
SelectNode(myList,7)  ; select the last node , there was 7 node in total after the previous test 
curr_pointer=DeleteNode(myList)
Print("Data Deleted , Function return the last node Pointer "+Chr(10))
Print("Chain has total 6 Node now "+Chr(10))
; traveling and  display the linked list
travellist=myList
Gosub SubTravel



; ===========================
;  Test 14:  Test Delete at Middle Position
Print("-----------------------------------------------------------------"+Chr(10))
Print("--Test 14:  Test Delete at Middle Position--"+Chr(10))
Print("Try to delete at Position INDEX 3 "+Chr(10))

SelectNode(myList,3)  ; select the 3rd node ,Index=3 , there was 6 node in total after the previous test 
;MessageRequester("Debug 3rd pointer", StrU(curr_pointer))

curr_pointer=DeleteNode(myList)
Print("Data Deleted , Function return the replaced 3rd node Pointer "+Chr(10))
Print("Chain has total 5 Node now "+Chr(10))
; traveling and  display the linked list
travellist=myList
Gosub SubTravel



; ===========================
;  Test 15:  Test Delete at Top Position with many node at the chain
Print("-----------------------------------------------------------------"+Chr(10))
Print("--Test 15:  Test Delete at Top Position with many node at the chain--"+Chr(10))
;curr_pointer=myList;SelectNode(curr_pointer,1)  ; select the 1st node ,Index=1 , there was 5 node in total after the previous test 
SelectNode(myList,1)    ; select 1st node as curr node

curr_pointer=DeleteNode(myList)  ; delete current node
;myList=SelectNode(curr_pointer,1)  ; get the replaced 1st node pointer 
Print("Data Deleted , Function return the replaced 1st node Pointer "+Chr(10))
Print("Chain has total 4 Node now "+Chr(10))
; traveling and  display the linked list
travellist=myList
Gosub SubTravel



; ===========================
; Test 16 : Debug [Head] info
Print("-----------------------------------------------------------------"+Chr(10))
Print("--Test 16 : Debug [Head] info--"+Chr(10))
Print("Result :"+Chr(10))
curr_pointer=SelectNode(myList,1)

Print(DebugHead(myList,curr_pointer))





; ===========================
; Test 17 : Free linked list from memory resource
Print("-----------------------------------------------------------------"+Chr(10))
Print("--Test 17 : Free linked list from memory resource --"+Chr(10))
Print("Command:  myList=FreeLinkedList(myList)"+Chr(10))
Print("Result :"+Chr(10))
myList=FreeLinkedList(myList)

Print(DebugHead(myList,curr_pointer))

;GuiWait()



; ===========================
; Test 18 : Benchmark and Perfomance Test
Print("-----------------------------------------------------------------"+Chr(10))
Print("--Test 18 : Benchmark and Perfomance Test--"+Chr(10))

max=1000
LOOP=200000
LF$=Chr(10)
total_travel_distance =0 ; Benchmark check
best_case=max
worst_case=0


Print(" Create a new list name ='Test' and add "+StrU(max)+" Element to test"+Chr(10)+Chr(10))


S0 = ElapsedMilliseconds()            

TEST=CreateNewList()
curr=TEST
For t=0 To max   ;    zero base , 1001 element
  ;curr=AddNode(curr,t)       ; initial assign value (better)
  AddNode(TEST,t)       ; initial assign value fast
Next 
 
S1 = ElapsedMilliseconds()    
T0=S1-S0

For j=1 To loop/max
For i=1 To max
  pos=SelectNode(TEST,i)
;  FastSetNodeData(pos,7788)
  b=FastGetNodeData(pos)
Next
Next


S2=ElapsedMilliseconds() 
T1 = S2-S1  

For t = 1 To LOOP;200000
  pos=SelectNode(TEST,Random(max,1))
;  SetNodeData(test,5544)     ; random asign value 
  FastSetNodeData(pos,5544)
Next

S3 = ElapsedMilliseconds()
T2 = S3-S2    


For t = 1 To LOOP;200000
  pos=SelectNode(TEST,Random(max,1))
;  b=GetNodeData(test)       ;random retrieve value
  b=FastGetNodeData(pos)       ;random retrieve value

Next                        

S4 = ElapsedMilliseconds()
T3 = S4-S3

skip:
Print("Elaspse Time to test Linkedlist random seek performance : "+lf$)
PrintN("List size = "+StrU(max)+"   added elements "+lf$)
PrintN("Sequential add Element (fill list): "+StrU(Max)+" nodes")
PrintN("                      Mark        : "+StrU(T0)+" ms")
PrintN("Sequential index Read Data        : "+StrU(LOOP)+" cycles")
PrintN("                      Mark        : "+StrU(T1)+" ms")
PrintN("Randomly seek and asign value     : "+StrU(LOOP)+" loops")
PrintN("                      Mark        : "+StrU(T2)+" ms")
PrintN("Randomly seek and retrieve value  : "+StrU(LOOP)+" loops")
PrintN("                      Mark        : "+StrU(T3)+" ms")
Print(lf$)
Print("Total time use     == :  "+ StrU(S4-S0)+" ms"+lf$)
Print("Total distance travel :  " + StrU(total_travel_distance )+" nodes"+lf$)
Print("Average random search :  "+StrU(total_travel_distance/loop<<1 )+" nodes / Select command "+lf$)
PrintN("Best case travel      :  "+ StrU (best_case)+" nodes")
PrintN("Worst case travel     :  "+ StrU (worst_case)+" nodes")
Print("-----------------------------------------------------------------"+lf$)




;curr_pointer=AddNode(myList,@"This is test string")
;Print(PeekS(GetNodeData(myList)))

;GuiWait()


; ******* End TEST ***************
Print(Chr(10)+">> Press ENTER to Exit <<")
String$ = Input()
End 

; ----------- sub routine to travel list and display all node -------
SubTravel:
If IsHeadNode(travellist) And PeekL(travellist+20)>0 ; Head ok and total >0
  travellist=PeekL(travellist+8);start point to travel from 1st node
  Repeat
    myData=FastGetNodeData(travellist);PeekL(myList)
    getNext=GetNextPointer(travellist);PeekL(myList+8)
    getPre=GetPreviousPointer(travellist);PeekL(myList+4)
    Print("Data = "+RSet(StrU(myData),9)+" |   Pre Pointer = "+StrU(getPre)+"  |  Next Pointer = "+StrU(getNext)+Chr(10))
    travellist  =GetNextPointer(travellist)
  Until getNext=0 
EndIf
Print(Chr(10))
Return