Data Structures: Arrays vs Linked Lists

41
5



See complete series on data structures here:

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:

Nguồn:https://wijstaanvooronzegrondrechten.org/

41 COMMENTS

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

LEAVE A REPLY

Please enter your comment!
Please enter your name here