Linked Lists - Computerphile

  Рет қаралды 204,095

Computerphile

Computerphile

7 жыл бұрын

Linked Lists explained: Dr Alex Pinkney returns to Computerphile.
Apologies for the traffic noise on this episode - we tried filming outside in London which it turns out didn't work that well for audio!
EXTRA BITS: • EXTRA BITS - Linked Li...
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: bit.ly/nottscomputer
Computerphile is a sister project to Brady Haran's Numberphile. More at www.bradyharan.com

Пікірлер: 409
@aksela6912
@aksela6912 7 жыл бұрын
The traffic noise wasn't that bad. I heard everything that was being said and it added an interesting background.
@Computerphile
@Computerphile 7 жыл бұрын
+Aksel Anker Henriksen thanks, I did my best to filter it but at the time we had to keep stopping and starting because of trucks stopping next to us etc... >Sean
@crystallastname9675
@crystallastname9675 7 жыл бұрын
I agree with aksel, but in my inexperienced opinion indoors'd be better
@Shadow4707
@Shadow4707 7 жыл бұрын
I didn't notice it at all actually.
@remmoze
@remmoze 7 жыл бұрын
I went to the comments section to tell the exact same thing
@DrRChandra
@DrRChandra 7 жыл бұрын
It worked well.
@mmanuel6874
@mmanuel6874 5 жыл бұрын
I love how you pointed out some used cases of the linked lists in real life! It helps me appreciate the data structure and makes me want to learn more!
@MrTransits
@MrTransits 3 жыл бұрын
I was mind blown when he gave real examples that we can all try/observe at our own homes. 😌
@hamzashakeel5684
@hamzashakeel5684 7 жыл бұрын
Really nice video. You should do more videos on data structures like binary trees, stacks, and queues.
@user-mn3iq2cs9n
@user-mn3iq2cs9n 5 жыл бұрын
The best explanation of anything in 10 minutes I've seen, and the best jumping into linked lists explanation I've seen. Thanks, Doc! Love the on the street tutorial. Reminds me of many on the fly, brilliant napkin tutorials I've had with professors and genius artists over the years, with ale, coffee, or tea.
@diogofolques3075
@diogofolques3075 7 жыл бұрын
Lot's of people saying linked lists are sh*t in terms of performance, and that might be true, however they are very useful to start learning data structures, so you can more easily learn other kinds of structures like binary trees
@boptillyouflop
@boptillyouflop 7 жыл бұрын
Yes. That's why they teach linked lists in those computer science classes. It does have real world applications - namely that after that, you know how to use std::map without blowing things up. :3
@Brandon_66
@Brandon_66 4 жыл бұрын
This is better than an entire college lecture
@AssailantLF
@AssailantLF 7 жыл бұрын
I'm loving these recent programming concept explanation videos! I hope the channel progresses to the more complex data structures over time, as those would benefit from the explanations more than the simple stuff.
@jayyyzeee6409
@jayyyzeee6409 7 жыл бұрын
Brings back fond memories of undergrad Comp Sci classes. Not one mention though of memory deallocation, the worst developer sin in languages without memory management.
@craigrotay3732
@craigrotay3732 7 жыл бұрын
I'm very impressed with Dr A here bcs he is so simplifying a concept that is extremely complicated.
@AnthonyHartwig
@AnthonyHartwig 7 жыл бұрын
Nerds make me happy. Makes me miss the CS culture from college. Keep up the awesomeness on this channel!
@greenolvi
@greenolvi 7 жыл бұрын
9:20 my thought 'unless you're using vim'. Few seconds after in the video 'unless you're using something like vim'. Great video :-)
@patrickmayer9218
@patrickmayer9218 Жыл бұрын
The comparison to tab history was genius! Thanks for the explanation!
@grzesiek1x
@grzesiek1x 3 жыл бұрын
I really like how he explains things! I am working now on linked lists and it really helps to understand ! Thanks :)
@ashtonscalise6949
@ashtonscalise6949 6 жыл бұрын
really liked this video. Every other piece of information i could find just explained what they are instead of the practicality. Understanding the use case makes it much easier to understand for me.
@rsmease
@rsmease 6 жыл бұрын
The live example with the animation running as he explains it is great.
@Woozeesh
@Woozeesh 7 жыл бұрын
Wow. Where did he get all of that antique fan-fold printer paper? I haven't seen that much ffp since my freshman engineering days back in the 80's.
@raunak51299
@raunak51299 2 жыл бұрын
You have no idea how helpful is this for new learners like me
@ikemuoma8495
@ikemuoma8495 4 жыл бұрын
Very good video. I particularly liked him using the web page examples as a means of explaining applications of double linked lists.
@coldensapir3901
@coldensapir3901 2 жыл бұрын
Awesome video, thanks for laying things out clearly without going boringly slow. I also liked the use of music paper lol
@gregoryfenn1462
@gregoryfenn1462 2 жыл бұрын
Double linked lists all the way! You can also generalise if you want: add a reference to the “middle” node which can fairly easily be maintained. Then inserting or editing the Nth item in your list can be done either from front to end, front end to front, from middle to end, or from middle to front. If you have a very long list then this added overhead is worth it and can half your insertion/modify time cost. (You could gene realise further with a reference to the item at each quartile or decile or percentile too, if you had incredibly big lists.)
@WarriorAjk
@WarriorAjk 3 жыл бұрын
The wikipedia example he gave was a pretty good application of linked list. Nicely explained!
@DrRChandra
@DrRChandra 7 жыл бұрын
"Pointing at null" seems semantically slightly different than saying "null pointer", which is what my CS courses taught me to put at the end of a linked list. "Pointing at null" means it's pointing at something (that happens to be null), whereas the concept of null pointer is that it isn't pointing at anything at all.
@DrRChandra
@DrRChandra 7 жыл бұрын
Most architectures have the null pointer as 0, but I've seen a few rare ones which it was all 1's for the width of its word. And it has nothing to do with hardware. Just saying, pointing at (for example) a zero is not the same thing as a pointer whose machine value is zero.
@TrevorPike
@TrevorPike 7 жыл бұрын
In the Amiga OS, the doubly linked lists combined the head and tail pointers in a which eliminated the special cases for insertion or removal at the beginning or end.
@Theraot
@Theraot 7 жыл бұрын
I would have prefered if they teach to put the link of the new node before you move the link of the previous one. Because if moving the link is an atomic operation (as it should be) then the list was never on an invalid state. But if you start by moving the link of the previous node and then set the link of the new one, there is a chance that the state where the new link points to null (or trash depending on your language and compiler) is visible to other threads.
@VeerleGroot
@VeerleGroot 7 жыл бұрын
what happens to the linked list elements that are cut away when you click another link in memory terms?
@robmckennie4203
@robmckennie4203 7 жыл бұрын
They become orphaned and are no longer accessible. Poorly designed programs might just leave it there, and over time more and more memory is consumed but isn't actually being used, that's called a memory leak. The proper way to deal with it is to deallocate the memory, which is just telling the operating system that you don't need it anymore and it can be used for something else. Some languages do this automatically in a process called garbage collection, but some lower level languages like C require the programmer to do this manually
@404namemissing6
@404namemissing6 7 жыл бұрын
Oh i need to know this for my exam in 4 days.
@Hopsonn
@Hopsonn 7 жыл бұрын
If you are interested, I have a video on creating a linked list using C++ on my channel, it might help out with your exam.
@PlatonicGuy
@PlatonicGuy 7 жыл бұрын
Had an exam on this last week. I guess I just got unlucky with the timing that they decided to post this. Good luck on yours btw :)
@404namemissing6
@404namemissing6 7 жыл бұрын
Matt Hopson I need to do it in scheme.
@PeoniesRoses
@PeoniesRoses 4 жыл бұрын
The noise wasn't too bad, I was just confused as to why you were casually explaining data structures in the streets of London, but oh well. Quite refreshing, I guess :D
@mrinalkd
@mrinalkd 7 жыл бұрын
Great video. I want to see more videos like this.
@khaled-dev
@khaled-dev 3 жыл бұрын
thanks for showing the streets, having seen that in awhile :D
@Cold_Ham_on_Rye
@Cold_Ham_on_Rye 7 жыл бұрын
Jesus christ. I said this on another video but the computerphile community is toxic. Like they criticize the shit out of every video.
@gophop
@gophop 7 жыл бұрын
I think it's more of a personality trait of the nerds.
@Cold_Ham_on_Rye
@Cold_Ham_on_Rye 7 жыл бұрын
but the numberphile and sixty symbols communities are nothing like this. It's specifically computer nerds.
@AttilaMihalyBalazs
@AttilaMihalyBalazs 7 жыл бұрын
I found the comments generally well mannered and useful, but leaving out the fact that you should never use linked lists in the real life is a big, glaring omission.
@0xCAFEF00D
@0xCAFEF00D 7 жыл бұрын
No this place is extra terrible for sure. Compare to sixty symbols, numberphile or even better deepskyvideos. I think it's because computer people aren't humbled enough as there's so many different correct answers. And we're taught to power through mistakes to a large degree.
@QuomoZ
@QuomoZ 7 жыл бұрын
I hope at this channel makes a video about algebraic data types and how to define a linked list using them.
@nackyding
@nackyding 5 жыл бұрын
Nice! Especially the case examples you used.
@N....
@N.... 7 жыл бұрын
It's a bit troubling though that linked lists are rarely more efficient and yet they are frequently taught as if they are extremely useful. They are a great learning tool, but they are generally very inefficient compared to contiguous arrays unless each element is very large, and it is rare to have very large elements. Always profile your code before settling on a linked list.
@probE466
@probE466 7 жыл бұрын
Uh no, you choose your list implementation based on the operations you plan on doing. if you want to keep adding at the end or front and wont be searching by index a linked list is perfect
@N....
@N.... 7 жыл бұрын
probE466 You choose your list implementation by profiling your code. Even in the scenario you describe, a contiguous list may be more efficient. There's also the issue of memory fragmentation.
@Hopsonn
@Hopsonn 7 жыл бұрын
I think they are mainly taught because it is simple to implement. Making my first linked list about a year ago now helped me understand pointers like I had never before.
@78wowguy
@78wowguy 7 жыл бұрын
The problem however is that a linear search is necessary to find the item to remove or add and that takes way more time in an linked list than in an array. This makes the array in most cases faster than a linked list.
@user-sw7yi9fx9b
@user-sw7yi9fx9b 7 жыл бұрын
Linked lists by itself are not very useful. That's true. But the idea of linking "something" by references in memory _is_ useful. And can be used for, for example, implementing graphs. So, I think learning linked lists is very important.
@AlbertoGuitarrista
@AlbertoGuitarrista 4 жыл бұрын
Great explanation indeed! Thank you very much, it was all clear. I'm subscribing.
@Kanephan
@Kanephan 5 жыл бұрын
well shot and edited
@brandonjanes6464
@brandonjanes6464 4 жыл бұрын
I like the traffic noise. It reminds me of the before times.
@786Peacelover
@786Peacelover 5 жыл бұрын
Terrific video... Example was great plus the location is an icing on the cake.. makes it learning pretty pleasant and real .. unlike sitting on computer and talking like robot :D
@borngraced3378
@borngraced3378 Жыл бұрын
thank you for the use cases!!
@izcool100
@izcool100 6 жыл бұрын
When adding a node in the middle of the list, you cannot break the link first as the reference to the node that the link was referencing would be lost. Create a temp variable that points to this node, break the link the you can point to the new node ad the new node point to the next node and remove the temp variable.
@swehunter2000
@swehunter2000 7 жыл бұрын
at 8:56 You wouldn't brak the pointer from Neil Armstrong to NASA when linking to ISS from NASA. it doesn't matter if two objects point to NASA, and it takes cycles to break the link for no reason.
@handsome7mateen
@handsome7mateen 7 жыл бұрын
can you do a video on time & memory complexity?
@andredejager3637
@andredejager3637 2 жыл бұрын
The back/forward web browser example was delicious
@AgentM124
@AgentM124 7 жыл бұрын
undoing the future and creating a new future destroys the ability to visit the other future unless you have a tree structure...
@IceMetalPunk
@IceMetalPunk 7 жыл бұрын
Right, but in regards to browser history, there are only forward and back buttons, or past and future histories. There's no option to switch to different branches of the history. It's not Git :P
@smurfyday
@smurfyday 7 жыл бұрын
You just repeated something said in the video, genius.
@0LoneTech
@0LoneTech 7 жыл бұрын
Agent M Another option is to treat the undos themselves as new edits, like Emacs does. That way they can in turn be undone, and you keep the history.
@Bunny99s
@Bunny99s 7 жыл бұрын
+LoneTech Right, that's "partly" what the explorer in windows does. A "back" event is not considered as a change but if you manually click on any parent folder it's a seperate navigation step. Say you navigate a folder down to the third level. If you now click on the root folder, the back action will bring you back to the third level then to the second and so on. However If every undo counts as new undo step you run into trouble because you have to keep a seperate list of the current undo step. Because if "going back" is added as new undo step at the end, going two steps back would bring you back where you were at the beginning.
@IceMetalPunk
@IceMetalPunk 7 жыл бұрын
On the other hand, you can model undo/redo as a pair of stacks. I don't know if that would be more efficient, but it whittles the functionality down to only the bare necessities for that behavior.
@IceMetalPunk
@IceMetalPunk 7 жыл бұрын
To elaborate: when a change is made, push the current state onto the undo stack. When UNDO is pressed, pop the top of the stack, set the current state to that popped state, and then push the state onto the redo stack. When REDO is pressed, just do the same thing in reverse. (And of course, clear the redo stack when any other changes are made.)
@rlamacraft
@rlamacraft 7 жыл бұрын
IceMetalPunk That was my thought, but then I thought about how to best implement the stacks and a linked list is probably better than an array because you add frequently and don't require random access. Though I would probably create a memory pool so that allocating memory can be batched up. Maybe each node would contain a small set of operations to reduce the memory overhead of the pointers, but still better than implementing the stacks as arrays.
@AdamLeuer
@AdamLeuer 7 жыл бұрын
I had a similar thought. I can say for sure a stack is perfect if you just need to implement undo, but maybe a linked list would be better for both undo and redo(?). I can say I've used a stack for implementing time reversal in a video game, and it was well suited to it.
@anousenic
@anousenic 7 жыл бұрын
Yes a stack is an solution - until you consider that you may want to limit how many undo steps are being preserved. Since at some point you probably want to start discarding the oldest undo steps, in order to not consume more and more memory with every action taken.
@Bunny99s
@Bunny99s 7 жыл бұрын
+AnotherUselessNick Well an undo stack can be implemented as a circular buffer. So you have a fix sized buffer a start and an end pointer. The start doesn't have to be fix. When you reach the end of the buffer you simply wrap around and start again from the beginning, overwriting the oldest entry. At the same time the start pointer would be moved forward so the second element is now the "first" and the first in the buffer is actually the last.
@saindst
@saindst 9 ай бұрын
Oh my goooooood, an actual damn example wtf. Its mad how a real world example just makes everything click
@stocktonjoans
@stocktonjoans 7 жыл бұрын
Could you have a repeating list where you pointed the last node back towards the first?
@Hopsonn
@Hopsonn 7 жыл бұрын
It is called a circular linked list.
@stocktonjoans
@stocktonjoans 7 жыл бұрын
Matt Hopson cheers
@Hopsonn
@Hopsonn 7 жыл бұрын
skunkFU25 a graph is a very general term, circular linked list is specifically what this guy asked for.
@hellterminator
@hellterminator 7 жыл бұрын
+skunkFU25 No. A linked list is a data structure, a graph is, well, a graph. However, you can represent a linked list with a graph. In this case it would be a directed cycle graph for a singly linked circular list or an undirected cycle graph for a doubly linked circular list.
@Quickstep1716
@Quickstep1716 7 жыл бұрын
+hellterminator Graphs are data structures too, much like arrays and hash tables.
@qwaqwa1960
@qwaqwa1960 7 жыл бұрын
The OS/2 Web browser DIDN'T break the forward links when you chose a new path. It kept a tree view of all visited pages. Man, I miss that.
@dimitrisdimitriou6969
@dimitrisdimitriou6969 7 жыл бұрын
you got Goodrich and Tamassia book?
@jy_chen
@jy_chen 2 жыл бұрын
The example of webpage history is very interesting and intuitive
@yash1152
@yash1152 2 жыл бұрын
0:47 I was wondering that what's the significance of showing the arrow curved, rather than straight just how he drew but 1:18, yeah, curved arrow are more suitable for conveying the non-contiguity. nice detail.
@Barreloffish
@Barreloffish 5 жыл бұрын
So when we deleted a node, we essentially unlink it from the list and not really delete it from memory. For array, we use delete [ ] array; but how do we actually delete this unlinked node?
@juicyclaws
@juicyclaws 7 жыл бұрын
undo/redo operation i've always implemented using two "stacks" (arrays). do something new, push to the undo stack and clear the redo stack. press undo, pop the undo stack and push it to the redo stack. press redo, pop the redo stack and push it to the undo stack.
@PEGuyMadison
@PEGuyMadison 5 жыл бұрын
My first class on C was in 1989, the professor started out by saying "I assume you all know how programming languages work, so we are going to focus on pointers and system programming in this class" I am a heavy user of linked lists but they also have their limits, I have found they are great for joining data into a pseudo array but when it comes to searching an array is much faster and an array is just a basic list. When it comes to multicore use a list with locks can be troublesome but far outweighs the impact of cache invalidations and excess memory bandwidth. For multiprocessors you can break down lists into per-core tasks and join them at the end of each task which will far out perform a array copy. Both have their advantages but profiling and ease of use also need to be considered.
@alexandrugheorghe5610
@alexandrugheorghe5610 3 жыл бұрын
Engineering is has and will always be about trade-offs
@OhNoRh1no
@OhNoRh1no 7 жыл бұрын
I was just going over this in CS50! now do tries! Those hurt my brain :P
@trianglefree
@trianglefree 7 жыл бұрын
Can you please do a video on segment tree
@jamesyeoman794
@jamesyeoman794 6 жыл бұрын
I have just thought of a way you could optimise the access time in a doubly linked list! Binary Search! Seeing as though you have access both ways, you can reduce the search time drastically (If I am wrong about this, please tell me. I have recently started a Software Development Apprenticeship and so I am keen to learn all that I can from wherever I can)
@shadowp2066
@shadowp2066 Жыл бұрын
Very Informative, Thank You
@73h73373r357
@73h73373r357 7 жыл бұрын
Can you do one on positional lists next?
@MRcrackerM
@MRcrackerM 7 жыл бұрын
can you make video about quadtrees please :)
@portblock
@portblock 7 жыл бұрын
I didnt see it, but you also have to account for the amount of data in the list. Example: first block, has number of bytes in the list, then tail says if its linked or not. Example, is the classic file system. you dont want to have a link list of single bytes, as the link pointers take up more data. just fyi info
@isaacjacobharris
@isaacjacobharris 5 жыл бұрын
Thank you for the lesson
@FREEZarts
@FREEZarts 2 жыл бұрын
really cool video
@vivekpal1004
@vivekpal1004 7 жыл бұрын
When you are surfing on the internet you are not really traversing a linked list data structure; Internet is more like a big (really big and keeps getting bigger every second) directed graph. Where you can get the feel of linked list is any image viewer on your system -- in its UI, '->' button is node->next; the '
@MasterGeekMX
@MasterGeekMX 7 жыл бұрын
I'm studying computer sicences in a mexican university and we have two data structure courses wich covers this topic in depth (alongside with other things like trees and graphs). Even we need to program from scratch the lists. That courses name (translated from spanish) are: Object-Oriented Algorythms and Linear Storing Patterns and Object-Oriented Algorythms and Non-Linear Storing Patterns
@wildgoosespeeder
@wildgoosespeeder 7 жыл бұрын
That's probably why a recursive function is better to search for entries in a linked list instead of an array because you don't need to specify an index because there is no index for each entry of a linked list. If no result is found, null (tail or head of the linked list) will terminate the recursive function. Else it will loop forever.
@Junk_bucket
@Junk_bucket 7 жыл бұрын
What's the difference between linked lists compared to Queues and deque's?
@justin1997sucks
@justin1997sucks 7 жыл бұрын
is this something like array list?
@Wh1ms_
@Wh1ms_ 7 жыл бұрын
Is there any reason to use an Array over the implementation of a Linked List?
@Wh1ms_
@Wh1ms_ 7 жыл бұрын
***** So would an ArrayList just be better than an Array at everything?
@Croxmata
@Croxmata 7 жыл бұрын
I like the term "non-blow-away-able".
@CODcanbefornoobs
@CODcanbefornoobs 7 жыл бұрын
please do more videos on data structures
@nienke7713
@nienke7713 7 жыл бұрын
Would going to the ISS page not only break the NASA Armstrong link but also the ArmstrongApollo11 link, because if from ISS you'd go back to NASA and click the Armstrong link again, your forward button doesn't suddenly allow you to go forward to Apollo11 again
@nienke7713
@nienke7713 7 жыл бұрын
Peterolen mmm... yeah, didn't think about that, thanks for the explanation :)
@jakerado4236
@jakerado4236 7 жыл бұрын
So Applied Arithmetic Sequence?
@Theraot
@Theraot 7 жыл бұрын
nope Edit: sure, you can consider each node as entity, and then you have a function that takes that entity and returns the contained value, and another function that takes the entity and returns the next node. In that abstraction it is similar to a sequence (That would be a function that takes the entity and return a pair of value and the next entity, right?)... as you can see, the value of each node doesn't depend on the value of the previous one. And even if it were, there is no constraint to make it an arithmetic sequence in particular.
@MyAce8
@MyAce8 7 жыл бұрын
I used a linked list for a gamestate manager, the current gamestate was the head of the list and every time you started a new state (like if you opened you inventory) I would push the new state on to the the stack, and since I never had more than 3 items in the list, even if I had to access a state at the bottom of the list (which was never actually necessary) it wouldn't be to costly, that being said in retrospect it was dumb considering it would have virtually no performance benefit, and all I accomplished was wasting my time implementing a linked list in lua for one stupid purpose
@Fransamsterdam
@Fransamsterdam 7 жыл бұрын
Don't worry too much about the noise. I have seen many videos from Royal British Famous Institutions which were worse.
@giancarloandrebravoabanto7091
@giancarloandrebravoabanto7091 3 жыл бұрын
why in the singly linked list you show an example of numbers? and for the doubly linked list you show an example of objects?
@mrfashionguy1
@mrfashionguy1 5 жыл бұрын
So a linked list is like back to the future basically.. you can go back and forth as much as you want until you change something, which them alters your "future" in the list.
@memo6032
@memo6032 2 жыл бұрын
I can't believe that I've never noticed that when I create a new nod or action in things like do and undo or backward and forward buttons in a browser, I delete the previous forward history! I can't also believe I finally get this thing 😌 I couldn't get it in class and it's really been bothering me.
@austinbaldwin7836
@austinbaldwin7836 7 жыл бұрын
What happens when item 1 points to item 2 and item 2 points to item 1?
@Yupppi
@Yupppi 6 ай бұрын
The linked list surely creates an exciting pointer handling job, but is cool if your only option is to always access heap.
@HardwareAddiction
@HardwareAddiction 11 ай бұрын
Why array wouldn't work for browsing history?
@unpronouncable2442
@unpronouncable2442 7 жыл бұрын
I am confused here a bit. if I have a list and I want to insert an element between 5'th and 6'th from the start then search operation will take me not n (I'm assuming n is the length of the list) but rather 5 if I want to place my element between 6'th to last and 5'th to last I then search will be n+(n-6) right?
@gabrielguedes6643
@gabrielguedes6643 7 жыл бұрын
Unpronouncable In this case n is not the length. If there are L elements and you want to add a new one after the N element (where N
@unpronouncable2442
@unpronouncable2442 7 жыл бұрын
Aaaah I see. thank you
@d3line
@d3line 7 жыл бұрын
N usually *is* the length when computer scientists talk about algorithmic complexity. If Dr Alex mentioned somewhere that lookup for element takes N lookups he was talking about worst case. Also 6'th to last and 5'th to last insertion can be done in N lookups if you create second variable, that is trailing behind current element by 6 elements.
@hellterminator
@hellterminator 7 жыл бұрын
He's talking about asymptotic complexity and n really is the length of the list here. Massively simplified: You want to know how long an operation will take in relation to the size of data (more generally problem), so you look at the average case. On average you'll have to traverse half the list to insert an element, so the operation takes n/2 and when dealing with asymptotic complexities, you don't care about constants, so you drop the half and are left with Θ(n).
@dragec48
@dragec48 7 жыл бұрын
which book does he have on the table ?
@dragec48
@dragec48 7 жыл бұрын
I found, it is "Data Structures and Algorithms in Java: WileyPLUS" by Michael T. Goodrich. :D
@tobortine
@tobortine 7 жыл бұрын
Usually link lists contain two addresses, the forward link address and the address of the data element. Also, I've always pointed the last link to the first such that you can detect the end when the head address is the same as the final link address.
@fablungo
@fablungo 7 жыл бұрын
Unless your list is a list of primitives. I think it's better to point to null at the tail: checking if an address is zero is less computationally expensive than a comparison which may require loading the head value into a register to see if they are equal. It also blurs the responsibility in code as to who is going to determine that its the end of the list: at what point is the comparison made, and after the comparison is made what is the function going to do? If it's going to return null, you might as well have had null as the next pointer and not have to do any checks when reading the next pointer (leaving them to when the function caller checks if null).
@HiddenWindshield
@HiddenWindshield 7 жыл бұрын
Doubly-linked lists are different than singly-linked lists. Doubly-linked should only be used when you need to move backwards in the list, otherwise, it's a waste of both memory and processor cycles. Same with circular linked lists (where the tail points back to the head), but in this case, you're not losing anything, so that's more of a style choice than anything.
@tobortine
@tobortine 7 жыл бұрын
Yes very true, I hadn't consider the list of primitives. I don't disagree about the null end pointer, it's really a style choice. There's not a lot in it computationally.
@jpratt8676
@jpratt8676 7 жыл бұрын
tobortine It's a little more than a style choice. If you use null you don't have to pass the head around with each computation. It's a small cost but still worth remembering
@tobortine
@tobortine 7 жыл бұрын
Why do you have to pass the head around? With each new link address you compare it to the head address as opposed to comparing it to null. No extra overhead.
@shikharupadhyay7435
@shikharupadhyay7435 4 ай бұрын
Awesome ❤
@timh.6872
@timh.6872 7 жыл бұрын
minor nitpick: in the drawing, the arrows point to the following pair. in the generated graphic, the arrows point to the *element* of the next pair. The latter is technically incorrect. Also, the last element doesn't point to null, its pointer *is* null.
@fablungo
@fablungo 7 жыл бұрын
I know he is just demonstrating on paper and showing the concepts but breaking the link before creating the new link for an insert operation is likely to cause concurrency problems. If you do it the other way around, you can do an atomic replacement of the pointer from "1" and "26" would already be pointing "2" (and not appear like the end of the list if a concurrent iteration of the list is taking place).
@fablungo
@fablungo 7 жыл бұрын
If I am not mistaken doing the same for a doubly-linked list would still be advantageous. Setup the links in the new node (next and prev) then change the next and prev of the prev and next respectively. The only problem that might occur between setting the new pointers is of consistency but an inconsistent state is better than an incorrect one. Although, since you can't do it atomically (at least I don't think you can set two addresses atomically) then this could cause a problem depending on what your application is doing.
@Bunny99s
@Bunny99s 7 жыл бұрын
That doesn't really solve concurrency. It might depend on the language / framework and the actual usecase though. If you have another thread currently iterates the list and you "cut off" a part two things could happen: Either the other thread is still before your cutting point in which case there's no problem. However if the other thread is already beyond the cutting point, how do you remove / destroy the cut-away nodes? You as the one who's changing the list can not know if someone is still using those nodes or not. If you want a datastructure thread-safe there are many ways to achieve this but it highly depends on the usecase and the language / framework. I mention that since frameworks like .NET / Mono or the Java VM have managed memory so you don't have to worry about invalidating memory (unless you use a node-pool) whereas in languages like C or C++ you have to free the memory yourself. Doing lock-free implementations is a dangerous field where you have to consider all possible cases. If you want to be safe, implement proper synchonisation in which case it doesn't matter in which order you update the pointers ^^. ps: How is inconsistant state better than incorrect state? If it's inconsistant it IS incorrect ^^. Inconsistancy is the worst you can do to your program, ever. You should never accept even the slightest bit of inconsistancy as it will, sooner or later, cause a race-condition in a multi-threaded environment.
@GenGariczek
@GenGariczek 7 жыл бұрын
He was talking about linked list, not concurrent linked list. Off-topic.
@prim16
@prim16 7 жыл бұрын
That bothered me too. If you break the link to Node 2....it will be forever lost in memory....as well as every Node that it and its latter Nodes were referenced by.
@mariohernandez6590
@mariohernandez6590 7 жыл бұрын
This is just a high level example... Not actually implementing the functions to add a node... lol relax
@topphemelig
@topphemelig 7 жыл бұрын
Sounds like a queue list, with only one link it will just jump forward as you dequeue.
@ushakarreddy1981
@ushakarreddy1981 3 жыл бұрын
excellent..
@irrigger1
@irrigger1 7 жыл бұрын
Vim represent!
@MrJackojc90
@MrJackojc90 7 жыл бұрын
What would be the advantage of using this over a traditional array?
@JeyJeyKing1
@JeyJeyKing1 7 жыл бұрын
Jack Clarke didn't you watch the video m8
@MrJackojc90
@MrJackojc90 7 жыл бұрын
I did, So it's basically just the fact that it's much more flexible than a normal array?
@lorenzorossi2000
@lorenzorossi2000 7 жыл бұрын
You can add/remove objects to the list in O(1) and it doesn't need to grow (prevents some attacks and for some big lists, faster) but it's slow in iterating, so it depends on the usage
@MrJackojc90
@MrJackojc90 7 жыл бұрын
Interesting, Thanks for clearing it up!
@JeyJeyKing1
@JeyJeyKing1 7 жыл бұрын
SnowyCoder it's not slow to iterate, the only thing it does slower than an array is random access look up.
@disk0__
@disk0__ 7 жыл бұрын
I love the comments telling the Doctorate how he should have done something
@LeducDuSapin
@LeducDuSapin 7 жыл бұрын
Kudos for mentioning vim and its history tree
@realraven2000
@realraven2000 7 жыл бұрын
Bad example. you should have inserted the number "1.4" :) If you look at dictionaries, internally these are often realized as linked lists. This could theoretically also be done with Arrays - once you add a layer of abstraction there is no need to use contiguous memory for them.
@digitaldina
@digitaldina 6 жыл бұрын
I don't mind the traffic audio. It makes the video interesting.
@joaofnds
@joaofnds 7 жыл бұрын
Remember folks, double pointer FTW
@Darigitin
@Darigitin 7 жыл бұрын
One comment I felt is needed on this video to any students possibly watching this, when adding or deleting a node, you always make the new links before you remove the old ones. It was really bugging me when he was removing the old links before making the one ones. If you delete the link between 2 and 3 before you create the link from 26 to 3, you will lose access to 3 and all subsequent nodes.
@ailuros_
@ailuros_ 6 жыл бұрын
oh, i miss the subtitles :|
@robmckennie4203
@robmckennie4203 7 жыл бұрын
couldn't think of something more natural to come between 1 and 2? like 1.5?
@AgentM124
@AgentM124 7 жыл бұрын
If you paste your secrets somewhere, don't delete them, but undo them and overwrite the redo history. that way if somebody sneaks up on your word document, they won't find out... unless they are really geeky and for some reason it's still stored in memory... but realistically... meh.
@kipbush5887
@kipbush5887 7 жыл бұрын
Brought to you by Frank Harris & CO
Arrays vs Linked Lists - Computerphile
29:57
Computerphile
Рет қаралды 492 М.
Why You Should AVOID Linked Lists
14:12
ThePrimeTime
Рет қаралды 272 М.
Alex hid in the closet #shorts
00:14
Mihdens
Рет қаралды 10 МЛН
Scary Teacher 3D Nick Troll Squid Game in Brush Teeth White or Black Challenge #shorts
00:47
Playing hide and seek with my dog 🐶
00:25
Zach King
Рет қаралды 31 МЛН
Cat Corn?! 🙀 #cat #cute #catlover
00:54
Stocat
Рет қаралды 16 МЛН
Computer Science ∩ Mathematics (Type Theory) - Computerphile
15:56
Computerphile
Рет қаралды 262 М.
Why Linked Lists vs Arrays isn’t a real choice
9:15
SimonDev
Рет қаралды 308 М.
AES: How to Design Secure Encryption
15:37
Spanning Tree
Рет қаралды 153 М.
Python Regular Expressions - Computerphile
22:16
Computerphile
Рет қаралды 53 М.
you will never ask about pointers again after watching this video
8:03
Low Level Learning
Рет қаралды 2,1 МЛН
Cracking Enigma in 2021 - Computerphile
21:20
Computerphile
Рет қаралды 2,4 МЛН
Fast Inverse Square Root - A Quake III Algorithm
20:08
Nemean
Рет қаралды 5 МЛН
Premature Optimization
12:39
CodeAesthetic
Рет қаралды 774 М.
Linked List - Data Structures & Algorithms Tutorials in Python #4
28:16
Big O Notation
8:37
HackerRank
Рет қаралды 1,6 МЛН
Alex hid in the closet #shorts
00:14
Mihdens
Рет қаралды 10 МЛН