1 00:00:00,420 --> 00:00:05,910 [Music] 2 00:00:09,920 --> 00:00:16,000 Welcome back to education everybody. I 3 00:00:12,960 --> 00:00:18,320 get the great honor of introducing Izzy. 4 00:00:16,000 --> 00:00:20,480 This is Izzy. Izzy is a secondyear 5 00:00:18,320 --> 00:00:22,480 software engineering student at UTS. 6 00:00:20,480 --> 00:00:24,400 Currently volunteers coordinator for 7 00:00:22,480 --> 00:00:27,359 PyCon AU. I think we get a little round 8 00:00:24,400 --> 00:00:29,279 of applause for that one. 9 00:00:27,359 --> 00:00:31,119 Uh, and so you've probably already seen 10 00:00:29,279 --> 00:00:32,719 her today. Uh, she's the administrator 11 00:00:31,119 --> 00:00:35,120 for the girls programming network. As 12 00:00:32,719 --> 00:00:37,360 well as being a tutor/room leader and 13 00:00:35,120 --> 00:00:39,760 intrinsic to the national content 14 00:00:37,360 --> 00:00:41,440 creation team. She coaches at a maker 15 00:00:39,760 --> 00:00:43,040 space and robotics team for upper 16 00:00:41,440 --> 00:00:45,840 primary age students. She drinks too 17 00:00:43,040 --> 00:00:48,160 many energy drinks. Uh, she gamifies 18 00:00:45,840 --> 00:00:50,480 meeting people by collecting LinkedIn. 19 00:00:48,160 --> 00:00:51,950 So, hit her up in the breaks. Thank you 20 00:00:50,480 --> 00:00:55,520 very much, Izzy. 21 00:00:51,950 --> 00:00:57,680 [Applause] 22 00:00:55,520 --> 00:00:59,680 Okay, so the title of this talk is data 23 00:00:57,680 --> 00:01:02,000 structures a learning journey. I came up 24 00:00:59,680 --> 00:01:03,600 with this title a while ago and then 25 00:01:02,000 --> 00:01:05,439 somebody told me a much better title. So 26 00:01:03,600 --> 00:01:07,520 that is now the subtitle. 27 00:01:05,439 --> 00:01:10,560 Self-inflicting first principles of data 28 00:01:07,520 --> 00:01:12,320 structures for learning purposes. 29 00:01:10,560 --> 00:01:13,680 Now I spent too long on this animation 30 00:01:12,320 --> 00:01:15,620 so you're all going to have to be really 31 00:01:13,680 --> 00:01:17,180 impressed by it. 32 00:01:15,620 --> 00:01:20,629 [Applause] 33 00:01:17,180 --> 00:01:20,629 [Music] 34 00:01:21,200 --> 00:01:25,520 Oh my god, I love 35 00:01:23,260 --> 00:01:28,000 [Applause] 36 00:01:25,520 --> 00:01:31,040 Who am I? Well, you were just told, but 37 00:01:28,000 --> 00:01:33,759 I am Izzy. I'm 19. 38 00:01:31,040 --> 00:01:36,799 That's me. That one is not me. Oh, I 39 00:01:33,759 --> 00:01:39,840 went backwards. That one's not me. 40 00:01:36,799 --> 00:01:41,680 I am very into music. I think my 41 00:01:39,840 --> 00:01:46,560 analytics from last year said I listen 42 00:01:41,680 --> 00:01:48,880 to 60,000 minutes. Um, that is 41 days 43 00:01:46,560 --> 00:01:53,040 straight. I have calculated it. That's 44 00:01:48,880 --> 00:01:55,040 about a ninth of the time in the year. 45 00:01:53,040 --> 00:01:59,280 Yeah. 46 00:01:55,040 --> 00:02:01,680 Um again, yes, I am very mildly into 47 00:01:59,280 --> 00:02:03,759 energy drinks. Um I don't have any stats 48 00:02:01,680 --> 00:02:06,159 for this one, but I should come up with 49 00:02:03,759 --> 00:02:10,080 some for next time because they would be 50 00:02:06,159 --> 00:02:11,440 high. Um I think I'm fine, but my 51 00:02:10,080 --> 00:02:13,120 parents apparently think I have a 52 00:02:11,440 --> 00:02:15,840 problem. 53 00:02:13,120 --> 00:02:17,599 I spend my time teaching several 54 00:02:15,840 --> 00:02:20,400 different students in several different 55 00:02:17,599 --> 00:02:21,760 capacities. So again, I'm part of the 56 00:02:20,400 --> 00:02:23,440 girls programming network, which you 57 00:02:21,760 --> 00:02:25,520 might have heard of before and was just 58 00:02:23,440 --> 00:02:28,959 referenced. Um, we teach free coding 59 00:02:25,520 --> 00:02:30,879 courses for girls uh once a term. I went 60 00:02:28,959 --> 00:02:33,120 as a student for nine years, and so I'm 61 00:02:30,879 --> 00:02:35,280 now a tutor now that I've graduated. So 62 00:02:33,120 --> 00:02:37,040 that's two years of being a tutor, but 63 00:02:35,280 --> 00:02:39,519 I'm also their administrator, so I do 64 00:02:37,040 --> 00:02:42,080 all their emailing and flights and 65 00:02:39,519 --> 00:02:43,840 paying and do a lot of stuff. There's a 66 00:02:42,080 --> 00:02:47,440 lot of things. I write content for them 67 00:02:43,840 --> 00:02:50,080 and I tutor for them once a term. I also 68 00:02:47,440 --> 00:02:53,120 do robotics. I teach robotics at a 69 00:02:50,080 --> 00:02:55,599 school and other things, 70 00:02:53,120 --> 00:02:57,280 but mostly robotics because the other 71 00:02:55,599 --> 00:03:00,879 people don't want to pay attention to 72 00:02:57,280 --> 00:03:03,360 me. That's fine. Anyway, I recently did 73 00:03:00,879 --> 00:03:07,440 an internship and that leads us to a 74 00:03:03,360 --> 00:03:11,040 couple months ago. Here is the story. So 75 00:03:07,440 --> 00:03:14,640 I was in this internship um it was more 76 00:03:11,040 --> 00:03:16,959 than a couple months ago now but um we 77 00:03:14,640 --> 00:03:18,239 were mostly I was doing JavaScript tests 78 00:03:16,959 --> 00:03:19,840 so I wasn't really doing anything 79 00:03:18,239 --> 00:03:22,480 important but there was some really 80 00:03:19,840 --> 00:03:24,720 intense code in the background that I 81 00:03:22,480 --> 00:03:26,800 wasn't really being told about but my 82 00:03:24,720 --> 00:03:29,120 boss was trying to like help me learn 83 00:03:26,800 --> 00:03:30,400 things and so to do that one day when we 84 00:03:29,120 --> 00:03:32,400 were at lunch he was telling me about 85 00:03:30,400 --> 00:03:34,720 how some of the other code worked and he 86 00:03:32,400 --> 00:03:36,959 told me about this data structure um 87 00:03:34,720 --> 00:03:38,319 that we were using and I didn't really 88 00:03:36,959 --> 00:03:42,159 understand what he was saying. He tried 89 00:03:38,319 --> 00:03:45,280 to explain it several times. He tried uh 90 00:03:42,159 --> 00:03:48,640 it wasn't enough. Anyway, um then I went 91 00:03:45,280 --> 00:03:50,720 to Wikipedia. That also did not help. Um 92 00:03:48,640 --> 00:03:52,959 and at the same time, I was in a class 93 00:03:50,720 --> 00:03:54,879 called data structures and algorithms 94 00:03:52,959 --> 00:03:57,200 for uni, which is a similar class to 95 00:03:54,879 --> 00:03:58,879 what a lot of people have. And I was 96 00:03:57,200 --> 00:04:01,360 like, well, it's got data structures in 97 00:03:58,879 --> 00:04:03,120 the name. So, I went to tutors, two of 98 00:04:01,360 --> 00:04:05,519 them, and neither of them had heard of 99 00:04:03,120 --> 00:04:07,360 this one before. Uh, so that didn't help 100 00:04:05,519 --> 00:04:09,519 either. So I decided that I was just 101 00:04:07,360 --> 00:04:11,360 going to make one from scratch in Python 102 00:04:09,519 --> 00:04:14,159 because I figured that would definitely 103 00:04:11,360 --> 00:04:16,720 help me learn. Um, anyway, the data 104 00:04:14,159 --> 00:04:19,359 structure was called a skip list. But 105 00:04:16,720 --> 00:04:20,880 what is a skip list? It's quite niche. 106 00:04:19,359 --> 00:04:25,280 So I'm going to have to run you through 107 00:04:20,880 --> 00:04:27,360 it. So here's our real life example. 108 00:04:25,280 --> 00:04:29,199 You can kind of think of it like IKEA. 109 00:04:27,360 --> 00:04:30,560 So in IKEA you have all those sections. 110 00:04:29,199 --> 00:04:32,639 You've got like the dining room section, 111 00:04:30,560 --> 00:04:34,400 the office section, the bedroom section, 112 00:04:32,639 --> 00:04:36,400 the kids stuffed animal section, and 113 00:04:34,400 --> 00:04:38,080 they're all kind of you're meant to go 114 00:04:36,400 --> 00:04:39,440 through them in a line so that you can 115 00:04:38,080 --> 00:04:41,040 buy all the things from all the 116 00:04:39,440 --> 00:04:44,000 sections. But sometimes you're just 117 00:04:41,040 --> 00:04:46,720 looking for one thing like you just want 118 00:04:44,000 --> 00:04:49,040 one thing. You want the blahage and it's 119 00:04:46,720 --> 00:04:51,520 all the way at the end. If you know, 120 00:04:49,040 --> 00:04:54,800 like at least in my IKEA, it is at the 121 00:04:51,520 --> 00:04:56,479 end. So, you could just go all the way 122 00:04:54,800 --> 00:04:58,240 through and search everything in every 123 00:04:56,479 --> 00:05:00,720 single section and it would take you 124 00:04:58,240 --> 00:05:02,560 forever. Or you could use some shortcuts 125 00:05:00,720 --> 00:05:04,240 that they've actually got to cut through 126 00:05:02,560 --> 00:05:08,000 and then you only have to search the one 127 00:05:04,240 --> 00:05:12,160 section, the stuffed animal section. 128 00:05:08,000 --> 00:05:16,240 I love a blah. I have a 1.7 meter blah. 129 00:05:12,160 --> 00:05:17,600 It's great. I love it. Anyway, so how do 130 00:05:16,240 --> 00:05:19,280 they actually work? Well, we got to 131 00:05:17,600 --> 00:05:22,320 start from the start, which is linked 132 00:05:19,280 --> 00:05:24,560 lists as skip list are built off them. 133 00:05:22,320 --> 00:05:27,600 Basically, with a linked list, if you 134 00:05:24,560 --> 00:05:29,360 want to store a bunch of data, um you 135 00:05:27,600 --> 00:05:31,360 can either store them next to each other 136 00:05:29,360 --> 00:05:33,120 in memory, but that can get a little bit 137 00:05:31,360 --> 00:05:35,120 confusing if you want to add things or 138 00:05:33,120 --> 00:05:37,440 take things away. 139 00:05:35,120 --> 00:05:39,759 So, it gets a little bit confusing. So, 140 00:05:37,440 --> 00:05:42,240 what we do for a linked list is when we 141 00:05:39,759 --> 00:05:45,440 have a piece of data that looks like 142 00:05:42,240 --> 00:05:47,759 this, we have two sections. one is the 143 00:05:45,440 --> 00:05:50,000 data and one is this other section that 144 00:05:47,759 --> 00:05:52,800 kind of works like an arrow. It points 145 00:05:50,000 --> 00:05:54,479 to the next thing in line. And then you 146 00:05:52,800 --> 00:05:55,919 can string them together like that and 147 00:05:54,479 --> 00:05:57,600 you've got all of your data connected, 148 00:05:55,919 --> 00:05:58,960 but then it's much easier to add into 149 00:05:57,600 --> 00:06:02,400 the middle because you can just cut 150 00:05:58,960 --> 00:06:04,400 those arrows like strings. This the way 151 00:06:02,400 --> 00:06:07,120 that I think about this is sort of like 152 00:06:04,400 --> 00:06:09,840 those really old uh snake games on the 153 00:06:07,120 --> 00:06:12,319 Nokia. Every time it eats an apple, it 154 00:06:09,840 --> 00:06:14,400 adds to the string. Um and so you can 155 00:06:12,319 --> 00:06:16,400 break apart the string in the middle. I 156 00:06:14,400 --> 00:06:19,199 have a diagram for anyone who doesn't 157 00:06:16,400 --> 00:06:20,560 know what that looks like. Um, that's 158 00:06:19,199 --> 00:06:23,120 pretty much how I think about link 159 00:06:20,560 --> 00:06:25,600 lists. So, how would we go about 160 00:06:23,120 --> 00:06:28,400 searching one? So, this one's in order, 161 00:06:25,600 --> 00:06:29,919 as you can see. Um, but if we wanted to 162 00:06:28,400 --> 00:06:32,000 look for the number eight, it would take 163 00:06:29,919 --> 00:06:33,759 us forever. Let's see how long it would 164 00:06:32,000 --> 00:06:36,720 take. So, we have to start at the start. 165 00:06:33,759 --> 00:06:38,400 It's the only place you can start. And 166 00:06:36,720 --> 00:06:40,000 you can't really do anything 167 00:06:38,400 --> 00:06:43,360 interesting. You just have to go from 168 00:06:40,000 --> 00:06:45,440 one to the next one through the next one 169 00:06:43,360 --> 00:06:47,120 to the next one and next one and then 170 00:06:45,440 --> 00:06:49,199 you can get to the end. And we found 171 00:06:47,120 --> 00:06:52,400 what we're looking for. And that was 172 00:06:49,199 --> 00:06:54,960 five jumps. Counted it. 173 00:06:52,400 --> 00:06:57,680 So what can we do to make this better or 174 00:06:54,960 --> 00:06:59,520 faster especially for something much 175 00:06:57,680 --> 00:07:03,599 bigger than 176 00:06:59,520 --> 00:07:06,240 six six items? Yeah. The short answer is 177 00:07:03,599 --> 00:07:08,800 skip lists. Skip lists introduce what's 178 00:07:06,240 --> 00:07:11,280 called fast lanes. um which only 179 00:07:08,800 --> 00:07:14,080 contains some of the numbers in the 180 00:07:11,280 --> 00:07:16,319 entire linked list with arrows that 181 00:07:14,080 --> 00:07:17,520 point downwards. I've said references, 182 00:07:16,319 --> 00:07:20,319 but it's the same thing. They're 183 00:07:17,520 --> 00:07:22,000 basically just arrows. So, here's a 184 00:07:20,319 --> 00:07:25,599 diagram of what a skip list would look 185 00:07:22,000 --> 00:07:27,919 like using our initial linked list. So, 186 00:07:25,599 --> 00:07:31,680 we start with this, our linked list. 187 00:07:27,919 --> 00:07:34,319 It's exact same. And then we have these 188 00:07:31,680 --> 00:07:37,039 ones which are our fast lanes and they 189 00:07:34,319 --> 00:07:39,280 are just link lists but they also point 190 00:07:37,039 --> 00:07:41,599 downwards instead of just pointing to 191 00:07:39,280 --> 00:07:45,039 the right. So that means that we can 192 00:07:41,599 --> 00:07:47,440 start at the top and then go down. And I 193 00:07:45,039 --> 00:07:50,880 can explain how the search will go in 194 00:07:47,440 --> 00:07:52,720 words but I have an animation later. So 195 00:07:50,880 --> 00:07:54,639 we'll get to that when we get to that. 196 00:07:52,720 --> 00:07:57,039 But if we're looking at this, how would 197 00:07:54,639 --> 00:07:58,879 we add a number? There's some special 198 00:07:57,039 --> 00:08:02,160 steps we have to do. So I'll run you 199 00:07:58,879 --> 00:08:03,840 through it. We start with our skip list. 200 00:08:02,160 --> 00:08:05,680 Then say we want to add number nine. 201 00:08:03,840 --> 00:08:07,280 First of all, it always gets add to 202 00:08:05,680 --> 00:08:08,639 added to where it needs to go. And 203 00:08:07,280 --> 00:08:14,039 because nine's the largest, it goes to 204 00:08:08,639 --> 00:08:14,039 the end. And then we flip a coin. 205 00:08:14,560 --> 00:08:19,919 Heads. It's very fun. Uh that means we 206 00:08:17,360 --> 00:08:23,120 can go up a level. So now we add our 207 00:08:19,919 --> 00:08:27,120 nine up. And then we do it again. We 208 00:08:23,120 --> 00:08:29,199 flip a coin. And this one doesn't 209 00:08:27,120 --> 00:08:30,879 succeed. This one's tails, which means 210 00:08:29,199 --> 00:08:33,120 we don't get to add it any higher, which 211 00:08:30,879 --> 00:08:34,640 means that's where it ends. But why 212 00:08:33,120 --> 00:08:36,800 would we be flipping a coin? That 213 00:08:34,640 --> 00:08:39,440 doesn't make any sense. 214 00:08:36,800 --> 00:08:41,919 So, the reason why we're doing it is to 215 00:08:39,440 --> 00:08:44,560 get it closer to what our perfect skip 216 00:08:41,919 --> 00:08:46,080 list looks like. Here's a This is what 217 00:08:44,560 --> 00:08:48,880 it's supposed to look like. So, 218 00:08:46,080 --> 00:08:50,880 basically, a perfect skip list is where 219 00:08:48,880 --> 00:08:53,279 you have the base list and then every 220 00:08:50,880 --> 00:08:55,680 second item goes up and every second 221 00:08:53,279 --> 00:08:57,839 item from that goes up. So basically it 222 00:08:55,680 --> 00:08:59,600 ends up looking like a really nice curve 223 00:08:57,839 --> 00:09:02,560 and it makes it so that it's sort of 224 00:08:59,600 --> 00:09:04,160 like a binary search when you're looking 225 00:09:02,560 --> 00:09:06,080 for it. You can split everything in half 226 00:09:04,160 --> 00:09:09,040 in half in half which makes it really 227 00:09:06,080 --> 00:09:11,120 fast for searching. Um if we look at how 228 00:09:09,040 --> 00:09:15,120 many are in the top we've only got one 229 00:09:11,120 --> 00:09:17,360 and then three and then seven. So 230 00:09:15,120 --> 00:09:21,200 since every succeeding layer has half as 231 00:09:17,360 --> 00:09:23,519 many elements roughly um that means that 232 00:09:21,200 --> 00:09:25,680 every element has one in two chance of 233 00:09:23,519 --> 00:09:27,519 being raised up a level hence flipping a 234 00:09:25,680 --> 00:09:29,920 coin. 235 00:09:27,519 --> 00:09:32,000 So told you I was coming back to it. 236 00:09:29,920 --> 00:09:34,720 This is how we can search a skip list 237 00:09:32,000 --> 00:09:36,240 again. We start at the t start except 238 00:09:34,720 --> 00:09:39,519 this time we start all the way at the 239 00:09:36,240 --> 00:09:42,080 top. And because we know that 8 is 240 00:09:39,519 --> 00:09:44,880 greater than two, 241 00:09:42,080 --> 00:09:46,480 we check across. And we know that it's 242 00:09:44,880 --> 00:09:48,640 greater than two. So we can check the 243 00:09:46,480 --> 00:09:51,360 next one. And it's also greater than 244 00:09:48,640 --> 00:09:52,800 seven. So we can jump across. And then 245 00:09:51,360 --> 00:09:55,360 there's nothing in front of the seven. 246 00:09:52,800 --> 00:09:56,800 So we can just go down and then down. 247 00:09:55,360 --> 00:10:00,480 And since there's now something in front 248 00:09:56,800 --> 00:10:04,360 of the seven, we check across. And oh 249 00:10:00,480 --> 00:10:04,360 look, we found it. 250 00:10:04,480 --> 00:10:11,279 Now, this was only four jumps, which is 251 00:10:07,440 --> 00:10:14,640 shorter. I know it's like so different. 252 00:10:11,279 --> 00:10:16,880 Um, that's because this is quite a small 253 00:10:14,640 --> 00:10:18,959 skip list, so it's not going to be very 254 00:10:16,880 --> 00:10:22,079 obvious, but there is a way that we can 255 00:10:18,959 --> 00:10:26,480 think about how complex or how much work 256 00:10:22,079 --> 00:10:30,000 that took. Um, so I actually wrote this 257 00:10:26,480 --> 00:10:32,240 talk and performed did it in a very 258 00:10:30,000 --> 00:10:34,240 smaller capacity and they were slightly 259 00:10:32,240 --> 00:10:36,079 more technical. So they probably 260 00:10:34,240 --> 00:10:38,240 understood complexity like they've heard 261 00:10:36,079 --> 00:10:41,120 of big O before and not all of you have. 262 00:10:38,240 --> 00:10:43,519 So instead I'm explaining it for you. 263 00:10:41,120 --> 00:10:47,200 Woo. This is proof I learned things in 264 00:10:43,519 --> 00:10:50,240 my unique clauses. Anyway, so when we're 265 00:10:47,200 --> 00:10:53,920 looking at complexity, uh it looks at 266 00:10:50,240 --> 00:10:55,839 the comp computation required to do a 267 00:10:53,920 --> 00:10:57,680 task relative to the size of the data 268 00:10:55,839 --> 00:11:00,399 set. So that's basically how many times 269 00:10:57,680 --> 00:11:03,440 we have to loop or call functions or do 270 00:11:00,399 --> 00:11:05,519 like these really big tasks for how long 271 00:11:03,440 --> 00:11:07,200 your data structure is. So ours is only 272 00:11:05,519 --> 00:11:09,040 six elements. So it doesn't matter how 273 00:11:07,200 --> 00:11:11,680 many loops we do, that's still going to 274 00:11:09,040 --> 00:11:13,760 be very small. In order to show this 275 00:11:11,680 --> 00:11:16,640 relationship, all constants are ignored. 276 00:11:13,760 --> 00:11:18,240 So if it's like n on two, which is 277 00:11:16,640 --> 00:11:20,240 technically the average for a lot of 278 00:11:18,240 --> 00:11:23,120 things, it would just be ignored. So 279 00:11:20,240 --> 00:11:25,839 it's just the n because that shows more 280 00:11:23,120 --> 00:11:30,240 of the relationship between smaller and 281 00:11:25,839 --> 00:11:33,360 larger sizes of data and this like 282 00:11:30,240 --> 00:11:36,800 complexity. We call it big O. I actually 283 00:11:33,360 --> 00:11:40,000 don't know why. Um probably somebody 284 00:11:36,800 --> 00:11:42,160 told me at some point, but big O is to 285 00:11:40,000 --> 00:11:44,880 test what the worst case scenario for 286 00:11:42,160 --> 00:11:47,200 this would be. and big theta is for 287 00:11:44,880 --> 00:11:49,920 averages. So if we want to look at the 288 00:11:47,200 --> 00:11:52,480 complexity of searching a linked list 289 00:11:49,920 --> 00:11:55,440 versus a skip list, we start with our 290 00:11:52,480 --> 00:11:57,600 big O. We've got for a linked list, 291 00:11:55,440 --> 00:12:00,800 that's N. Which means if we have 20 292 00:11:57,600 --> 00:12:02,880 elements, our complexity is roughly 20. 293 00:12:00,800 --> 00:12:04,959 You have to look at every single element 294 00:12:02,880 --> 00:12:09,279 in the worst case. 295 00:12:04,959 --> 00:12:11,040 For a skip list, it's also n. Um, 296 00:12:09,279 --> 00:12:13,120 but why would you do it if it's 297 00:12:11,040 --> 00:12:15,600 literally the same? because that doesn't 298 00:12:13,120 --> 00:12:18,000 make any sense. So let's look at the 299 00:12:15,600 --> 00:12:20,320 averages instead. So the average for a 300 00:12:18,000 --> 00:12:22,480 linked list is n. Technically it's n / 301 00:12:20,320 --> 00:12:25,839 two, but because we ignore the 302 00:12:22,480 --> 00:12:29,519 constants, it's n. But the average for a 303 00:12:25,839 --> 00:12:31,120 skip list is log n. Now, some of you 304 00:12:29,519 --> 00:12:34,320 might not be able to do graphs in your 305 00:12:31,120 --> 00:12:36,320 head, so I have made you one. 306 00:12:34,320 --> 00:12:38,560 Basically, that's a really big 307 00:12:36,320 --> 00:12:40,959 difference. Not when you're really 308 00:12:38,560 --> 00:12:43,839 little, like five or six, but when you 309 00:12:40,959 --> 00:12:46,399 get all the way over here, it's a very 310 00:12:43,839 --> 00:12:47,920 big difference. That's I have this 311 00:12:46,399 --> 00:12:51,200 written down. That's the difference 312 00:12:47,920 --> 00:12:53,279 between 1 million and 20. So if you had 313 00:12:51,200 --> 00:12:55,200 a linked list of the size of 1 million 314 00:12:53,279 --> 00:12:57,360 and you had to search for an item, your 315 00:12:55,200 --> 00:12:58,880 average would be 1 million searches. 316 00:12:57,360 --> 00:13:03,040 Whereas with a linked list, it would be 317 00:12:58,880 --> 00:13:05,360 only 20, which is significantly better. 318 00:13:03,040 --> 00:13:09,360 So now we got to go into the section of 319 00:13:05,360 --> 00:13:12,000 how I actually went about coding it. 320 00:13:09,360 --> 00:13:14,399 So I had three main steps. First one was 321 00:13:12,000 --> 00:13:16,399 to create a linked list. Skip lists are 322 00:13:14,399 --> 00:13:18,320 based off them and they require them to 323 00:13:16,399 --> 00:13:20,399 run as you can remember from the 324 00:13:18,320 --> 00:13:22,320 diagram. So I had to start there 325 00:13:20,399 --> 00:13:24,240 especially because I needed to have a 326 00:13:22,320 --> 00:13:26,480 lot more control than if I just used a 327 00:13:24,240 --> 00:13:30,240 linked list that already existed. And 328 00:13:26,480 --> 00:13:31,600 then step two was practicing. Um I will 329 00:13:30,240 --> 00:13:34,079 get back to that but there was 330 00:13:31,600 --> 00:13:36,959 practicing involved and then step three 331 00:13:34,079 --> 00:13:39,680 was actually making the skip list. 332 00:13:36,959 --> 00:13:44,000 So to make the skip list it involved 333 00:13:39,680 --> 00:13:45,760 three separate classes which is a lot. 334 00:13:44,000 --> 00:13:47,600 We had one to store the individual 335 00:13:45,760 --> 00:13:50,720 values. So that's like our boxes from 336 00:13:47,600 --> 00:13:53,839 the diagram. One to store the uh 337 00:13:50,720 --> 00:13:56,560 positions in list which is like the 338 00:13:53,839 --> 00:13:58,560 little ball. Basically it remembers 339 00:13:56,560 --> 00:14:01,519 where we're at. so we can loop through 340 00:13:58,560 --> 00:14:02,880 it much easier and then one to connect 341 00:14:01,519 --> 00:14:06,480 everything together so it actually 342 00:14:02,880 --> 00:14:08,320 becomes a linked list. 343 00:14:06,480 --> 00:14:13,399 This meant creating a total of 40 344 00:14:08,320 --> 00:14:13,399 methods which is so many. 345 00:14:13,440 --> 00:14:20,160 This is an overview of the functionality 346 00:14:15,199 --> 00:14:22,320 I made for linked list specifically. Um 347 00:14:20,160 --> 00:14:25,680 first thing I made and this is based off 348 00:14:22,320 --> 00:14:27,440 the link lists uh class that's in C++ 349 00:14:25,680 --> 00:14:30,160 which is what my data structures and 350 00:14:27,440 --> 00:14:32,480 algorithms class was in but I wanted to 351 00:14:30,160 --> 00:14:36,399 do it in Python so that I could practice 352 00:14:32,480 --> 00:14:38,399 my classes in Python and also because um 353 00:14:36,399 --> 00:14:40,399 I can't put Python on a resume if I'm 354 00:14:38,399 --> 00:14:43,199 not confident in it. So I felt like I 355 00:14:40,399 --> 00:14:45,600 had to be confident and do it in Python. 356 00:14:43,199 --> 00:14:48,560 So first thing I did was pushing to the 357 00:14:45,600 --> 00:14:50,000 front and back of the list. So that's 358 00:14:48,560 --> 00:14:51,920 just adding anything to the front or 359 00:14:50,000 --> 00:14:54,800 back specifically. 360 00:14:51,920 --> 00:14:57,839 Um then the next one was making indexing 361 00:14:54,800 --> 00:15:01,279 work which is basically saying making it 362 00:14:57,839 --> 00:15:03,279 so that I can do list position X and 363 00:15:01,279 --> 00:15:05,199 either find the value that's there or 364 00:15:03,279 --> 00:15:07,360 store one in there. And that's using 365 00:15:05,199 --> 00:15:09,920 those funky looking methods called get 366 00:15:07,360 --> 00:15:12,880 item and set item. These are specific 367 00:15:09,920 --> 00:15:14,560 methods that are actually known in 368 00:15:12,880 --> 00:15:16,720 Python. They're called dunder methods 369 00:15:14,560 --> 00:15:19,600 because they have two double two 370 00:15:16,720 --> 00:15:21,120 underscores either side. And basically, 371 00:15:19,600 --> 00:15:23,040 Python looks out for them and it's like, 372 00:15:21,120 --> 00:15:26,079 well, I know this one. So, it means that 373 00:15:23,040 --> 00:15:29,360 I can use standard notation like list 374 00:15:26,079 --> 00:15:31,760 position x equals something just like 375 00:15:29,360 --> 00:15:33,519 you would do with a regular Python list. 376 00:15:31,760 --> 00:15:36,079 I didn't really know about these very 377 00:15:33,519 --> 00:15:39,279 much. I knew of them, but I'd never used 378 00:15:36,079 --> 00:15:41,279 them before. Um, so I had to learn a lot 379 00:15:39,279 --> 00:15:43,199 about them while I was doing this. Next 380 00:15:41,279 --> 00:15:44,880 one was popping the first and last 381 00:15:43,199 --> 00:15:47,839 elements, which basically means taking 382 00:15:44,880 --> 00:15:50,959 it and cutting it off from the list. It 383 00:15:47,839 --> 00:15:53,360 doesn't exist anymore. Disappears. Next 384 00:15:50,959 --> 00:15:55,680 one was getting the len and the in 385 00:15:53,360 --> 00:15:58,160 functions to work. So that's more dunder 386 00:15:55,680 --> 00:16:02,240 methods. So I can find out the length 387 00:15:58,160 --> 00:16:05,040 and uh check if things are in my link 388 00:16:02,240 --> 00:16:08,000 list. Then adding and deleting. Deleting 389 00:16:05,040 --> 00:16:10,240 is very hard actually in Python because 390 00:16:08,000 --> 00:16:13,839 in C++ it's really easy. You just kind 391 00:16:10,240 --> 00:16:16,320 of say delete in Python that's not a 392 00:16:13,839 --> 00:16:19,440 thing. So I'm hoping it counts as 393 00:16:16,320 --> 00:16:22,639 deleting to just ignore the memory. But 394 00:16:19,440 --> 00:16:24,639 it is technically there still. Um and 395 00:16:22,639 --> 00:16:27,120 then being able to print the list was 396 00:16:24,639 --> 00:16:30,079 the next thing. This is not in order of 397 00:16:27,120 --> 00:16:33,120 what I did it obviously but printing the 398 00:16:30,079 --> 00:16:35,279 list. Um you can actually use this 399 00:16:33,120 --> 00:16:36,800 dunder method. the format one to make it 400 00:16:35,279 --> 00:16:38,880 so that when you print the list it can 401 00:16:36,800 --> 00:16:40,399 print however you want it to look like 402 00:16:38,880 --> 00:16:43,120 which was really helpful especially for 403 00:16:40,399 --> 00:16:46,560 the skip list um it meant that I could 404 00:16:43,120 --> 00:16:48,160 look at it and test it um then I had to 405 00:16:46,560 --> 00:16:50,880 make this one so that the skip list 406 00:16:48,160 --> 00:16:53,839 would work and that's sorting so with a 407 00:16:50,880 --> 00:16:55,440 skip list everything is sorted and it 408 00:16:53,839 --> 00:16:58,560 has to start sorted if you're starting 409 00:16:55,440 --> 00:17:01,040 with a list initially um and to make 410 00:16:58,560 --> 00:17:04,959 that faster I made a sort algorithm for 411 00:17:01,040 --> 00:17:08,400 my links list Uh, I couldn't be bothered 412 00:17:04,959 --> 00:17:10,799 to do anything better than bubble sort. 413 00:17:08,400 --> 00:17:14,799 Uh, I did think about doing quicksort at 414 00:17:10,799 --> 00:17:17,280 one point and then I didn't because I 415 00:17:14,799 --> 00:17:19,199 did not want to. Um, there are lots 416 00:17:17,280 --> 00:17:21,439 more. 417 00:17:19,199 --> 00:17:23,439 I don't even know why I did as many as I 418 00:17:21,439 --> 00:17:25,039 did, but there are tons. Um, some of 419 00:17:23,439 --> 00:17:27,520 them were required for my practice and 420 00:17:25,039 --> 00:17:29,280 some of them were just because I'd heard 421 00:17:27,520 --> 00:17:32,400 of them. 422 00:17:29,280 --> 00:17:35,120 Okay, next one. So, the practice 423 00:17:32,400 --> 00:17:37,039 section, in order to practice making 424 00:17:35,120 --> 00:17:38,880 difficult data structures in Python, I 425 00:17:37,039 --> 00:17:41,280 decided to recreate an assignment I'd 426 00:17:38,880 --> 00:17:42,960 done for my class, which was making a 427 00:17:41,280 --> 00:17:46,559 hashet. 428 00:17:42,960 --> 00:17:48,880 Um, which took a lot of work in C++, a 429 00:17:46,559 --> 00:17:51,120 slightly less work in Python, luckily. 430 00:17:48,880 --> 00:17:52,880 Um, so yeah, I made a hashet from 431 00:17:51,120 --> 00:17:54,960 scratch because I was really confident I 432 00:17:52,880 --> 00:17:57,520 knew exactly how it worked because I'd 433 00:17:54,960 --> 00:18:00,480 done it before. I had to make every 434 00:17:57,520 --> 00:18:03,840 single method before and all of it I had 435 00:18:00,480 --> 00:18:07,160 to do in C++ which 436 00:18:03,840 --> 00:18:07,160 is C++. 437 00:18:07,600 --> 00:18:11,520 This took another 18 methods which 438 00:18:09,679 --> 00:18:13,760 aren't even in the final skip list. So 439 00:18:11,520 --> 00:18:17,280 it was like 18 methods that I didn't 440 00:18:13,760 --> 00:18:18,799 even need to do. But still I that's even 441 00:18:17,280 --> 00:18:20,480 more. 442 00:18:18,799 --> 00:18:23,840 I am not keeping a running count of 443 00:18:20,480 --> 00:18:26,000 methods but I think we're up to 58. 444 00:18:23,840 --> 00:18:29,760 Anyway, finally making the skip list 445 00:18:26,000 --> 00:18:33,440 took two more classes. Yay. 446 00:18:29,760 --> 00:18:37,600 One was to use the linked list object 447 00:18:33,440 --> 00:18:40,640 for the I think that this was this 448 00:18:37,600 --> 00:18:44,320 doesn't make sense. Um anyway, one was 449 00:18:40,640 --> 00:18:47,200 basically the skip list and one was the 450 00:18:44,320 --> 00:18:49,679 positions in the skip list. So when you 451 00:18:47,200 --> 00:18:53,360 have the higher levels, those sort of 452 00:18:49,679 --> 00:18:56,080 work like the regular elements of um the 453 00:18:53,360 --> 00:18:57,679 linked list, but not really because they 454 00:18:56,080 --> 00:19:02,080 have the arrows pointing down. That 455 00:18:57,679 --> 00:19:04,240 means my linked list uh iterators 456 00:19:02,080 --> 00:19:08,160 wouldn't work anymore because they have 457 00:19:04,240 --> 00:19:09,840 more information to store. Um yeah, so 458 00:19:08,160 --> 00:19:13,039 all of that I kind of had to do that 459 00:19:09,840 --> 00:19:17,679 from scratch again. This was another 28 460 00:19:13,039 --> 00:19:19,280 methods. So what is that? That's 461 00:19:17,679 --> 00:19:22,320 70 462 00:19:19,280 --> 00:19:26,080 80 something. I have people yelling it 463 00:19:22,320 --> 00:19:28,720 out. I can't hear. Anyway, so the 464 00:19:26,080 --> 00:19:30,720 functionality for the skip list. Um, 465 00:19:28,720 --> 00:19:33,440 this was something that I learned you 466 00:19:30,720 --> 00:19:37,520 could do in C++ and but struggled with 467 00:19:33,440 --> 00:19:41,360 it a lot in Python. So in C++ you can 468 00:19:37,520 --> 00:19:43,520 have several of the same method but have 469 00:19:41,360 --> 00:19:45,520 it have different parameters or 470 00:19:43,520 --> 00:19:47,280 different types for its parameters so 471 00:19:45,520 --> 00:19:49,679 that it can work differently based off 472 00:19:47,280 --> 00:19:51,760 different types. So I tried to do that 473 00:19:49,679 --> 00:19:54,080 in Python and I had to do some funky 474 00:19:51,760 --> 00:19:56,559 stuff with the type function to test 475 00:19:54,080 --> 00:19:59,200 what type it was in order to do separate 476 00:19:56,559 --> 00:20:00,960 things with separate parameters. So this 477 00:19:59,200 --> 00:20:02,640 was basically so I could allow initial 478 00:20:00,960 --> 00:20:05,120 values to be passed in whether that was 479 00:20:02,640 --> 00:20:06,799 a linked list or a regular list. And at 480 00:20:05,120 --> 00:20:08,480 some point I'll probably add a skip list 481 00:20:06,799 --> 00:20:11,120 in there. So you can start it off with 482 00:20:08,480 --> 00:20:14,720 some values in it already. 483 00:20:11,120 --> 00:20:16,480 Um again I had to allow it to print but 484 00:20:14,720 --> 00:20:19,360 this time I could let it print in 485 00:20:16,480 --> 00:20:20,960 several different styles um so that I 486 00:20:19,360 --> 00:20:22,799 could see it from different views 487 00:20:20,960 --> 00:20:25,039 especially if one of the formatting 488 00:20:22,799 --> 00:20:28,240 styles wasn't working. Made it much 489 00:20:25,039 --> 00:20:30,480 easier. Um, and then I had to search the 490 00:20:28,240 --> 00:20:32,080 skip list. But that search isn't very 491 00:20:30,480 --> 00:20:33,760 standard. Like with a link list, you're 492 00:20:32,080 --> 00:20:35,440 just going one, then the next one, the 493 00:20:33,760 --> 00:20:37,039 next one. It's just a basic loop. But 494 00:20:35,440 --> 00:20:40,159 with a skip list, it is actually 495 00:20:37,039 --> 00:20:43,280 recursive, which is I'm not great at 496 00:20:40,159 --> 00:20:47,280 recursion, but it technically works. So, 497 00:20:43,280 --> 00:20:48,960 you know, that's all I can ask for. Um, 498 00:20:47,280 --> 00:20:52,000 and then some other functions like 499 00:20:48,960 --> 00:20:54,720 getting specific lanes given the height. 500 00:20:52,000 --> 00:20:57,760 Um, and then converting it from a skip 501 00:20:54,720 --> 00:20:59,440 list into a standard Python list, being 502 00:20:57,760 --> 00:21:01,280 able to reconfigure it for a different 503 00:20:59,440 --> 00:21:03,760 height. So, the way skip lists usually 504 00:21:01,280 --> 00:21:05,679 work is using maths to find out the 505 00:21:03,760 --> 00:21:09,280 height. But I figured that the easiest, 506 00:21:05,679 --> 00:21:11,679 the best way to do it was to allow the 507 00:21:09,280 --> 00:21:13,440 user to pass in a height when they were 508 00:21:11,679 --> 00:21:16,000 creating the skip list so that they 509 00:21:13,440 --> 00:21:18,240 could uh decide how high they want it to 510 00:21:16,000 --> 00:21:20,559 be based off how much space they have 511 00:21:18,240 --> 00:21:22,320 pretty much. Um, and then I had to make 512 00:21:20,559 --> 00:21:25,840 some other helper methods to make sure 513 00:21:22,320 --> 00:21:27,760 that the rest of my stuff worked. 514 00:21:25,840 --> 00:21:30,240 So, we're going to go over things I 515 00:21:27,760 --> 00:21:32,240 learned. So, I talked about this 516 00:21:30,240 --> 00:21:34,000 earlier, but I had to use the type 517 00:21:32,240 --> 00:21:37,039 function in order to get some 518 00:21:34,000 --> 00:21:39,600 polymorphism. So, example of me using 519 00:21:37,039 --> 00:21:42,240 that was to allow the user to insert a 520 00:21:39,600 --> 00:21:45,039 value into a linked list as either at 521 00:21:42,240 --> 00:21:47,440 either the index it would need to go or 522 00:21:45,039 --> 00:21:48,880 an iterator for where it needed to go. 523 00:21:47,440 --> 00:21:52,240 And I've got some code. You don't have 524 00:21:48,880 --> 00:21:54,320 to read it, but it is there. 525 00:21:52,240 --> 00:21:58,080 You can see it says type in there 526 00:21:54,320 --> 00:21:59,440 somewhere. Um, next thing I had to get 527 00:21:58,080 --> 00:22:01,840 really confident with the dunder 528 00:21:59,440 --> 00:22:03,520 methods. They're most of my methods at 529 00:22:01,840 --> 00:22:05,520 this point are dunder methods. These are 530 00:22:03,520 --> 00:22:07,919 the ones with the double underscores 531 00:22:05,520 --> 00:22:10,559 before and after. They're the known 532 00:22:07,919 --> 00:22:12,799 Python methods. Um, like one of the 533 00:22:10,559 --> 00:22:14,720 examples I had to use format to print 534 00:22:12,799 --> 00:22:16,159 the skip list in different readable 535 00:22:14,720 --> 00:22:18,400 styles. 536 00:22:16,159 --> 00:22:20,880 This is I think actually this is my 537 00:22:18,400 --> 00:22:24,080 linked list one but that is some code 538 00:22:20,880 --> 00:22:26,240 that has a format method in it. Um 539 00:22:24,080 --> 00:22:28,080 another one I got to practice using 540 00:22:26,240 --> 00:22:29,520 exceptions 541 00:22:28,080 --> 00:22:33,280 which I didn't really cover but 542 00:22:29,520 --> 00:22:35,360 basically if somebody was using a type 543 00:22:33,280 --> 00:22:38,080 in a parameter that I wasn't checking 544 00:22:35,360 --> 00:22:39,760 for and I hadn't written the code for I 545 00:22:38,080 --> 00:22:42,320 would raise an exception which basically 546 00:22:39,760 --> 00:22:44,400 throws an error. So it tells the user 547 00:22:42,320 --> 00:22:46,559 that they're not allowed to do that. 548 00:22:44,400 --> 00:22:50,000 Here's an example. 549 00:22:46,559 --> 00:22:52,080 Um, and finally, I got really good at 550 00:22:50,000 --> 00:22:54,320 classes, algorithms, recursion, and 551 00:22:52,080 --> 00:22:57,360 debugging because I had to do all this 552 00:22:54,320 --> 00:22:59,520 on my own. I had no help. The only help 553 00:22:57,360 --> 00:23:02,640 I had was YouTube. 554 00:22:59,520 --> 00:23:04,880 Um, and that wasn't great. So, I got 555 00:23:02,640 --> 00:23:09,760 really good at a lot of things really 556 00:23:04,880 --> 00:23:12,720 quickly. Okay, conclusion. 557 00:23:09,760 --> 00:23:15,720 This was a massive pain. 558 00:23:12,720 --> 00:23:15,720 Um, 559 00:23:17,840 --> 00:23:22,720 I definitely do understand skip list 560 00:23:19,840 --> 00:23:24,960 now. Like I really understand them. Like 561 00:23:22,720 --> 00:23:28,559 really really understand them cuz I had 562 00:23:24,960 --> 00:23:32,080 to make them and it was really hard but 563 00:23:28,559 --> 00:23:35,440 I learned a ton and I think that means 564 00:23:32,080 --> 00:23:38,320 that you guys should do it too. I'm not 565 00:23:35,440 --> 00:23:42,159 100% sure I would do it in Python next 566 00:23:38,320 --> 00:23:44,080 time. Um it just it comes with pros and 567 00:23:42,159 --> 00:23:46,320 cons. Cons are that you don't have 568 00:23:44,080 --> 00:23:47,919 direct data management. So a lot of it 569 00:23:46,320 --> 00:23:51,120 you have to fake and it kind of gets a 570 00:23:47,919 --> 00:23:54,400 bit messy and the pros are that you get 571 00:23:51,120 --> 00:23:56,159 to do stuff like dunder methods and also 572 00:23:54,400 --> 00:23:57,840 you get to practice doing some of this 573 00:23:56,159 --> 00:23:59,600 harder stuff in a different language 574 00:23:57,840 --> 00:24:02,320 that doesn't really support it but you 575 00:23:59,600 --> 00:24:04,559 can do it anyway. So doing something 576 00:24:02,320 --> 00:24:07,039 that the language isn't really meant to 577 00:24:04,559 --> 00:24:09,200 do means that you're practicing doing 578 00:24:07,039 --> 00:24:12,400 stuff that's a bit hard. 579 00:24:09,200 --> 00:24:14,480 Uh, but also doing this in any language 580 00:24:12,400 --> 00:24:16,320 is really helpful for learning like I 581 00:24:14,480 --> 00:24:18,000 really understand hashets and exactly 582 00:24:16,320 --> 00:24:21,440 how they work, exactly how they're set 583 00:24:18,000 --> 00:24:25,039 up, what the like UML diagram would look 584 00:24:21,440 --> 00:24:26,880 like. Another thing I learned in uni. 585 00:24:25,039 --> 00:24:29,100 But yeah, it was it was really good. 586 00:24:26,880 --> 00:24:39,719 Anyway, thanks 587 00:24:29,100 --> 00:24:39,719 [Applause] 588 00:24:39,840 --> 00:24:44,159 I I thought you were going I can 589 00:24:42,960 --> 00:24:47,200 I'm just going to go and give you a high 590 00:24:44,159 --> 00:24:51,679 five. Look at me stalling. 591 00:24:47,200 --> 00:24:54,320 Um we we do have a minute or two for 592 00:24:51,679 --> 00:24:58,679 questions. 593 00:24:54,320 --> 00:24:58,679 We can Yeah. Here we go. 594 00:25:00,720 --> 00:25:05,760 Did you create any test cases to see if 595 00:25:03,840 --> 00:25:07,679 your functions did what they're supposed 596 00:25:05,760 --> 00:25:09,600 to do and maybe compare between like 597 00:25:07,679 --> 00:25:11,679 your C++ and your your Python 598 00:25:09,600 --> 00:25:14,400 implementations? 599 00:25:11,679 --> 00:25:18,799 So I every time I made a method I tested 600 00:25:14,400 --> 00:25:21,679 it. I didn't test it very deeply um as I 601 00:25:18,799 --> 00:25:24,960 found out recently when I was trying to 602 00:25:21,679 --> 00:25:27,039 test it with some larger skip lists. Um 603 00:25:24,960 --> 00:25:29,600 so there are definitely issues and uh 604 00:25:27,039 --> 00:25:31,440 the testing was very minimal but the 605 00:25:29,600 --> 00:25:33,760 methods mostly work how they should 606 00:25:31,440 --> 00:25:36,640 except for when you get past 10 elements 607 00:25:33,760 --> 00:25:39,200 because mostly the issue is printing 608 00:25:36,640 --> 00:25:41,120 just I haven't I didn't account for 609 00:25:39,200 --> 00:25:43,840 second digits when I was printing so it 610 00:25:41,120 --> 00:25:45,679 kind of looks really ugly. Um but yeah 611 00:25:43,840 --> 00:25:47,840 no majority of the methods work. I 612 00:25:45,679 --> 00:25:50,880 didn't really think about doing this in 613 00:25:47,840 --> 00:25:53,679 C++, so I haven't looked at testing it 614 00:25:50,880 --> 00:25:56,400 alongside C++, but the functionality 615 00:25:53,679 --> 00:25:58,720 does exactly what it would do in C++. 616 00:25:56,400 --> 00:26:00,720 Um, a lot of the functionality because 617 00:25:58,720 --> 00:26:03,520 skip lists aren't really a thing that 618 00:26:00,720 --> 00:26:05,360 you can just use. They're not a data 619 00:26:03,520 --> 00:26:06,960 structure that is natively implemented 620 00:26:05,360 --> 00:26:09,279 in Python. You'd have to use a module. 621 00:26:06,960 --> 00:26:11,600 Same in C++. I didn't really have 622 00:26:09,279 --> 00:26:13,039 anything to compare against except I 623 00:26:11,600 --> 00:26:16,159 just used the standard things that you 624 00:26:13,039 --> 00:26:20,000 would have like add, delete, front, 625 00:26:16,159 --> 00:26:22,480 back, push, pop, all of those things. 626 00:26:20,000 --> 00:26:24,720 Basically, I made the linked list with 627 00:26:22,480 --> 00:26:27,360 everything that would be in a C++ linked 628 00:26:24,720 --> 00:26:29,039 list and then I made a skip list and I 629 00:26:27,360 --> 00:26:31,760 made as many functions as I could think 630 00:26:29,039 --> 00:26:34,400 of. Um, but that was like the extent of 631 00:26:31,760 --> 00:26:39,360 my testing. Some of the functions don't 632 00:26:34,400 --> 00:26:39,360 work one specifically, but that's fine. 633 00:26:42,000 --> 00:26:47,120 Great talk. Um, what data structure are 634 00:26:44,640 --> 00:26:50,080 you going to build next? 635 00:26:47,120 --> 00:26:52,080 I was thinking a red black binary tree. 636 00:26:50,080 --> 00:26:55,679 Oh, I don't know how to build that. 637 00:26:52,080 --> 00:26:58,320 Yeah. Um, that's another when I did this 638 00:26:55,679 --> 00:27:01,120 in a smaller version. Um, somebody asked 639 00:26:58,320 --> 00:27:04,000 me why I didn't use that in my 640 00:27:01,120 --> 00:27:05,440 internship and um, I didn't have an 641 00:27:04,000 --> 00:27:08,559 answer for them because I'd never heard 642 00:27:05,440 --> 00:27:10,240 of it before and I had to I think they 643 00:27:08,559 --> 00:27:11,840 were mostly asking it cuz they wanted 644 00:27:10,240 --> 00:27:16,039 everyone to know that they knew what a 645 00:27:11,840 --> 00:27:16,039 red black binary tree was. 646 00:27:16,640 --> 00:27:25,159 So yeah, but that will be next maybe if 647 00:27:20,720 --> 00:27:25,159 I ever look at this code again. 648 00:27:26,559 --> 00:27:32,640 Um, you mentioned the special format 649 00:27:29,520 --> 00:27:34,960 method. What does that actually do? 650 00:27:32,640 --> 00:27:38,159 So, with the format method, if you've 651 00:27:34,960 --> 00:27:40,159 looked at format uh strings or frings in 652 00:27:38,159 --> 00:27:43,520 printing before, basically it means that 653 00:27:40,159 --> 00:27:46,080 you can customize how those fstrings 654 00:27:43,520 --> 00:27:48,400 behave with your object. So, when you're 655 00:27:46,080 --> 00:27:50,720 printing, usually you can print any type 656 00:27:48,400 --> 00:27:52,080 of object and once it gets to objects, 657 00:27:50,720 --> 00:27:54,559 it doesn't really recognize. It just 658 00:27:52,080 --> 00:27:57,039 prints a thing that says the object type 659 00:27:54,559 --> 00:28:00,240 and then a random code of numbers and 660 00:27:57,039 --> 00:28:03,200 letters. But if you use fstrings and use 661 00:28:00,240 --> 00:28:06,880 the format method, you can customize how 662 00:28:03,200 --> 00:28:09,520 that gets printed. So if I go back to 663 00:28:06,880 --> 00:28:13,600 the section of code that I have for 664 00:28:09,520 --> 00:28:15,440 that. Uh is that it? Yeah. Um basically 665 00:28:13,600 --> 00:28:18,080 what this one's doing is it's looping 666 00:28:15,440 --> 00:28:20,320 through the list. Like it starts by 667 00:28:18,080 --> 00:28:21,840 printing out the open list. Then it 668 00:28:20,320 --> 00:28:23,840 loops through every item in the list and 669 00:28:21,840 --> 00:28:25,919 it prints out the item plus a comma and 670 00:28:23,840 --> 00:28:27,440 a space and then prints out a closed 671 00:28:25,919 --> 00:28:29,520 list. So that's basically how it would 672 00:28:27,440 --> 00:28:30,960 happen for a regular list. This was just 673 00:28:29,520 --> 00:28:33,120 so my linked list would look the same 674 00:28:30,960 --> 00:28:36,960 when you printed it out. This means when 675 00:28:33,120 --> 00:28:39,200 you use an fstring or a format string on 676 00:28:36,960 --> 00:28:41,200 the object, it will print out like a 677 00:28:39,200 --> 00:28:44,240 regular list. And so I have several of 678 00:28:41,200 --> 00:28:46,000 these for my skip list. Uh if you look 679 00:28:44,240 --> 00:28:49,200 up the top there's a parameter called 680 00:28:46,000 --> 00:28:51,840 format specs that's required for this 681 00:28:49,200 --> 00:28:53,679 function. Um and that's basically you 682 00:28:51,840 --> 00:28:56,399 can pass in whatever code you want to 683 00:28:53,679 --> 00:29:00,320 write. Uh like it's usually a code like 684 00:28:56,399 --> 00:29:02,159 ll or whatever string. Um you pass it in 685 00:29:00,320 --> 00:29:04,000 and then you can test for those. So you 686 00:29:02,159 --> 00:29:06,399 can format it differently based off what 687 00:29:04,000 --> 00:29:09,279 you've passed in. So I did a link list 688 00:29:06,399 --> 00:29:11,760 version. I did a skip list version and I 689 00:29:09,279 --> 00:29:12,960 did one other version for my skip list 690 00:29:11,760 --> 00:29:15,960 so that they printed in different 691 00:29:12,960 --> 00:29:15,960 styles. 692 00:29:17,600 --> 00:29:21,840 Okay, I think we've run out of time for 693 00:29:19,919 --> 00:29:24,840 questions. Can we please thank Izzy 694 00:29:21,840 --> 00:29:24,840 again?