Linked Lists -

[kevin]

Note:  This Code requires PlayBASIC V1.10 (or newer) to run correctly, will most likely crash in older versions.



Linked List Module

PlayBASIC Code: [Select]

; ==============================================================
;  Define the 'Parent' Link List elements
; ==============================================================

 Type tList
     NextLink
     PreviousLink
     FirstUsed; only seeded in element zero
     FirstFree; only seeded in element zero
 EndType

; 
; Dim List(0) as tList



; *=--------------------------------------------------------------=*
;           >> Init linked List <<
; *=--------------------------------------------------------------=*
;  Element zero is used to house the list properties (first/free)
;  all other elements are linked forward andback.  upon creation
;  elemented 1 through to the Maxsize will be linked as FREE
; *=--------------------------------------------------------------=*


Psub InitList(Me().tlist,MaxSize)
   Dim me(MaxSize) as tlist
   me(0).FirstUsed=0
   me(0).FirstFree=1

   For lp=1 to MaxSize
  me(lp).PreviousLink  =lp-1
  me(lp).NextLink     =LP+1
   next
; set the Next link in the last item to null
   me(lp).NextLink =0
EndPsub


; *=--------------------------------------------------------------=*
;           >> Show List<<
; *=--------------------------------------------------------------=*
; this is just debug function which shows the linking of each element
; *=--------------------------------------------------------------=*

Psub ShowList(Me().tlist,Size)
   print "First USED:"+str$( me(0).FirstUsed)
   print "First FREE:"+str$(me(0).FirstFree)
   For lp=1 to Size
  print "item"+str$(lp)+"  Prev"+str$(me(lp).PreviousLink)+" , Next"+  str$(me(lp).NextLink)
   next

   ThisItem=me(0).FirstFree
   s$=""
   While ThisItem>0
  s$=s$+Str$(Thisitem)+","   
  ThisItem=me(ThisItem).NextLink
   endwhile
 print "Free List:"+s$

EndPsub


; *=--------------------------------------------------------------=*
;        >> Get The First Element the List <<
; *=--------------------------------------------------------------=*

Psub GetFirst(me().tlist)
; Get the current first item
  ThisLink=me(0).FirstUsed
EndPsub ThisLink


; *=--------------------------------------------------------------=*
;              >> Get a NEW Link  <<
; *=--------------------------------------------------------------=*
;  This functions grabs a free element from the free list.
; *=--------------------------------------------------------------=*

Function NewLink(me().tlist)
   FirstFreeLink  =me(0).FirstFree

; ===========================
; Check if link is full
; ===========================
   if FirstFreeLink<>0

; unlink the free item from the free list
;  PreviousFreeLink       =me(FirstFreeLink).PreviousLInk
  NextFreeLink      =me(FirstFreeLink).NextLInk
  me(NextFreeLink).PreviousLInk   =0

; Get the current first item
  FirstUsedLink   =me(0).FirstUsed

; if not first the set the old first link to point back at the new one
  if FirstUsedLink<>0
  ; adjust Back link of the old first item
    me(FirstUsedlink).PreviousLink=FirstFreeLInk    
  endif   

; init the new cells previous and next links
  me(FirstFreeLink).previouslink   =0
  me(Firstfreelink).nextlink     =FirstUsedLink


  me(0).FirstFree   =NextFreeLink
  me(0).FirstUsed   =FirstFreeLink

; Bump the 
   endif

EndFunction FirstFreeLInk
 


; *=--------------------------------------------------------------=*
;              >> Delete Link  <<
; *=--------------------------------------------------------------=*
;  This function deletes a link and returns it tot eh free list.
; *=--------------------------------------------------------------=*



Psub DeleteLink(me().tlist,ThisItem)

   FirstFreeLink  =me(0).FirstFree
   FirstUsedLink  =me(0).FirstUsed


; Get the pervous and next links from this item
   PreviousItemLink   =Me(ThisItem).PreviousLInk
   NextItemLink  =Me(ThisItem).NextLInk

; Check if the frist link is being deleted
   if FirstUsedLink=ThisItem then me(0).FirstUsed=NextItemLink     


; Link Previous item forward to then Next item
   If PreviousItemLink<>0 then Me(PreviousItemLink).NextLink=NextItemLink
   
; Link Next item back to the Previous item
   If NextItemLink<>0 then Me(NextItemLink).PreviousLink=PreviousItemLink   

; Add newly unliked item to the head of the FREE list
   Me(ThisItem).NextLink=0
   Me(ThisItem).NextLink=FirstFreeLink  
   

Login required to view complete source code