Linked Lists - Computerphile

so a linked list is kind of the first serious data talks you learn about because it's very simple and it's actually got structure when rains got a bit for october link list is kind of slightly more complex we consume some flourishing things of the link list so a linked list is made up of nodes each node stalls and items data so it could be a number it will be in our example this is easy to write and it has a reference to the next node in the list if we wanted to store the numbers 1 2 3 & 4 in a linked list it would look something like this each node stores a value and a pointer to the next node so the value is 1 then we have another node with 2 in it and the first one point to the second one and if we want to have 3 we can fire where do you put the link is it in the new single or is it no if you're adding things at the end of the list the link goes from the existing node to the new node if you're adding things at the start to list which you can do you can't do it with an array because where do you put it you've got nothing you don't have access to what's before that in memory you know you're going to trample over something else and cause problems if you want to know that starts with linked lists so you want to add 0 to this list we could just create a new node somewhere it's not aware in memory actually is they don't need to be next each other these arrows can point to anywhere else in memory but if we wants to add the node 0 to the start of this list we'd create a new node put 0 in it and then point it at this element so now if we have two special nodes we have one called the head and one called the tail so the head is the node at the start of the list that points to everything else the tail is the nose at the end of lips that is pointed to by previous nodes and points to nowhere in general you would link list you need to keep track of at least the head the tail is kind of optional you don't have a keep track of the tail necessarily but if node it's going to be the head of our linked list so we'll have a some reference somewhere probably a you know as variable called head that points so this node so if we want to find things in the list we can go to the head and then we look at its next pointer and this one's next pointer little next pointer the last element in a linked list the tail of this you'll notice is some point anywhere conceptually there needs to be some value here we can't leave it uninitialized memory because it will be a garbagey number it will point to somewhere who knows where in memory and if you follow that link and try and interpret it as a node you're probably going to make your program crash what we do is we we point out that null so in C or Java it's called null or I'll be the number 0 like a memory address 0 which is interpreters null or in Python it would be none I think it's I think it's null in most languages if I know it points to null then we know it's the last item in the list which is nice we know when we know we've gone through the whole list and found every element kind of reminds me little bit of a sort of Treasure Trail where you find something and then it tells you where to go next yeah I guess is like that so yeah I mean similarly to that you can't you can't find a middle clue without having to find one before it so with a link layer you don't have random access or constant time random access to the element so if you wanted to find the last one element in the list you need to start from the start keep counting forward probably until you get the last one and then oh it's gone before that I mean if you want to get to the 10th element you have to go through 10 times so in a row you can access the 10th element really easily you just say get the element n it multipliers the width of the variable or the width of the item by 10 and jumps that far in memory with a linked list you can't do that because they're stored in arbitrary places in memory you don't really know where and you can only get to them by following the link so this intense thing you've got Paulo's handling thousands thing you've got the follow-up out of the link because they could be buried anywhere in however many gigabytes of RAM on your computer so yeah these could be anywhere in memory you could be jumping around all over the place yeah that's the only way to get there is to follow the link sometimes we might also want to maintain a reference to the tail as well as the head so we can just point tail at this last element and this helps us if we want to add elements to the end of the linked list because if we know where this node is we can stop it pointing at null and point a new node and then point the new node at Mel's what happens if you need to have something in the middle of the list oh let's say we wanted to add the number 26 in between 1 and 2 so you know who knows why but we want to do it so what we need to do is create a new node somewhere matter let's let's put it here that contains the number 26 we need to break this link so that's no longer there and we add two new ones one pointing from the node 126 another one point from no 26 to 2 if we wanted to do this in an array what we have to do is we'd have to shift every element after one down one that will take and operations and then put the number 26 in the gap we just made by moving a tool on so with a linked list after we found the place we want to insert the node it's constant time assertions at least we're breaking one link and creating three more and that subtle how many knows there are in the list we're changing three links breaking one adding two searching may take up to in it if we want to insert after an element with a value of 3 we're gonna have to search through the whole list and that will take up to n so after those up to the number of things in the list the actual insertion is constant time also if you want to remove an element from the list that's that quite easy to what we do we would we break these two links and then we create a new link joining one two two again so the flight special case for inserting or removing if you want to do it at the head or the tail you need to change the head or tail reference points of the new nose please the head or tail so if we want to remove the first node in the list we break this link we would break this link and then we create a new link from head to the new head of the list similarly if we insert we point a head at the new node if we delete the tail we point tail at that node create a new one we point it at the new know these linked lists we've looked at so far are called singly linked Lee because they each have a single link to the next node in the list now there are also stubbly linked lists so a doubly linked list has a link both to the next node and the previous node so those are slightly different they now have three compartments okay so we have the value still here so we've got 0 1 2 3 each of these as a point of votes to the next node and to the previous node so three here and of course not getting okay no that goes the no seeing kind of thing is it's a breadcrumb trail but it goes both ways so if you want to you can start at the head and go down to the tail you can start the tail and work throughout so the head still you don't have very good random access because you've either got to go from the tail and backwards or from the head and forward okay so a practical example of where I've actually used a doubly linked list in almost the real world in your web browser you visit website you click some link you go to the next page next page next page and then in the top corner you can click the back button and go back a bit keep going back so you can go forwards again and then also you might go back a bit you might click another link let's see how this works for the link list I'm just going to all the data compartments is easier so we start with main page at the start of a list this just points the null this will also point to null as soon as we browse to somewhere so yesterday I was looking up on Wikipedia and it was linked to nothing on the front page so I went to look at NASA so it's points back from here this points to null because we're browsing NASA and then really bit about NASA click on the Neil Armstrong article it points back here and points forward to null because it's the end of the list from Neil Armstrong I started reading about Apollo 11 so points back to Neil Armstrong and forwards the null so while we're going forward we know which page were on so we're on Apollo 11 so if we're pointing out Apollo 11 here is my hastily constructed non blow away able pointer so I think enough about Apollo 11 I'm going to go back a couple of so go back to Neil Armstrong now we're reading about Neil Armstrong again so on his page you know if you wants me to go forward to Apollo 11 click forward button but okay we go back a couple back to NASA our black history is still there or forward history is still there however we decide to take another link on NASA we decide to look at the International Space Station page so there's a link from NASA to the IFF page for the click there now we break this link we no longer have Nia long stroganoff forward history we're now ISS pointing back to NASA and if we go back to NASA from ISS we're at where I assessed we go back to NASA we can't get back to the alarm stron anymore we have no no way to get there every time we're on a page and we click a new hyperlink we break the previous history the previous port it's big goes away and we create a new nodes that that represents the current page rom are the many other things that sort of code gets useful yeah so you might do this with something like undo and redo history in a program like word or or notepad or something like that some saw mentor every time you take one do you go back to previous takes but your redo states still there until you do something and then you've lost through your redo history aleko using something like sure we like vim which I think sauce all your undo and redo is a tree and you can eventually get back to the things so it doesn't ever throw anything away but but for most ones would you say it's breaking the chain yeah so you break the chain you throw away all this future that you you've gone back from and it's gone so look at the names and make the names meaningful so instead of doing that you can use a thing called an array which is one name that points up multiple items of data which we saw next to each other and a contiguous block of memory

Channel: Computerphile

Views: 169,418

Keywords: computers, computerphile, computer, science, computer science, linked list, array

Id: _jQhALI4ujg

Length: 10min 10sec (610 seconds)

Published: Fri Jan 20 2017