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

Comments • 426

  • lashe adebayo
    lashe adebayo Month ago +2

    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!

  • User Unknown
    User Unknown 4 months 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 4 months 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 5 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 6 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 7 months ago

    Thank you for the lesson

  • Meh Kay
    Meh Kay 8 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 11 months ago

    well shot and edited

  • Q(t)=π
    Q(t)=π 11 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 11 months ago +1

    Nice! Especially the case examples you used.

  • Gin Zeng
    Gin Zeng Year ago

    it's vrey funny : )

  • 陈瀚龙
    陈瀚龙 Year 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 Year ago

    thumbs up for learning how to throw away my future

  • Felipe Martins
    Felipe Martins Year 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 2 years ago

    u cute

  • Isma Rekathakusuma
    Isma Rekathakusuma 2 years ago

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

  • John Jones
    John Jones 2 years 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!! 2 years 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 +2

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