Linked Lists Introduction

[@Mydad-et1el]

At 13:00, I would like to point out that for Singly Linked List, insertion at tail only takes O(1) if we have a pointer to the tail. Otherwise, it is O(n) to insert at the end, since we need to traverse from head to tail to insert at the end.

[@zss123456789]

good point!

[@cyberknight9874]

I know this. But it's still a good point to mention here.

[@AkshatSinghania]

he said that "we have a refrence to the tail so we can remove it in constant time" in the video

[@JIHYELEE-h2m]

Note that Singly Linked List also can have Head and Tail Node, But only one pointer to next node. When remove at tail in Singly, We can remove last Node using Tail Node. But Tail Node doesn't know what is previous Node only know next is NULL. So we have to throw away Tail node after removing that.

[@BlueSky-ho6dy]

14:00 complexity

[@musthafajm]

Very nice sir.

[@danimanabat5791]

Thank you!

[@anupampandey3758]

if an n-1th element needs to be deleted in case of deletion from the middle in a doubly linked list, why can't we use the tail pointer and prevent the O(n) traversal? I think time complexity is O(n/2) since we must have to traverse in case the middle element in the list has to be deleted.

[@kroypatcha]

O(n/2) = O(n)

[@IvanRandomDude]

@@kroypatcha Yes but keep in mind that jdk actually does check if element is closer to head or tail. If you take a look at jdk you will see that they check if index of element you want to remove is closer to tail or head. If it's closer to tail they start traversal from tail and vice versa.

[@IvanRandomDude]

@@kroypatcha Here it is: hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/LinkedList.java On the line 566 in node function (used to locate node with specific index) you can see they check if index is smaller than size/2 or bigger than size/2. (Bit shifting by two is faster way of dividing by 2)

[@IvanRandomDude]

So yes, in algo analysis theory O(n/2) is the same as O(n). But in real world that doesn't mean we won't optimize the code to run twice as faster. If my program can run in 5 sec instead of 10 sec I'm doing it, I won't be like "muh 10/2 is the same as 10"

[@kroypatcha]

@@IvanRandomDude BigO notation is intended to find the scalability of the code (It can't always tell which is better algorithm). When two algorithms have same BigO then we chose the one with less time (such as n/2 or whatever). There is no notation for that part.

[@amirsaeed7759]

Well done!!!

[@sanskarsoni2912]

Do you have a video on floyd's cycle detection algorithm? If not will you please do one.

[@marlonstevenson4923]

I'm 1:27 into this vid and I've already seen 2 advertisements. Truly ruining my experience. edit: 5:27 and the 3rd ad. KZbin is commiting suicide. Got to get off this platform.

[@WilliamFiset-videos]

That's not okay, removing mid roll ads.