Linked Lists - Computerphile

Share
Embed
  • Published on Jan 20, 2017
  • 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: thexvid.com/video/jiHuPbUGlBE/video.html
    facebook.com/computerphile
    twitter.com/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

Comments • 426

  • Oh Yeahhh
    Oh Yeahhh Month ago

    By the look on his face, its like Brits hate themselves lol

  • User Unknown
    User Unknown Month ago

    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.

  • Blue Tree Code
    Blue Tree Code Month ago

    If you need further help with searching, insertion and deletion in Java, I have a tutorial on Linked Lists with animations to make it easy to grasp.

  • Dr. Guy Madison
    Dr. Guy Madison 2 months ago

    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.

  • Adam Warlock
    Adam Warlock 3 months ago

    Couldn't you keep the forward history though using another linked list to handle forward and back histories, okay I just figured out what's wrong with what I'm saying lol

  • isac
    isac 4 months ago

    Thank you for the lesson

  • Meh Kay
    Meh Kay 5 months ago

    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

  • john
    john 8 months ago

    well shot and edited

  • Q(t)=π
    Q(t)=π 8 months ago

    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?

  • Max Eisenhardt
    Max Eisenhardt 8 months ago +1

    Nice! Especially the case examples you used.

  • Gin Zeng
    Gin Zeng 9 months ago

    it's vrey funny : )

  • 陈瀚龙
    陈瀚龙 9 months ago +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.

  • Noah Pillow
    Noah Pillow 10 months ago

    thumbs up for learning how to throw away my future

  • Felipe Martins
    Felipe Martins 11 months ago

    oh, i miss the subtitles :|

  • izcool100
    izcool100 Year ago

    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.

  • Dina Elhanan
    Dina Elhanan Year ago

    I don't mind the traffic audio. It makes the video interesting.

  • Ashton Scalise
    Ashton Scalise Year ago

    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.

  • James Yeoman
    James Yeoman Year ago

    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)

  • Ryan Mease
    Ryan Mease Year ago

    The live example with the animation running as he explains it is great.

  • Sumit Singh
    Sumit Singh Year ago

    British people are adorable.

  • Daniel
    Daniel Year ago

    nice phone cover

  • osmar herrera
    osmar herrera Year ago

    u cute

  • Isma Rekathakusuma

    This video Doesn't explain the concept of link list.

  • John Jones
    John Jones Year ago

    Linked lists for browser history is a good example of a graph-based data structure that was implemented as a linked list and ruined my life. There are others.

  • MM!!
    MM!! Year ago

    It sure didn't feel simple when I had to build it in the Kingdom of Nouns.

  • CommanderLake
    CommanderLake 2 years ago

    Ooo a dumper truck!

  • Anthony Hartwig
    Anthony Hartwig 2 years ago +1

    Nerds make me happy. Makes me miss the CS culture from college. Keep up the awesomeness on this channel!

  • Jayyy Zeee
    Jayyy Zeee 2 years ago

    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.

  • 2swap
    2swap 2 years ago

    Could you have a looped linked list? 1>2>3>back to 1 or something like that

    • marq
      marq Year ago

      yea its called a Circularly linked list

  • Joseph Ang
    Joseph Ang 2 years ago

    In real life very few programmers use Linked Lists directly, and when they do they use a Library, or they use a "growable aeeay" that is really implemented as a highly advanced data structure that probably is a hybrid between an array and a linked list.

  • nullternative
    nullternative 2 years ago

    Browser history demonstrates a stack. Not the best analogy for a linked list.

  • Babek Evomer
    Babek Evomer 2 years ago

    Why would anyone use a list or stack, when vectors are way easier and do all the same stuff?

  • dimitris dimitriou
    dimitris dimitriou 2 years ago

    you got Goodrich and Tamassia book?

  • Vivek Pal
    Vivek Pal 2 years ago

    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 '

  • Nienke Fleur Luchtmeijer

    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

    • Nienke Fleur Luchtmeijer
      Nienke Fleur Luchtmeijer 2 years ago

      Peterolen mmm... yeah, didn't think about that, thanks for the explanation :)

    • Peterolen
      Peterolen 2 years ago

      You'll probably create a new node each time you visit a page. The same page could occur multiple times in the history so reusing one single node for each page wouldn't really work anyway.

  • Jeffrey Lee
    Jeffrey Lee 2 years ago

    Can you please do a video on segment tree

  • AssailantLF
    AssailantLF 2 years ago

    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.

  • dragec48
    dragec48 2 years ago

    which book does he have on the table ?

    • dragec48
      dragec48 2 years ago

      I found, it is "Data Structures and Algorithms in Java: WileyPLUS" by Michael T. Goodrich. :D

  • Kankerdick Lemur
    Kankerdick Lemur 2 years ago

    Is there any reason to use an Array over the implementation of a Linked List?

    • Kankerdick Lemur
      Kankerdick Lemur 2 years ago

      @Peterolen So would an ArrayList just be better than an Array at everything?

    • Peterolen
      Peterolen 2 years ago

      One of the advantages of using arrays is that you can directly jump to any element by using an index.

  • CODcanbefornoobs
    CODcanbefornoobs 2 years ago

    please do more videos on data structures

  • Ace shinigami
    Ace shinigami 2 years ago

    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

  • Realraven2000
    Realraven2000 2 years ago

    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.

  • Austin Baldwin
    Austin Baldwin 2 years ago

    What happens when item 1 points to item 2 and item 2 points to item 1?

    • Peterolen
      Peterolen 2 years ago

      If this is a singly linked list it means you have implemented it incorrectly.

  • Daniel G.
    Daniel G. 2 years ago

    tablet mode test

  • QuomoZ
    QuomoZ 2 years ago

    I hope at this channel makes a video about algebraic data types and how to define a linked list using them.

  • nunya biznez
    nunya biznez 2 years ago

    what a terrible explanation. it's like taking an overly excited yet uncommitted kid wanna-be programmer and telling them they know enough to teach others.

  • Mister J
    Mister J 2 years ago

    Please do hash tables.

  • Hoggerpop
    Hoggerpop 2 years ago

    is this something like array list?

    • Peterolen
      Peterolen 2 years ago

      ArrayList in Java is not a linked list. Instead it uses an array underneath.

  • bighugejake
    bighugejake 2 years ago

    never record a video on the sidewalk again please.

    • John Sprunger
      John Sprunger Year ago

      Never record yourself playing guitar again.

  • wildgoosespeeder
    wildgoosespeeder 2 years ago

    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.

  • qwaqwa1960
    qwaqwa1960 2 years ago

    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.

  • SuperStewie
    SuperStewie 2 years ago

    Can you do one on positional lists next?

  • JunkBucket
    JunkBucket 2 years ago

    What's the difference between linked lists compared to Queues and deque's?

    • Peterolen
      Peterolen 2 years ago

      Queue is an _abstract datastructure_ that allows you to add things at the back and take things from the front. You could use a linked list to implement a queue, but it's not the only way.

  • Gabriel Kressin
    Gabriel Kressin 2 years ago

    You just could use an array for the browser, can't you?

    • Martin Towell
      Martin Towell 2 years ago

      An array is, generally speaking, a set size. One doesn't know how many links a person will follow so can't really have a set sized history. If you set it to, say, 100, and the user only visits 5 links, then you're wasting all that memory. If you, conversely, set it to 5 and they visit 100 links, then your array isn't long enough. The benefits of a linked list is that the length is dynamic and can grow and shrink as needed.

    • Peterolen
      Peterolen 2 years ago

      I thought the same thing.

  • Woozeesh
    Woozeesh 2 years ago

    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.

  • Big Mofo
    Big Mofo 2 years ago +1

    Wow. That was boring. The Internet is full of newbie programming tutorial already.
    Try to make interesting video next time. We don't need more of the same.

    • John Sprunger
      John Sprunger Year ago

      Well, someone is pretty cunty, why don't you post a link to your well edited infromative videos? lol

    • Peterolen
      Peterolen 2 years ago +1

      What I like about these videos is that you don't need to know anything about the subject in order to follow along. I have watched a few computerphile and numberphile videos with my brother and even if we are on different levels it works great for starting interesting discussions. I wouldn't use computerphile for serious learning purposes.

    • BlinkY
      BlinkY 2 years ago

      Define interesting? What's considered newbie and what isn't? Not the best explained video I admit also - some vital keywords were left out. But for some, this may open doors and point people in the right direction.

  • longcat
    longcat 2 years ago

    talking a bit too fast at the beginning... for my tastes

  • Henry van Megen
    Henry van Megen 2 years ago

    Are you guys sponsored by Frank Harris & Co ?

  • Lycanite
    Lycanite 2 years ago

    Those null pointer exceptions though...

    • Big Mofo
      Big Mofo 2 years ago +1

      What is the alternative? Use terminator value that is within addressable range so that all your data become corrupted instead of faulting? Thanks brilliant. gg.
      That segfault is good. It tell you that you have a bug.

  • BeltedYapper
    BeltedYapper 2 years ago

    I've had to retake a class on linked lists... in java...

  • Positive Mental Attitude

    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.

  • Christopher Bush
    Christopher Bush 2 years ago

    Brought to you by Frank Harris & CO

  • Fransamsterdam
    Fransamsterdam 2 years ago

    Don't worry too much about the noise. I have seen many videos from Royal British Famous Institutions which were worse.

  • Ruxify
    Ruxify 2 years ago

    Hmm... I just use std::vector for this purpose.

    • Peterolen
      Peterolen 2 years ago

      That's what I would have used too.
      For those that don't know it, std::vector is implemented using arrays.

  • Trevor Pike
    Trevor Pike 2 years ago

    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.

  • Diogo Folques
    Diogo Folques 2 years ago +11

    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 2 years ago +3

      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

  • Vexatos
    Vexatos 2 years ago +6

    I like the term "non-blow-away-able".

  • TheMasonX
    TheMasonX 2 years ago

    Today I used doubly linked lists while making a spline tool for path editing :)

  • David Yue
    David Yue 2 years ago

    On Wikipedia, the chain doesn't break, the last node is always Philosophy.

  • Daniel Houck
    Daniel Houck 2 years ago +1

    Was anybody else bothered by the memory leak in his back history explanation?

    • Peterolen
      Peterolen 2 years ago +2

      Maybe he used a language with garbage collection (e.g. Java).

  • CK
    CK 2 years ago

    One of the worst data structures for data locality (cpu cache and ooo execution) as well as memory overhead (because of additional memory pointers). Excluding temporal retrieval/insertin complexity.

  • Mateen Ozil
    Mateen Ozil 2 years ago

    can you do a video on time & memory complexity?

  • Rik Wisselink
    Rik Wisselink 2 years ago

    There's a back to the future joke waiting to happen at the end.

  • GreenOlvi
    GreenOlvi 2 years ago +10

    9:20 my thought 'unless you're using vim'. Few seconds after in the video 'unless you're using something like vim'. Great video :-)

  • Craig Rotay
    Craig Rotay 2 years ago

    I'm very impressed with Dr A here bcs he is so simplifying a concept that is extremely complicated.

  • Redok09
    Redok09 2 years ago

    Just an fyi for Computerphile and everyone I guess, the diagrams you did are a little bit wrong. The arrows should not be pointing inside the nodes, because this would mean the association is made with the value inside the node and not the actual node. As you can see, when Dr Alex Pinkney made his drawing on paper, he respected this law. He made the arrows pointing at the node, not inside of it.

  • Leduc DuSapin
    Leduc DuSapin 2 years ago

    Kudos for mentioning vim and its history tree

  • Jetman640
    Jetman640 2 years ago

    seems alot like Trees to me

  • Nathan Pierce
    Nathan Pierce 2 years ago

    I was just going over this in CS50! now do tries! Those hurt my brain :P

  • Cold Ham on Rye
    Cold Ham on Rye 2 years ago +77

    Jesus christ. I said this on another video but the computerphile community is toxic. Like they criticize the shit out of every video.

    • MrSnowman
      MrSnowman 2 years ago +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.

    • Attila-Mihaly Balazs
      Attila-Mihaly Balazs 2 years ago +3

      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.

  • Steve Lindsey
    Steve Lindsey 2 years ago

    True nerd, writes on green bar paper. Respect!

  • apenasmeucanal
    apenasmeucanal 2 years ago

    Bjarne sweedsweedish told me not to use those

  • MGMX
    MGMX 2 years ago

    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

  • Rob Mckennie
    Rob Mckennie 2 years ago

    couldn't think of something more natural to come between 1 and 2? like 1.5?

  • Michael Bradley
    Michael Bradley 2 years ago

    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

  • IceMetalPunk
    IceMetalPunk 2 years ago +3

    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.

    • Kvozart
      Kvozart 2 years ago

      Bunny83, then array with one/two (head/write, tial/read) indexers are used. Don't forget - links also consume memory

    • AnotherUselessNick
      AnotherUselessNick 2 years ago

      @Bunny83 fair 'nuff

    • Bunny83
      Bunny83 2 years ago +1

      +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.

    • AnotherUselessNick
      AnotherUselessNick 2 years ago +1

      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.

    • Adam Leuer
      Adam Leuer 2 years ago

      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.

  • Alied Pérez Martínez
    Alied Pérez Martínez 2 years ago +1

    2:43 _nil_ in Pascal.

  • Creatchture
    Creatchture 2 years ago

    I think you just described time travel.

  • Veerle Groot
    Veerle Groot 2 years ago +3

    what happens to the linked list elements that are cut away when you click another link in memory terms?

    • Rob Mckennie
      Rob Mckennie 2 years ago +15

      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

  • irrigger1
    irrigger1 2 years ago +6

    Vim represent!

  • Star
    Star 2 years ago

    I do not recall using linked lists in a real application ever
    it is just that weird thing that we learned in college

    • Peterolen
      Peterolen 2 years ago

      Big Mofo, when you say "built-in", do you mean built in to the language, or part of the standard library?
      In C++ I can think of one data structure that is built in to the language and that is arrays.
      Some, but far from all of the containers in the C++ standard library use linked lists. std::list and std::forward_list is obviously using linked lists but that's what they are supposed to be. The hash set/map types are probably using singly linked lists for the buckets.
      There is no need for the the sequential containers std::array, std::vector and std::deque to use linked lists. The associative containers std::set and std::map are normally implemented as binary search trees.

    • Big Mofo
      Big Mofo 2 years ago +2

      Whatever toy programming language you are using, all it's build-in data structure are done with linked list. So you are using linked list. You are just ignorant. But that's not surprising.

    • Ahsim Nreiziev
      Ahsim Nreiziev 2 years ago

      I would suggest you read a bit through the comment section. You know, to get perspectives from different parts of the Industry to see if they match up with your own.
      Other commenters who are (also?) working in actual programming jobs have said that they *do* use Linked Lists in "real applications" _[whatever that means, exactly]_ quite frequently. Especially if the Programming Language they code in is a Functional one.

  • Matt G.
    Matt G. 2 years ago

    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.

  • Unpronouncable
    Unpronouncable 2 years ago

    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?

    • hellterminator
      hellterminator 2 years ago +3

      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).

    • Deline
      Deline 2 years ago +1

      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.

    • Unpronouncable
      Unpronouncable 2 years ago

      Aaaah I see. thank you

    • Gabriel Guedes
      Gabriel Guedes 2 years ago

      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

  • Maqbool
    Maqbool 2 years ago +2

    All items in linked lists are linking to Chuck Norris.

  • Zero Cool
    Zero Cool 2 years ago +1

    You don't break links. You just change them. When adding a new node, it's important to copy the link from the previous node, before changing it, because otherwise you loose the rest of the list.

  • xN811x
    xN811x 2 years ago

    And this probably is the reason why prepending in Haskells lists is way faster then appending...

    • SuperManitu1
      SuperManitu1 2 years ago

      MrSnowman If you allow for mutability, you loose the advantages of immutable data structures. You cannot garantuee that there wont be race conditions (which cant happen if you dont change your data).
      So yeah, even on compile level, the list will be recreated, because part of the program might need the original one somewhere else

    • MrSnowman
      MrSnowman 2 years ago

      They're immutable on the AST level I get.
      But in compilation/interpretation surely they allow for mutability right? In properly checked programs I don't see why they'd decide to live with that constraint.

    • SuperManitu1
      SuperManitu1 2 years ago

      QuomoZ This is only true for prepending. As every member of the list has a reference to the next one, you would have to alter the last element in the list the add the reference to the newly created element. So it will be recreated, this would change the reference of the previous, so you recreate that and so on and so on. Structural sharing works only for prepending

    • QuomoZ
      QuomoZ 2 years ago +2

      Actually, because everything is pure in Haskell (unless using unsafe), a new list is not created when an element in prepended or appended. The list before the operation and the list after the operation "share" as the whole original list.
      If, afterward, an operation that changes all elements of the prepended list takes place, THEN the whole list is duplicated.
      Appending in Haskell is generally slower because the whole list has to be traversed in order to get to the end.

    • xN811x
      xN811x 2 years ago

      +LordBlackhole Ahhh okay that makes sense

  • Fabrizio Lungo
    Fabrizio Lungo 2 years ago +30

    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).

    • Kvozart
      Kvozart 2 years ago

      But, people often use that kind of examples without thinking. It's better to say in right way at first place than explain more and more additionally

    • mario hernandez
      mario hernandez 2 years ago

      This is just a high level example... Not actually implementing the functions to add a node... lol relax

    • Primaski
      Primaski 2 years ago

      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.

    • Filip 'GenGariCZek' Kejnar
      Filip 'GenGariCZek' Kejnar 2 years ago

      He was talking about linked list, not concurrent linked list. Off-topic.

  • David Chipman
    David Chipman 2 years ago

    Why is he doing this talk out on the sidewalk?

  • Fabrizio Lungo
    Fabrizio Lungo 2 years ago

    If you are learning functional programming then I can understand linked list being taught first... But otherwise, don't you learn about arrays first?

  • tobortine
    tobortine 2 years ago

    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.

    • Peterolen
      Peterolen 2 years ago

      I don't understand why it matters if you're storing primitives or class objects in the list. The nodes are not going to be copied so you don't need to worry about the size of the nodes, so why not just store the objects inside the node itself and avoid the extra indirection?

    • tobortine
      tobortine 2 years ago

      Let me start by saying that there is little in it either way. However, everything is stored in memory, whether it's a constant generated by the compiler or a variable stored during execution. Look at the compiler assembler output for your pseudo code example and you'll find there there is very little difference in the code. Of course different compilers and different languages will generate different assembler(machine) output so ultimately it's a moot point. It's not a big deal and modern day computers will cope with either method but I still maintain it's more style than practicality.

    • Fabrizio Lungo
      Fabrizio Lungo 2 years ago

      @tobortine Null is 0, you don't need to know the value of null. Not only is it a constant that is defined by your language and replaced at compile time, comparing to zero (null) will be a single CPU cycle with no need to fetch from memory.
      To compare to the head you need to know within your scope what the value of head is to be able to do the comparison and so the head must be passed.
      A pseudo code example with some list object showing how the null value is usable without a comparison:
      Using head as the end of the list:
      ```
      if list.next() != list.head: # Reached end of list
      ```
      Using null as the end of list:
      ```
      if !list.next(): # Reached end of list
      ```
      Say you have a large list and your walking the list, you need to do one of the following:
      ```
      while (ptr = list.next()) == list.head:
      # Do some work using `ptr`
      ```
      ```
      while ptr = list.next():
      # Do some work using `ptr`
      ```
      Sure you will get cache hits after the first few operations and if your lucky context switching won't happen resulting in the register values being unloaded, but in general its an extra memory access for each step in your walk.
      I think using null at the end is the generally accepted implementation UNLESS you want a circular linked list, in which case your tail would link to your head, but that's a different data-structure for different use cases.

    • tobortine
      tobortine 2 years ago

      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.

    • Joshua Pratt
      Joshua Pratt 2 years ago +1

      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