Video 1-11: Jumplists

0:03 In the last chapter of this of this long first unit, I want to show you one final attempt at making a randomized list-like structure that does not have these arbitrarily big nodes, uh but rather keeps it to two.

0:19 And that's that's the idea of jump lists. The name is not very specific. I think it's a very little-known data structure, but it's kind of cute. So, maybe you'll agree by the end of this. Uh binary trees, after all, can get away with just two pointers per node if if you don't use parent pointers, right? Just left and right. Uh we should be able to do that as well. But if you want a list that has next pointers, there's only really one pointer left that we can use. Mhm. Let's call that the jump pointer and see what we can do.

0:57 So, um let's keep this hypothetical minus infinity point, the sentinel value. Um it's nice to have this boundary case. And then this has one next pointer for the list in sorted order and one jump pointer somewhere further into the list. And if you have this for the other nodes, the search strategy is kind of clear. You always try to do the long jump. If you can take a big shortcut, that's good. That brings you forward more. And if that's too far, if the element you're searching is less than eight in this case, you start the linear search and go to the next element, but hopefully there you can make another jump. Now, the question immediately becomes for this element one here, what kind of jump pointers should we allow?

1:46 Uh hypothetically, anything behind it could still be a valid target for this pointer one. But really, we don't want it to point behind this other jump pointer. That's utterly pointless. We've already decided by the time we go here, we've already concluded that this is too far. So, why try to jump further than that again? So, you very much want to stay below this jump pointer. They shouldn't ever cross.

2:16 If you explain it this way, I think this is very clear, right? Uh from the offset, it seemed um this wasn't completely clear. Uh but this uh you you definitely want the jump pointers to have this this property of being well nested. So, the general case, uh if you have two jump pointers, either one is inside the other or they're one after the other, of course. For anything after the eight here, again, the whole tail of the list is eligible.

2:54 As a second condition, that's uh so, you may notice um I was involved in this this refinement. There was There was essentially one paper on jump lists that described this data structure and did some analysis. Uh and we continued it a bit. I'll come at the very end to the part that we changed. But, I'll present you the I think sanitized definitions um that we used. So, apart from this well nestedness, which you really want for the jump pointers to make sense, I also want them to be useful beyond the next pointer. So, uh whenever there is um an element that already points to its successor, I don't want a jump pointer pointing to the same guy. That's useless.

3:37 Okay. Um similarly, if you if you look for can phrase it as incoming incoming pointers, if an element already has a jump pointer pointing into it, there's no need to have another jump pointer into it. That can never be useful in a search from the beginning. By the same argument as before. And we should never point to the successor. Does anyone see a problem with these rules?

4:09 They they they both make sense. Uh So, we can try building um a jump list based on these. So, for now I haven't said anything about randomness yet.

4:24 That's right. For some nodes, we won't have any allowed pointers. Yeah. Uh so, this is we'll have we'll have to live with that. Either we give up this non-degeneracy, it's one option. But then we waste the space. Kind of the jump pointers we could do in this case are all useless. Or we live with the fact that there's two types of nodes, the ones with and the ones without a jump pointer. It's uh depending on on your taste what you feel is better. Um This definition already suggests, without telling you how to choose the pointers for now, let's just arbitrarily take some decisions. We could have a jump pointer over here, then for the next element in size, I could choose another one, and it has to be via this uh it has to be from this range. Right? That's the eligible target range for this uh node one to have its jump pointer point to.

5:18 Otherwise, it would violate one of these conditions. And so, we can con- continue. The two can get a pointer here, but here the four node was already the only choice. And poor poor three cannot have a valid jump pointer. So, it will have to go without. Um then five, we can point say to 10. Then we can have a few more in here. But here again, uh there were two options, but with this choice, neither seven or nine can use any sensible jump pointer, so they don't get anyone.

5:55 Same for 11 and 12 anyways. So, I'll call these plain nodes if they don't have another pointer and jump nodes otherwise. With that, it's it's useful to define a few terms that we can then use in the algorithms. If I have some node V, say this one. There's a few lists that are interesting for this node. One is its sublist, which starts at that node including that node and ends well, with the last node that its jump pointer could have pointed to, which is only defined recursively. So, there will be some overarching jump pointer that tells me, ah, eight is out of range for me. I'm not allowed to point there, so it's not part of my sublist for V1.

