The course is part of this learning path
In this course, we begin building a game in Solidity, and more specifically, we begin to look at defining the mechanics and the components of the game.
Okay, let's talk about how we are going to implement this linked list in our smart contract for our Highscores. This is how a linked list could look like. So, we have a couple of elements, and in our case, that's going to be addresses and they are having in this mapping to our struct data type, they're having the number of wins, but in addition to what we already defined, we're going to add an address to the next element and from the next element back to the previous element. So, in our struct, we have the number of wins stored. We're adding two addresses that either from this point of view pointing back to the previous elements, so to the top position number one, to the higher element, and to the next element, to the lower one in the list. So, when we know our Highscore holder here, then we can easily go to the number two following the addresses. So, we can go from number two to number three, from number three to number four to number five to number six to number seven, eight, nine until we hit number 10. So, we can always seek through this list, and if we have somebody who wins something, we can find the right position where we have to either take it out or move to the top number two around. So, let's give you an example. We have on our top position, number one, we have an address that one, five times, on top position number two, in our top 10 list number two, we have someone who won four times. In the position number three, we have someone who won three times. And on number four, we have someone who won one time and that's it. We have nobody else playing this game yet. So, we only have four people in our top 10 list. Now, let's assume that we have a new winner. The person on our position number two in our top 10 list one another time, and now he's a number of wins counter incremental to number five. So, he had five wins, which is the same as the number one here. So, he would actually have to switch places here. It's easy for us to judge when we have the, the full picture here, but, if you want to do it in a programmatic way, it's getting a little bit more complicated. First of all, we have to find the position where he would now be the new Highscore holder or in our top 10 list. So, ideally, we start with a Highscore holder and it seems like our first hit in our list where we start is already the place where this person now belongs to. So, what are we going to do? First of all, we're going to detach him. We're going to take him out of the list totally. We are going to set the lower address of the number one to the number three and the higher address of number three to number one. So, if we would just look at this picture, then our Highscore list would have now three elements: one, two and three. But we are going to reattach him in a second, so during the same transaction so that this would make sense. The next thing is we are going to assign our element that we are going to reattach into the list the right upper and lower bounds meaning we are putting him under the right position and in our case he's going to be the new Highscore holder. He's going to be our new number one, so there's nobody higher than him. There's only somebody lower than him. So, like this element here pointing to the previous one, our new one here pointing to the last top number one. Now, there's just one thing missing that is having this here pointing back to the new number one. So, in our case, we end up with two new links between our elements going back one and going forward one. Okay, then the last thing that we have to change here is that this one is not number two anymore. This one is number one. That means they are basically switching positions but that is only a formality because it's automatically given by our highscore holder. So, if our first element that we found in the linked list is the highscore holder, then we are setting the new highscore holder for the address that just one. All right. There is enough theory for here. Let's get some hands on and let's get to work. All right. In the previous short video, you saw how we do this in theory and now we are going to implement this in practice, which means we have to extend our struct here in order to point to the different positions in our Highscore list. So, ideally, all we have to do is we have to add an address, lowerHighscoreAddress and an address higherHighscoreAddress. And those are going to be populated with the different positions in our top 10 list and that's going to be determined in our addWin functionality. So, we're going to change this slightly. We don't have just a top one position. We're going to have a top 10 position. So, we have to basically remove this and then we have to think of a couple of cases. The easiest one is going to be our top 10 list is yet empty. There is nothing inside there yet and we have no highscore holder, and that's the easiest one. If our highscoreHolder is the address zero, then we have no highscore holder yet. Then our highscoreHolder is the address that we're just adding here and we are finished because we have no other elements, our higher and lower highscoreAddresses are all empty. There are all zero addresses. There is nothing to add, nothing to shift around, nothing to remap. On the other hand and here gets a little bit more interesting we have more than one where we have one person or more than one person in our Highscore list. Then we have to run through the list until we are either at the position number 10 where it's finished or we are at the position where we have now an higher number of wins than the person in our Highscore list, then we have to remap our item in there. Or we reach a position where the address of our Highscore list is or the lower address of Highscore list is the address zero. Before I'm talking too much, let's get down to business and let's start programming. So, first of all we have something like a pointer that points to the current address. So, let's call this current position and that is the highscoreHolder. And addresses are value types. If you write here into the current position, the new address, it will not overwrite the highscoreHolder here which is good to know in case you're working with reference types. If you rewrite something in a reference type, then you're overwriting actually the original entry on the storage position. Then we have to go 10 times through our list. So, we have to have something like a counter which is zero by default. And while that counter is smaller or equals than 10, then walk through our list. The first thing our counter is doing, it is going to be incremented every time we walk through the counter and our current position is the highscoreMapping of the current position, the lowerHighscoreAddress. So, if we are going through our while loop here, we are always assigning the current position to the next position in our mapping. And that is achieved by having this reference in our struct. So, we have one item that has a lowerHighscoreElement and that points to the next item in the top 10 list. And so on so we can go on. So, the next thing that we have to find is if our item in our list that we are just currently looking at has a lower equals number of wins than our current person that just won. So, if we have the highscoreMapping of the current position, number of wins is small or equals than the highscroreMapping for the person that just one number of wins. And obviously, our current position is not the item or that the person that we are just trying to enter the win in our top 10 list, then we have to first detach the item then assign the right upper and lower bounds and then we reattach item inside the correct position. And if necessary, we assign a new highscoreHolder, that is, if the count is zero. Detaching the item is very easy, that is, if the highscoreMapping is already in our top 10 list. That means if the lower address is not the address: 0, then take the highscoreMapping. The lower address, the one that is the next element and assign it to the higher address in our mapping, where the element is just currently in. So, we have to detach it. We have to take it out. We have to merge the higher and the lower one together so that our entry is not existing in the list anymore. Well, that is the higherHighscoreAddress. So, what is the problem here? If the highscoreMapping for higherHighscore address is the... One that, we have in our mapping and then... Now let me copy this. If our higherHighscoreAddress, then you have to assign the higherHighscoreAddress. lower thing to the... So, we have to take it out. We have to take our lowerHighscoreAddress from the current item to the lowerHighscoreAddress from the higher item, so they are merged together. This is the detaching, so our item does not exist in the list anymore. Now we assign the right upper and lower bounds to the item and that means that our highscoreMapping for the lowerHighscoreAddress is going to be the current position. And the reason for that is, we found a position which is going to be replaced by the current item. So, definitely, the lowerHighscoreAddress of our current item is just the position that we hit in our top 10 List.
And now it gets a little bit complicated. If the highscoreMapping current position is not the address 0. And we set the highscoreMapping. So that's just another double check here. We are not talking about the same item that is in our, that we're just trying to put into the list then the... Our complete here is annoying. Then the highscoreMapping for; higherHighscoreAddress is the highscoreMapping. Current position; higherHighscoreAddress. And the reason for this is now we are going to put our current items place into the position that we are replacing from the item before. And obviously, that is pointing maybe if you're not having the first element but maybe the second or third element. Maybe that's pointing to another element on the left side on the higher side in our list. So, we have to put our item into that list and let it point to the higher item. Or else we have detached maybe the first or second item from our list. And if it's the highest item than the highscoreMapping for highscoreaddress is the address 0. So, if you have the top number one item in our highscore list, then we have no higher item, we have the highest item now, and then that's it.
So, the last thing that we have to do is really from the list perspective, is to reattach the item inside the current position. And that means if our highscoreMapping current position... and the highscoreMapping... And that is a lot of mappings now... So, we take the item, which is the next item, and then let it point to this item. And we have our current item, higherHighscoreAddress, and that must be the item that we just replaced. Now, here is little coding challenge, and that shouldn't hopefully be too much. First of all, we have here return. We don't continue here. Here's a little coding challenge. If we have the top one position, then we have to assign a new highscoreHolder, or else this highscoreHolder here will afterwards point to the position number two in our list. So, if we just replace number one, then we also have to replace the highscoreHolder here. And that is something that you have to do here. It should be fairly easy, once you understood how these things work. In case you want to study how these things work and not just trust the code that I'm just writing, then there is a good idea just to replace this only game manager modifier and just play around with the HighscoreManager self-deployed. A HighscoreManager, add a couple of highscores for addresses, and let you give back the top 10 high scores, which we haven't done yet. We're going to do this in the next lecture. But in that case, you can always drill into the transaction with the debug button and check out what the values are of the different elements.
It's a fairly good exercise if you want to get into the debugger, or else you just trust me on this part of the code, which is replacing an item. And the last part of replacing an item is if you have the top 10, the number one in the top 10, then you should also replace the highscoreHolder. So, if you want to do this coding challenge, then pause the video now, or else I will show you in a second how this is done. It's not too hard , and I'm sure there are hundreds of ways to do it, and I chose to do it. If the counter is 0, then we have the first element in our iteration, then our highscoreHolder is the new element. So, there's one last thing which is to do this has nothing to do with finding the right position. The thing is, if our position that we are in our top 10 list is already the address 0, then we can just add our element in and let it point to the next one, and the next one point back to this one. So that is if our highscoreMapping; current position; lower address is the address 0. So, we already reached the last element in our top 10 list. So, if you have only five, then this could be our sixth element now that we are trying to enter. And our current position is not, this element that we are trying to add. Then we are going to detach our item again just in case. And then we say the current position, our address, is the current address that we're trying to add and... ScoreMapping higher address is the current position, and the highscoreMapping for lower address is the address 0. So, we just added an element at the end of the top 10 list in case there are not enough elements yet in the top 10 list. So, we have maybe just adding the fifth player or sixth player. This was a fairly long lecture, and I'm sure it's very exhausting to read all this quite complicated code. And in the next one, we are just giving it a try and seeing if we can implement the top 10 list and return the top 10 players. And then play our game and see if that works out correctly.
Tom is a CTO, senior back-end developer, and systems architect with over twenty years of hands-on development experience in a variety of languages and systems. He has a CS master's degree and has been working with Ethereum and blockchain technologies since 2016.