# Data Structures: Arrays vs Linked Lists

41
19

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:

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 .

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

def __init__(self, d):
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. amazing, i am preparing for googles kickstart.
btw im 15 and python programmer ,web developer.

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

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

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

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

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

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

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

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

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

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