6:52 Of course, could be that I'm There's no overarching pointer then I go until the very end. And then there's there's after choosing the jump pointer for V1, I have two sublists. The next sublist, which is the list that I would only reach if I use my next pointer. And the jump sublist, which is likewise the one I reach via my jump pointer. Okay?

7:17 Um Do you define do you like double jump, triple jump sublist also? Yeah, of course. Um this V Z um Here we don't have so many we don't have triple jumps. But in a way, V1 could double jump down to this this list here, right? But that is then V4's jump list, and so it's enough to do one step. By doing one step, you reach a new head. So, V1 um did I have a Is the header of this sublist? So, after following one pointer, I have a new header, and that has a new sublist, and it's new next and jump sublist. So, that's enough.

8:04 Question? Yeah. Yeah. You look at the node. Mhm. How do we How do we know the end of like an overarching pointer that skips over it because it obviously the node itself is only the pointer directly forward and one pointer. So, wouldn't we have to examine the entire list to then find that structure? That's right. The question was, how do we know uh where this sublist ends? Right? It's only defined recursively. So far, it's only a definition. You can, of course, follow from from the header of the total list, you can work it out recursively. But from the node itself, if I if you're If someone drops you uh you're blindfolded and then dropped on this node, there's no way for you to know where this ends. In particular, an incoming jump pointer you don't know about, right? There's some guy having your memory address. You don't know about that. Uh as you'll see, we don't need to ever figure this out. If we ever need to, we can learn it recursively. So, we already have the information available.

9:10 Okay, so here just just keep this picture in mind. Um I should also mention uh at each point in time, the header is an element that may store a key, like here V1 is an actual proper node element list node uh that stores some some key. But for its sublist, I'm going to treat this key as nonexistent. The header of a list always serves as the sentinel only, and if it has a key, it's ignored. It's not part of this sublist. With the understanding that if I would have to find this key, I need to deal with this at some uh outermost outer recursive call.

9:51 Okay. Now, we can uh define so far I haven't said how we choose jump pointers. One option is random. So, specifically I'll just call them random jump lists, but really you should think of them as uniform wherever possible. Uh and outside-in. So, we pick the jump pointer of the header for the entire list. And that's done uniformly at random from all its eligible targets, which are it's a bit weird if the list is overall um n keys, it has n plus one nodes because the header is not storing a key, and n minus one eligible targets. Now, these weird little offsets, they come from this non-degeneracy condition. Um they make the model a tiny bit different, but uh in a non not very consequential way. So, you choose this uniform from all possible options, and then you have recursively a next in a sub and a jump sublist. And on those you do the same.

10:58 Again, from all the eligible options uniformly. Uh here's the picture again to remind you. Um The header here doesn't contribute to the stored keys, but it has a jump pointer into this this blue range, the sampling range, which is uh here I'm I'm always using m for the number of uh nodes in the sublist and n for the number of keys is of course almost the same but I I thought it's rather helpful to be super explicit that the two are not identical even though it's just a plus minus one. The probability of one specific configuration of the jump list is a bit like for the binary search trees you can express this recursively. Uh if the jump list is too small to have a jump pointer for the head for the header then there's only one shape and that shape will have probability one of occurring because there's nothing to choose. And if it's uh not boring if there is a jump pointer for the header then we have m minus two options for that pointer where it should go. So we pick one uniformly at random and we continue recursively so we multiply with the probabilities for the the choices we made in these subproblems.

12:37 Okay? This is very similar to the formula that we had for random binary search trees a while ago where we said the uni- the root is picked uniformly at random and then the left subtree and right subtree have recursively the same probability. And there you could express it even in a different way but we don't don't need to here. Uh okay. If you would draw a random jump list from this distribution it could for example look like this. So here's the backbone. This was um Mathematica's automatic layouting of graphs so it decided to put it in this slightly strange shape. Um but one thing that's essentially obvious from just how we define things, this outermost this outermost jump pointer will usually point roughly in the middle of the list. Because, well, we chose it to be like that. We chose it uniformly. So, it can go anywhere, but like in a random binary search tree, uh if you have many of these independent uniform decisions, many of them are roughly in the middle.

13:51 Say the the middle half of positions. All right.