This video is unavailable.
Sorry about that.

Data Structures: Arrays vs Linked Lists

Share
Embed
  • Published on Apr 2, 2013
  • See complete series on data structures here:
    thexvid.com/p/PL2_aWCzGMAwI3W_JlcBbtYTwiQSsOTa6P
    In this lesson we will compare arrays with linked lists based on various parameters and understand the cost of various operations with these data structures.
    Lessons on big-oh notation can be found in these series on time complexity:
    thexvid.com/p/PL2_aWCzGMAwI9HK8YPVBjElbLbI3ufctn

Comments • 184

  • cool rowdy
    cool rowdy 7 hours ago

    Kindly any one clarify my doubts..
    in linked list why to traverse the entire list inorder to add the new node at the end.
    Instead just maintain a static variable inside the linked list class that will always hold the end address of the list.
    inadditon why to have the head variable to store the starting address can we not just access the starting address of the list which is gonna be the same.
    eventhough if you want to add the node at the beginning of the list you just have to change the address of the list to the new node created at the beginning .
    why waste 4 byte variable head for storing starting address?????????????

  • RUPRAJ ROY
    RUPRAJ ROY 15 days ago

    Instead of dynamically memory allocation why arrays are of fixed size

  • Alex Joslin
    Alex Joslin 20 days ago +1

    Correction: time complexity for inserting at the end of a linked list is O(1) if you have a tail pointer pointing to the last node of the list.
    Example (in Python):
    class Node:
    def __init__(self, d):
    self.data = d
    self.next = None
    class LinkedList:
    def __init__(self, d):
    self.head = Node(d) # Head stays the same
    self.tail = self.head # Tail points to ending Node
    def append(self, d):
    self.tail.next = Node(d) # NEW NODE
    self.tail = self.tail.next

  • NYNC Alfa
    NYNC Alfa Month ago

    Shouldn't time complexity for inserting in between be O(i)?10:44

    • Ali Shah
      Ali Shah 3 days ago

      For inserting at i-th position we don't know the value of i so in worst-case scenario it could be at the end of the array. So time complexity would take O(n) where n is the length of the array.

  • maxima -
    maxima - Month ago

    love your tutorials. Wish you guys continued no matter what.

  • nitin tomar
    nitin tomar Month ago

    You are champ man ! Nicely explained

  • Yara Ye
    Yara Ye 2 months ago

    We will get our hands dirty....lol

  • sl Test
    sl Test 2 months ago

    Thank you very much for all the videos!!
    I have a question, in the linked list, inserting an element at the end and at ith position should be O(1), isn't it? Because only pointers need to be changed..? Only access to elements at the end and at ith position would be O(n)?

  • Kalyani ‘s Kitchen
    Kalyani ‘s Kitchen 3 months ago

    Isn’t deleting the last element in the array always constant time O(1)? We never have to resize the array or shift any elements

  • Konduru Bharath
    Konduru Bharath 4 months ago

    does a pointer variable require 4 bytes here..?? I heard from some sources that any pointer variable irrespective of the data type consumes 8 bytes..isnt this correct..???

  • Tanmay Kumar
    Tanmay Kumar 4 months ago

    he has the best playlist on linked list

  • aaron balthaser
    aaron balthaser 4 months ago +1

    Why is adding a node to the end of the list O(n)? If you maintain a tail you can add nodes to the list in constant time no different than added to the head. I have seen many implementations with both head and tail. Is a linked list with a tail not a valid implementation?

  • arfat inamdar
    arfat inamdar 4 months ago

    Very well explained, but subtitles are irritating a lot

  • Yash Tailor
    Yash Tailor 5 months ago

    I have a question, lets say in the linked list, if we keep the address of the last memory block then we can save the time of traversing the linked list by O(n) and it can be achieved in constant time.What about this? @mycodeschool

  • stillFLiP
    stillFLiP 6 months ago

    So, linked lists are better the larger the data is, right? For example dealing with strings, specially if you need to add new ones at the start, i.e. todo list.

    • Peterolen
      Peterolen 6 months ago

      Some kind of array-based data structure is often best.

  • Mayukh Biswas
    Mayukh Biswas 6 months ago

    one doubt. If we store the start and end nodes in separate pointers, then adding a new element at the end should take O(1), shouldn't it?

    • bipin singh
      bipin singh 5 months ago

      to Reach the end node in Linked List you have to start from head and reach till tail (Traverse across the list ) , so the time complexity is O(n)

  • Cindy Shi
    Cindy Shi 7 months ago

    So tremendously helpful. Thank you so much!

  • Fatima Kashif
    Fatima Kashif 7 months ago

    oop java pey karain ye program linklist k programs

  • Drumpf Cheeto
    Drumpf Cheeto 7 months ago

    IN-TEE-YERS

  • Abdelghani Draoui
    Abdelghani Draoui 7 months ago

    Awesome course thanks for sharing !

  • Alireza Ghodsipoor
    Alireza Ghodsipoor 9 months ago +6

    I can watch your videos as a movie and not get bored :) Awesome!

  • Ayeman Bin Salauddin
    Ayeman Bin Salauddin 9 months ago +1

    amazing, i am preparing for googles kickstart.
    btw im 15 and python programmer ,web developer.

  • ahmed zahid
    ahmed zahid 9 months ago

    Thanks sir well done job

  • Sakshi Soni
    Sakshi Soni 11 months ago +1

    Can someone tell me that these videos are helpful for the gate (for data structure) preparation or not?

  • Jakub Lorenc
    Jakub Lorenc 11 months ago

    i think deleting at the end of array is O(1), not O(n) so deleting times are not the same

  • Aritra Das
    Aritra Das Year ago +8

    The way you explain, I could listen to these videos for hours and not get bored. Absolutely mindblowing content man, keep doing the good work.

  • Belal Abdulnasser

    Good explanation, I think you have error at the point of adding item in the end and middle of linked list

  • Toufique Hasan
    Toufique Hasan Year ago

    Apne liKh rhe aur khud samj rhe ho

  • Iqbal Mohamad
    Iqbal Mohamad Year ago +1

    dude,you basically just saved me my whole semester studying with difficult lecture before,now all is ez

  • Nagalakshmi Duvvuri

    These are very helpful, Thanks so much for making the videos

  • AdiTya Dev
    AdiTya Dev Year ago

    awesome

  • Amit Chhetri
    Amit Chhetri Year ago

    Why do we always write as
    Struct Node {
    int data;
    Node* next;
    }
    and not as
    Struct Node {
    int data;
    int* next;
    }
    What difference does this make?

    • Adarsh Todi
      Adarsh Todi 9 months ago

      (1)Node* next basically means a pointer next to a type of Struct Node.
      (2) int* next means a pointer next to a type int.
      The second implementation is completely wrong as we need a pointer to a next node(comprising of data and next pointer) and not an int type.

  • Samvit Agarwal
    Samvit Agarwal Year ago +1

    Hey this was a great video! Since I use Python, which uses dynamic arrays(arrayLists) by default, could you explain how exactly these work and the time/space complexity for these? Thanks

  • John Rhaenys
    John Rhaenys Year ago

    The time complexity to insert an element at the end of the linked list is O(n), since we only have the reference to the head and we have to traverse it until we get to the end of it. However, if we add another pointer that points to the last element of the list, the insertion at the end will be O(1), constant time. That being said, is it a good trade to use 4 more bytes to store the memory address of the last element and get a faster insertion?

  • Usama Iftikhar Butt

    thank u sir for such an amazing playlist

  • aditya verma
    aditya verma Year ago

    hi what about self referential pointers in a structure what amount of memory would they take?

  • Xavy Aly
    Xavy Aly Year ago

    can we get the same ppt in my mail id please: wellboy.alam13@gmail.com

  • KV M
    KV M Year ago

    Can't appreciate your videos enough. Following it religiously for my data structures journey. I have a question. seeing the comparision though, I don't see any good benefit of linked list at all. Mostly it is either comparable to arrays or it falls behind arrays and yeah, implementation is more time consuming and hard as well. Then why do we even use it? Just for one case of inserting at beginning where it scores better? Arrays are almost better or at par I mean! Sure we can compromise that one case. Memory these days should be not be an issue. So just why???

    • KV M
      KV M Year ago

      After my research, I feel very fine grain control over memory ( dynamic memory and implementation of stacks and queues ought to be the reason for it. Otherwise insertion and deletion are easy but have same time complexity.

  • MURALI KRISHNA
    MURALI KRISHNA Year ago +2

    The way you are teaching is superb and do you have pdf version or any other format notes for quick revise.thanks...;

  • ronald abellano
    ronald abellano Year ago +7

    I dont get the Memory requirements part. How does Linked List consume lot less memory if it uses more memory because of its pointer?

    • Amar bhardwaj
      Amar bhardwaj 5 months ago +3

      Because there is no unused memory in linked list.

  • ronald abellano
    ronald abellano Year ago

    Im confused. How does the array win over linked list in time complexity for accessing its elements?
    Linked List node uses its next pointer and how about array? How does array access its elements if Linked List always starts at the head?
    What are the operations for array if Linked List is Head links to next node? Head.Next

    • confidential303
      confidential303 9 months ago

      Array is simple, you know the size of an array.. if you want to read the 10th element, you just calculate begin memory address(200) + 10*(x bytes ..for int..we assume x=4)= 200 +40= so 10th element is at memory location 240.
      with linked list, you have to cycle through 10 times to get your memory address.., now the question is now the question is how long does 1 step take. In my opinion arrays wins almost in performance. since memory operations are slow..

  • Sambit Pati
    Sambit Pati Year ago

    please make videos on GATE entrance for computer science branch

  • Archit Atrey
    Archit Atrey Year ago

    Sir make a video on unrolled link lists

  • Youyi Liu
    Youyi Liu Year ago

    NEW BOOK: The Art of War by Sun Tzu, the first copy in the world to have those ancient words correctly reflected. Read it and get the job done!
    www.amazon.com/ART-WAR-Sun-Tzu/dp/1521303002/ref=sr_1_1?ie=UTF8&qid=1526481164&sr=8-1&keywords=the+art+of+war+Youyi+Liu
    Chinese-English version
    www.amazon.com/ART-WAR-Sun-Tzu/dp/1521311838/ref=sr_1_1?s=books&ie=UTF8&qid=1526481967&sr=1-1&keywords=youyi+liu+the+art+of+war

  • Akhil Jain
    Akhil Jain Year ago

    These videos are really helpful. You are doing a great job.!!!!! Please keep making more such videos.

  • Ashwin Karthikeyan

    All these videos on data structures are very useful. Thanks a lot. But can you upload videos of OOP using JAVA too please.

  • saurav yadav
    saurav yadav Year ago +1

    Your videoes are great. very useful for weak students like me .

  • Yashkirat Singh
    Yashkirat Singh Year ago +3

    When insetring an element at the end of a linked list why we will be needed to traverse whole memory.
    It can be done by changing the last pointer.

    • Mister Smith
      Mister Smith 5 hours ago

      @cool rowdy just use deque :) it allows you to access elements from both ends

    • cool rowdy
      cool rowdy 6 hours ago

      @Mister Smith i understood what i have asked is not possible in c.since the static variable cannot be declared inside a struct.
      so this cannot be done...
      thanks for the help ..
      note:
      but in c++ what i have asked previously is possible i guess.

    • cool rowdy
      cool rowdy 6 hours ago

      @Mister Smith what i am asking is suppose if we have a struct named list inside which if you have two variables one for storing value and another one(pointer) for storing address.
      why cant we have a third variable or pointer which may be static to store the last address of the list.
      since it is static the pointer can only be created by one instance and can be used by all the instances.
      eg:
      struct node
      {
      int value;
      node* next;
      static node* last;
      }

    • Mister Smith
      Mister Smith 7 hours ago

      @cool rowdy Im not really sure what you are asking but you must understand that linked list is already an established data structure and if you want to change something you can implement a new class that does whatever you want , most likely it will be ineffective , but if you are a great programmer maybe you will create something usefull :) If a particular data structure is not working in some case just use another.

    • cool rowdy
      cool rowdy 7 hours ago

      Hi @Mister Smith.can we not use a static variable inside the class of the linked list to store the last address..???????

  • Aqib Mulla
    Aqib Mulla Year ago

    Hello bro plz remove that text when u speak it's not visible to us to note it down .
    Thanks

    • Tirth Patel
      Tirth Patel 7 months ago

      It's captions, u can turn it off from options.

  • Arghyadip chakraborty

    Sir please remove subtitles ..with the subtleties it's more difficult to read what you are writing at the time of teaching.

  • Sanket Ray
    Sanket Ray Year ago

    I have question....I dont really understand what he says regarding Arrays. He says that Arrays have a fixed length and we need to specify them in the beginning? I use Swift to code. We don't specify number of elements while initializing. Array can be initially empty and you can perform any logic you want. Am I missing something? Someone please clarify :(

    • Sanket Ray
      Sanket Ray Year ago

      oh...thanks for answering

    • ANKUR SATYA
      ANKUR SATYA Year ago

      The arrays referred to in the above video is the data type as used in C++. Different languages may have different data types. The data type you are referring to in Swift is also present in C++ but under the name "Vector".

  • Shivraj Sharma
    Shivraj Sharma Year ago

    4:10 ....why the time complexity in avg case is given as n instead of n/2

    • Peterolen
      Peterolen Year ago

      Constant factors are ignored so O(n/2) = O(n)

    • John
      John Year ago

      Worst case scenario. Also, 1/2 becomes insignificant. I think

  • Dhruv garg
    Dhruv garg Year ago

    awesome!! really well explained, but what about dynamic array or vector in c++

  • Larissa Ford
    Larissa Ford 2 years ago

    I thought arrays had O(n) and not O(1)? because isn't big-O concerned with worst case scenarios where we may have to iterate through the entire array before finding our element, and would thus need n-time for an array of size n? I thought this because I understood hash tables to be special because they had a faster run-time than arrays, having a general case of O(1) run-time. Am I mistaken somewhere in there? Thanks for the amazing lecture!

    • Larissa Ford
      Larissa Ford 2 years ago +4

      oh wait, it would be constant time if we knew ahead of time where in the array (which index) an element is found. I think my question is still valid in terms of finding an element, but is that not what big-O is concerned with? is big-O concerned only with look up for a particular known element?
      *EDIT* gosh, I missed the part that said "Cost of accessing an element". this all makes sense now.

  • Suman Chakrabarti
    Suman Chakrabarti 2 years ago

    This is honestly better than watching the MIT presentations. Thank you!

  • Jay
    Jay 2 years ago +11

    Inserting node at end of linked list would be constant time if we have tail pointer!

    • Dillon Cote
      Dillon Cote 9 months ago

      @Nuril Ahmed Tail pointers are optional and can be made the same way as a head pointer. He just didnt use it in the video.

    • Nuril Ahmed
      Nuril Ahmed 10 months ago

      But why is there no tail pointer?

  • Jonathan H
    Jonathan H 2 years ago

    thanks!

  • Jaider Ariza
    Jaider Ariza 2 years ago

    The cost of inserting an element at the end 10:24 could be a constant O(1) if you use doubly linked list :)

  • Vishwjaeet Singh
    Vishwjaeet Singh 2 years ago +3

    mycodeschool you're the best

  • Venkataraghavan Yanamandram

    Thank you for the great explanation!! I'd a doubt on linked list, when we insert a data at the end of linked list or in between linked list the time consumption is proportional to O(n). I thought however we're going to add it and just have to change the address of last one O(1). but we've to iterate from the first to find the tail node address so it comes to O(n) am I right?