Creating a Linked List with Sibling Objects

Linked lists are just one of the many things siblings are useful for. In it's most basic form a linked list is a collection of items that each contain a reference to the next item. Linked lists are used in many familiar data constructions.


Collections allow for dynamically adding, inserting and removing objects but linked lists are an efficient way of tracking similar objects that are spawned randomly across the screen. To illustrate this we'll modify the Star copying project from Dynamically Creating Sibling Objects. To do this save the Star copying project under a different name. Now use the reset script to clear the sibling Star copies and start over.

Steps

This time we'll get the world object to track the first and last star created. Right click on the world Object and click on the blue eye icon.  We need to create two new player type variables. Variables are created by clicking the light brown down arrow on the top bar of the viewer. Name the variables firstStar and lastStar. If you forget to set them to player type or name them, modify them using the menu icons on the left side of the variables category.

We only have one star available so click on the value boxes in the viewer and select the Star object with the cross hair for both variables. The firstStar variable must be created in an object other than Star to prevent the copies from updating it with their own value. We want the firstStar variable to remain constant.

Star reset script

Now drag the "world's firstStar" and the "world's lastStar variables' to the reset script by the assignment icon just to ensure these variables are properly set whenever we delete copies and start over.



 

We need one more player type variable in the Star object to store a reference to the next star. References in linked lists are usually called nodes so we can call it nextNode. Now somewhere in our scripts we need to assign an object to it that hasn't been created yet.





This where the world variable lastStar comes in. Get out a new script from the World object viewer and call it makeStars.

Drag out the Star's spawn script tile from Star's viewer and drop it in the new script.
 

world makeStars script

Now replace Star's with the tile for the lastStar variable. This means whenever makeStars is run the spawn script belonging to the player assigned to lastStar will run.

Star spawn script

We now have to make some changes in the Star's spawn script. If each copy is spawning the next copy we no longer need the increment variable to set the x axis location. Remove the tile that increases the xIncr variable.
 
Get a number tile out of the gold box, replace the xIncr variable tile with it and set it to 140.

Star spawn script

Now open the World viewer and drag the lastStar variable tile out by the assignment symbol. Replace the value with the newStar variable tile from the Star viewer.
 
Drag out the nextNode variable and assign variable newStar to it too.




Everytime makeStars runs,  the spawn script runs in the object that the lastStar variable is assigned to.  A copy is assigned to  the newStar variable in that object, the copy gets a random color, gets moved 140 pixels right along the x-axis and then  the copy is assigned to the lastStar and the nextNode variables in the object represented by lastStar. Make few stars and look at the values in the viewers for the World and the stars. firstStar's value should still be the original star because it was assigned once in the World object and not in any of the sibling stars. lastStar's value should be the last star in the row. Each Star object should show the next copy in the list as the value for nextNode unless it's the last star.

 

Count the Stars

 

If everything has worked out with our scripts we should now be able to work with our linked Star objects. Counting them is the simplest to illustrate.

Open the World viewer and create a number type variable called sCount (count is reserved for collections).

world startCount script

Drag out sCount by the assignment icon and set it to 1. Call the resulting script startCount.




We are going to use recursion for this. This means we'll use a script that calls itself somewhere in the script.

Get out another script, name it countStars, open the script editor menu options icon and select add a parameter. Use the up/down arrows to the left of the parameter to set it to type player.

world countStars

If we make sure that the nextNode variable in the last star is set to dot   we can use dot to test if the script has reached the last star. Drop a test tile on the countStars script.In the test section, drop the nextNode variable tile from the Star's viewer. Click on the parameter and there should be a player tile stuck to the mouse cursor. Replace the star name tile with the player tile. The statement should read "Test player nextNode = dot".

Star reset script

Drag another "nextNode" variable tile by the assignment symbol to the reset script. Drag out the "world's lastStar" variable tile from the world viewer and replace "Star" with it. Go to the Supplies flap and drag out the Players Tool. The Players Tool displays all the player objects in the world. Click on the menu icon on the left of the dot object and select tile for this object. Drop the "dot" tile on the value on the right of the "lastStar nextNode" assignment statement. This way we can be sure that the last star's nextNode variable will be set to dot and the recursive loop will be able to meet it's stopping condition.

world countStars script

Now go back to the world countStars:dot script. Leave the yes branch blank because if that is true we can stop counting as there are no more Star objects.

Get the sCount variable from the World viewer by the assignment symbol and drop it into the No branch. Set it to increase by 1.

Now drag out the world "countStars:dot" script tile and drop it underneath the "sCount" assignment statement inside the No branch.

Get another nextNode variable from one of the stars and replace the parameter tile in the statement with it.

Click the parameter box on the script editor menu to get another player tile and replace the star's name with it. This statement should read "World countStars player nextNode".
   

world startCount script

Drag out the "world countStars:dot" script tile again but drop it in the startCount script this time. Replace the parameter tile with the firstStar variable tile from the World object. Make sure to save before running this script in case something goes wrong. Run startCount and check the sCount variable.

So what is going on here? This example demonstrates a process known as traversing a list using recursion. The startCount script initializes the counting variable and calls the countStars script passing it a reference to the first star in the list. The countStars script assigns this object to the player variable. The test tile checks the value for the nextNode variable inside that object. If it is equal to dot nothing more happens and the script stops because there are no more Star objects in the list. If the nextNode value is a Star object then the tiles in the No branch execute. The sCount variable value is increased by 1 and the countStars script is called again but is passed a reference to the object assigned to nextNode which should be the next star in the list. The script will repeat until the player nextNode variable equals dot.The sCount variable should equal the number of stars in the list.


Of course you could also count the stars at time of creation. By giving objects unique values, you can use these techniques to locate objects by testing for values and issue commands to them or change their properties. If you want to remove an object, you'll have to make sure to reassign the preceeding object's nextNode value. The countandremovestars.007.pr project file demonstrates how to remove the last Star object in the list. This file can be downloaded from my GitHub repository. Save it to your Etoys directory and load it into Etoys.

Although recursive processes, referencing objects and traversing lists are common programming tasks, they aren't the easiest to understand. Hani Awni's SnakeSpawn project at Etoys Illinois was my guide. This is an excellent example of how linked lists can be used in games.



Last Updated  January 30, 2017.