Linked Lists
By: Kevin Picone
About
The following was written to take the user through the basic usage and concepts associated with managing linked lists of Types. The article mostly follows in a top down nature. With the most advanced concepts located towards the bottom. There's various key headings all the way through, so if your already familiar with types then you should be able to skim the headings to brush up on PlayBASIC's implementation.
In a previous tutorial about types, we had running example about storing peoples information (name/address etc). First individuals, then groups of people in a typed array. So in this tutorial, we'll use the same premise, but this time we'll use linked type list rather than array.
I N D E X:
Type's, What are they?
In order to understand Linked Lists, we'll first need to be familiar with User Defined Types. So it's highly recommended that you read through the Types tutorial, before continuing on with linked lists.
Top
What's a Linked List all about ?
In programming, one of the biggest hurdles is often managing information, as typically the more information we have to handle, the more important code design becomes. Moreover, different types of programs tend to require different approaches for managing information.
In game programming, we're typically processing groups of the Characters (I.e. Players, Badguys / Aliens, Bullets, etc), where we'll be frequently adding (When a new character is spawned) and deleting characters when they've died.
Immediately, this sounds like a perfect situation for a typed array (See ArrayBasics), where we'd create various arrays to store the different character types in. This means to add/delete items we need to write our code to manage the size of the array. While this is perfectly fine approach, and one that I often use myself, but there's another way.
A linked List is a mechanism PlayBASIC can embed into type variables. What this mechanism does, is it allows us to hold a series of typed variables all connected (linked) together and access through the single type variable. The beauty of the Linked List is that we no longer have to concern ourselves about the size of the list. Nor do we generally have to worry about manually providing indexes to reference each individual character within our list, like we would when using an array for example. Since it's all handled transparently to the user.
Top
Declaration of a Linked Type List
Before we get the declaration part, first we need to setup a type. So for the sake of simplicity, Lets imagine we wish to store the personal information about a group friends. The collected information might cover the persons first, middle, surname (family) name, home address, phone number, type of employment etc etc. This information will be bound together into a user defined type that we'll called Person
I.e.,
The following code is declaring a type called "Person". This type will hold all of the relevant information about a single person in one place.
; Declare the "Person" user defined type.
Type Person
; These Fields will hold this persons full name
FirstName$
MiddleName$
SurName$
; Phone Number
PhoneNumber$
EndType
|
The code above purely shows the declaration of our "Person" type. We can see the type has four string fields FirstName$,MiddleName$,SurName$ and PhoneNumber$ are contained within this type. At this point we can't really do much with it, we need to create a variable of this type, in order store and retrieve information about our friends.
To declare a type variable with Linked List Support we append the List keyword to end of your variable dimension.
E.G
; Dimension the Friends variable of type Person,
; with linked list support
Dim Friends As Person List
|
So far we've our code doesn't really do anything that we can see. All we've done is declared our user defined type (Person) and declared our Friends list. So at this point the list is empty, so there's nothing to see until learnr how to add people to the list. Which we do via the NEW operator.
Top
Adding New Types to the LIST (the NEW operator)
When we deal with UDT (User Defined types) link lists. The dimensioning process declares the type variable container, but at this point it's empty. To add new types to our list we must use the NEW operator.
What the NEW operator does, is it allocates some memory to hold this type, which we can then assign to our list variable. If you're read the types tutorial this is nothing new, if not, you might want to go back and read the types tutorial first.
E.G
; Dimension the Friends variable of type Person, with linked list support
Dim Friends As Person List
; Explicitly create a NEW person and ADD it to the Friends list.
Friends = New Person
|
(Sample code only)
You're probably no doubt wondering by now, just what all the fuss is about ? - as so far the code is identical to a regular Type Variables. Which is true, but the unlike type variables, when we assign a linked list a new type data, this new type gets added to the head of the list. It doesn't replace whatever was there (if anything), but it is added to the list. So if we assign the a list two new items, the list now contains two individual items. Which you can see in the following example.
In this (Cut and past friendly) example we're declaring our person type, making your Friends list and adding two people to the list.
; Declare the "Person" user defined type.
Type Person
; These Fields will hold this persons full name
FirstName$
MiddleName$
SurName$
; Phone Number
PhoneNumber$
EndType
; Dimension the Friends variable of type Person,
; with linked list support
Dim Friends As Person List
; Add a person to Friends list
Friends= New Person
; The Friends list is now pointing at the newly added
; Person, so lets assign this persons name
Friends.FirstName$ ="Billy"
Friends.MiddleName$ ="Bob"
Friends.Surname$ ="Citizen"
; Add another person to Friends list
Friends= New Person
; The Friends list is now pointing at the newly
; added person, so assign this persons name also
Friends.FirstName$ ="Sally"
Friends.MiddleName$ ="Anne"
Friends.Surname$ ="Stevens"
; Display size of this list
Print GetListSize(Friends())
; display the screen and wait for a key press
Sync
WaitKey
|
If you run this code, you'll see that PlayBASIC returns that there are 2 Person types store in our Friends
This is one of major fundamental difference between working with regular type variables are typed variable lists. As if we assign a regular typed variable a NEW type more than once, the second/third etc times we assign it, PB will overwrite the existing data it's holding.
Top
Retrieving Information From a Linked List
Retrieving information from a linked list type variable is just the same as regular typed variables. So we
simply enter our type name with field in our expression, and PlayBASIC will retrieve this information for you.
e.g. (Cut and past friendly)
; Declare the "Person" user defined type.
Type Person
; These Fields will hold this persons full name
FirstName$
MiddleName$
SurName$
; Phone Number
PhoneNumber$
EndType
; Dimension the Friends variable of type Person,
; with linked list support
Dim Friends As Person List
; Add a person to Friends list
Friends= New Person
; The Friends list is now pointing at the newly added
; Person, so lets assign this persons name
Friends.FirstName$ ="Billy"
Friends.MiddleName$ ="Bob"
Friends.Surname$ ="Citizen"
; Add another person to Friends list
Friends= New Person
; The Friends list is now pointing at the newly
; added person, so assign this persons name also
Friends.FirstName$ ="Sally"
Friends.MiddleName$ ="Anne"
Friends.Surname$ ="Stevens"
; Display the current Friends name
Print Friends.FirstName$
Print Friends.MiddleName$
Print Friends.Surname$
; display the screen and wait for a key press
Sync
WaitKey
|
If you run this example, you'll notice that it only displays one of the two people (Sally) that were added to the list. Why ? - This is because inside the friends list, PB stores a pointer to the 'current' person. So each time we read/write to a friends properties within the list, PB is effectively redirectingly us to the current person. Therefore, In order to display all of the different people contained within our list, we need a method for moving the current pointer through all of the people. For this, we use the For Each /Next looping structure.
Top
Looping Through Lists (For Each / Next)
The For Each /next loop structure is a variation of the For/Next designed for iterating through linked type lists. What this structure does is handles the current pointer within the list. Upon enter the For Each/Next loop the Current Pointer of the list you pass it reset to it's Head position. Each time the loop iterates, the lists current pointer is stepped through the list of available items, until reaching the end of the list where it'll exit and continue on.
e.g. (Cut and Past friendly)
; Declare the "Person" user defined type.
Type Person
; These Fields will hold this persons full name
FirstName$
MiddleName$
SurName$
; Phone Number
PhoneNumber$
EndType
; Dimension the Friends variable of type Person,
; with linked list support
Dim Friends As Person List
; Add a person to Friends list
Friends= New Person
; The Friends list is now pointing at the newly added
; Person, so lets assign this persons name
Friends.FirstName$ ="Billy"
Friends.MiddleName$ ="Bob"
Friends.Surname$ ="Citizen"
; Add another person to Friends list
Friends= New Person
; The Friends list is now pointing at the newly
; added person, so assign this persons name also
Friends.FirstName$ ="Sally"
Friends.MiddleName$ ="Anne"
Friends.Surname$ ="Stevens"
; Display all of the people in our friends list
; When PB hits the opening For EACH statement it
; reset the current item pointer in Friends()
; to it's head object.
For Each Friends()
Print Friends.FirstName$
Print Friends.MiddleName$
Print Friends.Surname$
Print ""
; Each time the loop hits next, PB Moves
; the Friends() current pointer to the next item
; until there's no more items left. Then it exits
Next
; display the screen and wait for a key press
Sync
WaitKey
|
If you run this example it'll display Sally and Billies names. Sally will be the first, since she was last added to the list.
Top
How Do I Delete Items from Linked Lists ?
There are two ways to remove items of a linked list. Which are,
1) Assign the List a NULL - Assigning a list a NULL will tell PB that you wish to the remove the Current object that the list is pointing too. After the object has been deleted, the list pointer will move back to the previous object in the list.
2) You can use the FreeCell command with the index of any cell you wish to delete/free. See the Manual List Processing topic bellow for more information how on that.
e.g. This example deletes the current list item by assigning NULL (Cut and Past friendly)
; Declare the "Person" user defined type.
Type Person
; These Fields will hold this persons full name
FirstName$
MiddleName$
SurName$
EndType
; Dimension the Friends variable of type Person,
; with linked list support
Dim Friends As Person List
; Add a person (Billy) to Friends list
Friends= New Person
Friends.FirstName$ ="Billy"
Friends.MiddleName$ ="Bob"
Friends.Surname$ ="Citizen"
; Add another person (Sally) to Friends list
Friends= New Person
Friends.FirstName$ ="Sally"
Friends.MiddleName$ ="Anne"
Friends.Surname$ ="Stevens"
; Display the number of people in the friends list
Print "ListSize="+Str$(GetListSize(Friends()))
; DELETE the current person from friends list
Friends = null
; Show the Friends list after the delete
For Each Friends()
Print Friends.FirstName$
Print Friends.MiddleName$
Print Friends.Surname$
Print ""
Next
; Display the number of people in the friends list
Print "ListSize="+Str$(GetListSize(Friends()))
; display the screen and wait for a key press
Sync
WaitKey
|
If you run this example, you'll see it only displays Billies name. This occurs because Sally was the last person added to our friends list, as such, she was current person in the friends list. So when we assigned our Friends list a Null, PB will remove whom-ever the Friends list is currently pointing at. In this case Sally. After the delete, the current pointer will be pointing at Billy
Top
How do I know where I am ?
While most of the time knowing our position within the list isn't important to us, since we're not really concerned with what's in the list, we just want to drop objects onto it and process them all individually in a FOR EACH/Next loop.
However, it can sometimes be helpful to get the current position of an object. To do this, we use the GetListPos() function. This this returns the list current index. Moreover, since the objects are linked together we can also look ahead at the next and previous objects, using the GetListPrevious(), GetListNext() functions. You can change the current position using the SetListPos() command.
e.g. This example create a list of two people and then runs through and display the persons names and their list position. (Cut and Past friendly)
; Declare the "Person" user defined type.
Type Person
; These Fields will hold this persons name
FirstName$
SurName$
EndType
; Dimension the Friends variable of type Person,
; with linked list support
Dim Friends As Person List
; Add a person (Billy) to Friends list
Friends= New Person
Friends.FirstName$ ="Billy"
Friends.Surname$ ="Citizen"
; Add another person (Sally) to Friends list
Friends= New Person
Friends.FirstName$ ="Sally"
Friends.Surname$ ="Stevens"
; Show the Friends list
For Each Friends()
; Display current position in the list
Print "List Position="+Str$(GetListPos(Friends()))
Print Friends.FirstName$+" "+Friends.Surname$
Print ""
Next
; display the screen and wait for a key press
Sync
WaitKey
|
If you run this example, you'll see it displays Sally has a list position of 2 and that Billy has a list position of 1. The positions of objects (within the list) will never change until these people are deleted. After deletion PlayBASIC will re-use any freed cells the next time a new object is added to a list.
Top
How do I change my current list position ?
So we now know from the previous section, that we can read the current position from a list using the GetListPos() function, so it stands to reason that we can also change to a new position via the SetListPos() function.
; Declare the "Person" user defined type.
Type Person
; These Fields will hold this persons name
FirstName$
SurName$
EndType
; Dimension the Friends variable of type Person,
; with linked list support
Dim Friends As Person List
; Add a person (Billy) to Friends list
Friends= New Person
Friends.FirstName$ ="Billy"
Friends.Surname$ ="Citizen"
; Get the position of the BILL within the list
BillsPosition = GetListPos(Friends())
; Add another person (Sally) to Friends list
Friends= New Person
Friends.FirstName$ ="Sally"
Friends.Surname$ ="Stevens"
; Get the position of the SAlly within the list
SallysPosition = GetListPos(Friends())
; Call the show friend function with the
; Position of the person we wish to display
; in this case we're passing it the position
; of BILLY
ShowFriend(BillsPosition)
; Next we pass the show friend function
; sallys position
ShowFriend(SallysPosition)
; display the screen and wait for a key press
Sync
WaitKey
; Show Friend function is use show a persons name
Function ShowFriend(ThisListPosition)
; Change the current link in the friends() list
; this person
SetListPos Friends(),ThisListPosition
; Show this persons name
Print Friends.FirstName$+" "+Friends.Surname$
Print ""
EndFunction
|
Top
How do I find the First Item In the List ?
You can retrieve first item using the GetListFirst() function. If the list is empty, GetListFirst will return a -1. Moreover if you're adding/deleting objects to the list then it's important not to assume what the first item is. So it's highly recommended that if you call GetListFirst(), rather than just assume some object is still at the heads of the list.
e.g. This example create a list of two people and returns the display the then persons names and their list position. (Cut and Past friendly)
; Declare the "Person" user defined type.
Type Person
; These Fields will hold this persons name
FirstName$
SurName$
EndType
; Dimension the Friends variable of type Person,
; with linked list support
Dim Friends As Person List
; Add a person (Billy) to Friends list
Friends= New Person
Friends.FirstName$ ="Billy"
Friends.Surname$ ="Citizen"
Print "Billies List Position="+Str$( GetListPos(Friends()))
; Add another person (Sally) to Friends list
Friends= New Person
Friends.FirstName$ ="Sally"
Friends.Surname$ ="Stevens"
; Get the position of the BILL within the list
Print "Sallies List Position="+Str$( GetListPos(Friends()))
; Display
Print "First Item In List ="+Str$( GetListFirst(Friends()))
; display the screen and wait for a key press
Sync
WaitKey
|
Top
Manual List Processing
While generally we'll only need to the use the basic list controls mentioned above. However, there will most list come times where you might just want some more hands on functionality, as such PlayBASIC has various extra list processing functions at your disposal.
Such commands include,
NewList MyList() ; Allocate List for this type variable
ResetList MyList() ; Reset current object index to first object in list
StepList MyList() ; Move the list index to the next item in the list
result=EndOfList(MyList()) ; check if we've hit the end of the list
FreeCell MyList(),Index ; The link you wish to delete
These function can used to replicate the For Each / Next behavior like so.
Example #1
; Declare the "Person" user defined type.
Type Person
; These Fields will hold this persons name
FirstName$
SurName$
EndType
; Dimension the Friends variable of type Person,
; with linked list support
Dim Friends As Person List
; Add a person (Billy) to Friends list
Friends= New Person
Friends.FirstName$ ="Billy"
Friends.Surname$ ="Citizen"
; Add another person (Sally) to Friends list
Friends= New Person
Friends.FirstName$ ="Sally"
Friends.Surname$ ="Stevens"
; Process the List Manually
; Set the Lists Current Index to the FIRST link
ResetList Friends()
; USe a While/EndWhile to process the list
While Not EndOfList(Friends())
; Show this persons name
Print Friends.FirstName$+" "+Friends.Surname$
; Move to the next link in the list
StepList Friends()
EndWhile
; display the screen and wait for a key press
Sync
WaitKey
|
Example #2
You can also use the GetListFirst() / SetListPos() & GetListNext() functions to replicate the same behavior..
; Declare the "Person" user defined type.
Type Person
; These Fields will hold this persons name
FirstName$
SurName$
EndType
; Dimension the Friends variable of type Person,
; with linked list support
Dim Friends As Person List
; Add a person (Billy) to Friends list
Friends= New Person
Friends.FirstName$ ="Billy"
Friends.Surname$ ="Citizen"
; Add another person (Sally) to Friends list
Friends= New Person
Friends.FirstName$ ="Sally"
Friends.Surname$ ="Stevens"
; Process the List Manually.
; Ask this list for the First LINK
ThisLInk=GetListFirst(Friends())
; USe a While/EndWhile to process the list
While ThisLink>0
; Set Friends current to ThisLink
SetListPos Friends(),ThisLink
; Show this persons name
Print Friends.FirstName$+" "+Friends.Surname$
; Ask our list object what the next list is
ThisLink=GetListNext(Friends())
EndWhile
; display the screen and wait for a key press
Sync
WaitKey
|
Top
Manual List Deletion
; Declare the "Person" user defined type.
Type Person
; These Fields will hold this persons name
FirstName$
SurName$
EndType
; Dimension the Friends variable of type Person,
; with linked list support
Dim Friends As Person List
; Add a person (Billy) to Friends list
Friends= New Person
Friends.FirstName$ ="Billy"
Friends.Surname$ ="Citizen"
; Get the position of the BILL within the list
BillsPosition = GetListPos(Friends())
; Add another person (Sally) to Friends list
Friends= New Person
Friends.FirstName$ ="Sally"
Friends.Surname$ ="Stevens"
; Get the position of the SAlly within the list
SallysPosition = GetListPos(Friends())
; USe FreeCell to remove Bill from the list by bills position
FreeCell Friends(),BillsPosition
; Display the People in the friends list
For Each Friends()
Print Friends.FirstName$+" "+Friends.Surname$
Next
; display the screen and wait for a key press
Sync
WaitKey
|
Top
Lets put that knowledge to good use
So that's a crash course in PlayBASIC's Linked List controls. The following is a simple game frame work built around list processing. The frame work doesn't include a player, only a simple object handler for manging the aliens. Which in this case, are going to be some randomly coloured circles.
The example includes object spawning, deletion and even inter object collision. This is where each object in the list checks for impacts against all other objects in the list. Which is one of circumstance where manual list processing can come in very handy. When an impact occurs the objects just randomly flashes and changes direction. Which means some will get stuck on each other.
; Tell PlayBASIC to limit this programs speed to 60 frames
; per second or less.
SetFPS 60
; Declare tObject type to hold the information about our object
Type tObject
x#,y# ; position
Angle# ; Direction object is moving in
Speed# ; speed object is moving at
Size ; Size of this object
Colour ; colour
EndType
; Declare Alien variable as type tObject with linked list support
Dim Alien As tObject List
; Start of Do /loop
Do
; Clear the Screen
Cls RGB(20,30,40)
; Check if the Space Bar was press ?
If SpaceKey()=true
Alien = New tobject
; init it's position
Alien.x#=Rnd(GetScreenWidth())
Alien.y#=Rnd(GetScreenHeight())
; init it's size
Alien.Size=RndRange(10,30)
; init the direction and speed
Alien.Angle#=Rnd#(360)
Alien.Speed#=RndRange#(5,10)
; init it's colour
Alien.Colour=RndRGB()
EndIf
; use FOR EACH to iterate through
; Alien() list and move them.
For Each Alien()
; Get the Speed and direction this alien is moving
Size =Alien.Size
ThisColour=Alien.Colour
Angle# =Alien.Angle#
Speed# =Alien.Speed#
; Calc New X & Y coordinates of this alien
x#=Alien.x# +CosRadius(Angle#,Speed#)
y#=Alien.y# +SinRadius(Angle#,Speed#)
; Check if the Alien has left the screen ?
If PointInBox(x#,y#,-Size,-Size,GetScreenWidth()+size,GetScreenHeight()+size)=true
; Remember the list position of the current alien
CurrentListPOs=GetListPos(Alien())
; Run through the Aliens list and check if we hit another alien
While Not EndOfList(Alien())
; Move to the next alien
StepList Alien()
; Check if our position over laps another alien
If CirclesIntersect(x#,y#,Size,Alien.x,Alien.y,Alien.Size)=true
; if it does change colours and size
ThisColour=RndRGB()
Alien.Colour=ThisColour
; Randomly change he hit aliens direction
Alien.Angle#=Rnd(360)
; Randomly my angle, so object
Angle#=Rnd(360)
EndIf
; Contine the While loop
EndWhile
; restore our original position in the list
SetListPos Alien(),CurrentListPos
; draw a circle to represent this alien
CircleC x#,y#,Size,true,ThisColour
; record the aliens new position/Colour and angle
Alien.x#=x#
Alien.y#=y#
Alien.Colour=ThisColour
Alien.Angle#=Angle#
Else
; This alien is no longer inside the screen bounds
; and has thus moved off the screen. So lets delete it
; from the Alien list.
Alien = null
EndIf
; Continue processing all of the aliens in the list
Next
Print "Number Of Aliens:"+Str$(GetListSize(Alien()))
Print "Press Space To Spawn Aliens"
;refresh the screen
Sync
; Jump back to the DO statement, to keep program running
Loop
|
Top
Where to from here ?
If you've made it all the way through that, then you might want brush over Variables, ArrayBasics, loops, Types, Functions&Psub's & the Images and Sprites tutorial.
Top
|
