feel free to test the code or use it if needed.
Any comment welcome ^.^
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
