Essentials: Pointer Power! - Computerphile

professor brailsford we are doing our series on um the most important thing in computer science or uh something that you know you couldn't do without what have you got for us then today well i think my most important thing we're gonna sort of share this discussion uh steve bagley and i because i think we very much agreed that one of the most powerful concepts constructs in computer science is just the idea of a pointer one of the uses of pointers that's easiest to understand is in linked lists we're going to use lego to illustrate linked lists i know that some of you are demon programmers and could take it if i just ran through a program with you but i think a lot of you who are beginners perhaps might appreciate having a more pictorial introduction to linked lists so at great mental expense sean and i have developed a lego model of the linked lists we want to talk about and we'll gradually introduce the elements of this as we go along but the first thing to say is that pointers are pieces of i don't know what they are in lego fireman's hoses or connectors or whatever they're called that is a pointer of some sort in order to bring this home and make it more concrete i've got to say well what are we linking together and once again i mean this has been referred to in brian kernighan's thing about associative arrays he pointed off to singly linked lists and each of the elements within in this list contained a string what i'm going to start with is basically a piece of lego underneath a small section of c coding i'm going to go through this very carefully and those of you who aren't demon programmers don't get panicked about it i'll try to go very slowly and explain to you what's happening this is what i am going to call a thing whenever you look later on and say what is that gray base plate doing what does it signify gray base plate means it's a thing what are the components of a thing well a red box sitting on top of the thing holds a string of characters and again we're going to follow up with the idea of things you might buy for a barbecue burgers chips wine stuff like that but because it's a singly linked list the other box sitting within the structure is going to point off to the next thing along in this singly linked list if that's a thing then the only bit of programming i'm going to do today honest this is it is to just show you how this would be declared in the c language i'm using a type def declaration because i just want to be able to use the shorthand of thing a bit like ins instead of saying int shawn semicolon sean is an integer and can have context i just want to be able to say thing sean but in order to be able to make that abbreviation and to cut the clutter a lot i have to give what's called a type def a definition of what a structure of type thing really is and all it's saying in here if you look at it is char star item now what that is saying this is again those of you familiar with c will know it's a standard c way of saying it's a pointer to a char apparently but actually they cheat a bit because it's not just appointed to a single character it can be a pointer to a great long string of characters does char mean character that char is short for character yes some people call it car some people call it char but it's basically if you point at the first character in a string then you've pointed at the whole thing because you just step along it sequentially and here for the blue box in my model i've got to say well how do i point at the next thing along in my list well i hope you can see there's a sort of bit of recursion in the definition here but the compiler knows you can do things like this and doesn't panic you've got a struct underscore thing inside here referring back to this struct underscore saying what it's saying is that this thing i'm calling next within the structure is a pointer to the next thing so what are these things known as then this item and next they're called members in c next is also a member in other languages you'll find these internal identifiers if you like within a structure called different things i mean in algol 68 where i started they were called fields of the structure those are just so that you can pick out the components of your structure and remember the overall package of a pointer to the next one a red box which means i can contain a string of arbitrary size mount the whole thing up on a piece of gray lego and the whole thing is a thing we've got the basic building block then of what we need to start building together linked lists now some of you are going to say hey come on you're glossing over actuality because obviously this next member field is going to have a pointer in it to the next one of these things but you haven't said that inside the string box you can't just put a string inside an address box it might not be big enough to hold supercalifragilisticexpialidocious yeah quite right those of you in the know will know that within this box that contains a string you will have when it says so here you must create yourself enough space to hold the string and point at it we draw a veil over that for the moment just imagine that it doesn't matter what the string is burgers zucchini whatever we can create enough space in the red box to hold that string make it identifiable i'm going to put out the code for this program and any subsequent ones in the usual way available to you in in c i'll try and get my indentation so it doesn't make those of you care passionately about these things mind you there'll be there'll be indentation wars some people will love the way i've done it and other people will hate it but we'll live with that but yes the idea of this going through this model purely with lego is that if you then get hold of the program look back at the video try and follow all the things i'm doing and saying well how does the program do that and see if you can understand as we go along i wish in many ways i'd thought about trying to do this when i was teaching uh linked lists to third year undergrads i think it might have helped some of them who are very pictorial in the way they want to look at things once we've declared at the top of our c program that this whole thing is called a thing i can then say later on in the program if i wanted to thing sean just like saying int sean but this is the thing okay we haven't filled in your likes and dislikes sean um what's your favorite stuff at barbecue sausages sausages so that of course is the barbecue item that sean likes best now if i've named my thing which i haven't given this an identifier name i can say things like shawn dot item equals quotes sausages and that works fine because if you give an explicit string of characters in c it will at compile time find the space to hold that for you so that should work okay and there's also no prizes for guessing that perhaps for cleanliness i ought to fill in what the next field of shawn is and there is a standard way of saying it's the zero pointer it points nowhere it's called nil it's called null not been filled in yet but you've got to fill it in with something so you fill it in with null a stage beyond that is to say thing star p now if you're happy that star item within the structure means pointed to a string of characters then it follows that the type of p is pointer to thing so i haven't filled anything in here yet um this contains nothing this box but i could overwrite it with a pointer to sean if i wanted to do that okay so we will be developing quite a lot the idea that we don't necessarily deal always directly with things we stand back one level and we use pointers to things it makes good sense because within the list of structures we're developing as you know the next field is of type pointer to a thing i guess at this stage perhaps to make this a bit more concrete we could turn our attention now over to the lego and in that infuriating way that they do on home help do-it-yourself programs on tv i'm going to say here's one i've prepared already the idea in this particular linked list of barbecue items is that there are strings inside each of these red boxes as we've discussed and these strings of characters correspond to things you might want on a bbq but we are so neat and tidy we want to keep these in alphabetical order so look at this the string content in that red box says beer chips pizza slaw wine so don't forget these are the contents of the boxes the member name of each box is all the same it's always the item part of the particular thing you're on at the moment and the pointer here is the next part of that box but it's all beautifully set up look every one of your next boxes really does point to the start address of the next thing all the way down they're all in alphabetical order but the one aspect we didn't mention which is vital is that you must set up a pointer to the head of the linked list if you don't have that you can't reference anything what we're saying here is it's not part of linkedlist processing in general to give each of these uh things structures its own name i mean i could call them sean dave steve mike and uh robert or something like that but no that's too short i'd run out of names no keep them all in order but just retain one pointer that tells you what is the lead item in there so this start pointer look at the color coding it's blue so it's a thing star or as we used to say another 68 a reference to a thing you jump onto the pointer and you're the start address of the thing and inside that you can say give me the item give me the next and so on but the big question now is it's all beautiful but suppose actually i was told to get some burgers but they didn't have them available at the first supermarket i went in so i had to go somewhere else and get some burgers and unfortunately brian o'shawn has made this list up already so determinantly keeping it alphabetic if i prepare over here a new thing with burgers ready to be put in how do i traverse down this list find out where it belongs alphabetically and get it to work so that i can fiddle with the pointers and link it in quick check will show you that burgers belongs after beer but before chips therefore what you need is a probe to look inside each of these structures and to tell you what is inside there in terms of the item field now i can't you start as the probe if i move that away from the head of the list i'm sunk i'll never find that wretched list ever again you mustn't use start as your roving pointer but what i can do just like the thing called p i develop let's call this p for the pointer if i first of all copy over the contents of start into p which is also of type reference to thing then i hope you'll all agree that what will happen is i've now got this thing called p is pointing at exactly the same structure at the head of the list as starters so hope i've got enough finger power here to do it there you go you start with p up here and you say what's the item within that thing i'm pointing at the answer is beer so burgers goes after beer then move that from there to there and use it as a probe to ask what is the item entry in that one chips i need to be earlier than chips so you can see here you've got a bit of a problem with a single linked list if you move the pointer too far you end up with chips but you say ah but i want to insert it before chips but after beer i want to be back at this address so what i'm saying is it's perfectly possible to do it you've got to be very careful you've got to come in you've got to say that one's beer then you've very carefully got to take a look at this next field and say should i follow that pointer and see what's in the next red box you can do that it's fine but be so careful that it doesn't contain nil no it could be a very short list it could be that there's only one item in it and right down the bottom here this thing that looks like something from angry birds denotes no and if you start trying to follow the null pointer your program will go bang and say segmentation violation well that's fine but it needs some careful programming but it can be done and i will give you a solution that does it just that way next thing you've got to sort of say to yourself though is when i found where i want to be how do i bind in the new thing well the actual construction process if you like putting in the new thing once you've discovered that burgers needs to go in here somewhere is to do this you've got to well use an extra long pointer here which points to our newly created thing and we are then going to take the old pointer that was in there and put it as going from here to here so look we've done it we go beer follow the pointer to a thing that's got burgers let's move that out of the way follow the pointer to a thing that's called chips so we've inserted burgers so it's just point of manipulation once you've discovered where you are what you need in this and it's really frustrating you need to keep your finger in two places or you need two fingers let's put it that way you want to remember the one you've just looked at you want to take a look at the next one and say yes it's in between those two we've done it we've patched in our new thing for burgers so let me just sort of summarize some of the problems then obsessively keep checking for nil obsessively if you dereference that bang you're dead and that brings into question certain special cases what happens if i want to insert something at the end of a list where nil is parked there already i've got to be very careful there what suppose i wanted to put zucchini or something in at the bottom below wine that might be a problem even worse problem potentially might be if i wanted to put something in at the head of the list ahead of what's there already i mean under those circumstances what you'd be saying is something beginning with asian avocado to make guacamole with if we want to put avocado here then what you would have to do is create a new thing there and move that to pointed avocado and then make avocados link point at that one so this is avocado that would be the start of your list now and you'd have a internal one to complete it going from here to here now here is a big problem because you'd better get this right because notice you have actually altered start what i was saying all along was be careful of start it's your point to the head of the list but if you get something like avocados that has to be the new head of the list then you must make sure that the start pointer gets updated another special case that's got to be put in your code so be obsessive about checking for nil can you cope with things inserted at the head of very start of the list nicely can you cope with putting zucchini at the end is it all nice and clean you'll see in the solution i give you that there has to be a lot of special case checking to get all of this right but on the other hand you can make it work but you will in general need some sort of roving pointer or pointers moving down the list to check what you're pointing at and what the next one is now if you look at that code and say oh it's yucky it's horrible can't you do any better than that it's not easy however there is a top secret trick which actually makes it so much easier to do that it'll have to be a separate video sorry to leave with cliffhangers folks but it's a becoming almost a computer file tradition now isn't it so what would make life a lot easier is instead of just having start i mean we can't do away with it but we got it but you know it's a blue thing it points to a destructive type thing is if we introduce the concept of a pointer to a pointer to a thing and this is what a green box signifies i've got an extra long linkage here and i'm going to put that on there so i hope you're all happy because this is really doing type theory elementary type theory in a way that would make my functional colleagues blend but i'll try not to say anything too obviously untrue you'll have to agree with me that if the contents of a blue box is a reference to a thing then if you step one beyond it you're referring to a ref thing or a thing start or whatever so the contents of the green box would be a ref ref thing or in c notation a thing star star assembly programmers among you will say oh come on this is just type safe nonsense they're all pointers just mess about with them do what you want with them and don't make any mistakes now what i like about sea is it's a nice halfway house it gives you a bit of type safe capability it does distinguish between a pointer to a thing and a pointer to a pointer to a thing and makes you very carefully get the level of your pointing correct but what can be revealed in the future is that that simple trick of this thing containing a pointer to a pointer can solve a huge number of problems here is the definition or one possible definition of rec in the lambda calculus and this is what's known as the y combinator and if you look at this i mean it looks like a jumble of symbols but it's actually very similar to loop if we look back to see the definition of lube

Channel: Computerphile

Views: 417,587

Keywords: computers, computerphile, computer, science, Computer Science, University of Nottingham, Pointer, Linked List, Professor David Brailsford, DFB, Pointers, C Programming Language, LEGO

Id: t5NszbIerYc

Length: 20min 0sec (1200 seconds)

Published: Fri Aug 18 2017

Reddit Comments

[u/SurealStuff]

Why is this getting down voted?