The same thing as well for the short on Structures. There's the video on Data Structures that refers to the one on Structures but I couldn't find it on edX, I had to come here on TH-cam to find it.
god that was hard. all was +- smooth until Doug mentioned we need to include head and tail cases to remove a node. i rearranged the entire file, added head and tail as global variables and updated their values in functions and main
How can you say that a search takes linear time? Not if you are searching for an item in the list with a binary search strategy. It consumes practically zero time, regardless of the length of the list.
You don't have random access here like in an array (that needs to be sorted for that strategy to work), nor is this a binary search tree, so you'll have to traverse each node in the worst case, henceforth = O(n) linear time.
@ Heinrich you are wrong. Binary Search works well with SORTED lists of items with RANDOM ACCESS. You need to be able to split the list in the middle and either check the left or right half depending on the target you are searching for. You cannot do that with these doubly linked lists, i.e. they do NOT have random access.
@@silberlinie Even if your linked list is sorted, yet you cant do binary search, because you just have only the head of the list, you dont know how many elements in the list, you dont know where is the middle etc. İt is like being blind in the dark and just knowing the friend whose hand you are holding.
They keep referring to insertion sort but it was never discussed in week 4 or 5 in 2021 or 2022 classes
yeah, but there is a video of that. you can search on youtube insertion sort cs50 shorts
Wonder why this is not in the videos for cs50 2018 on edx?
Yeah, especially since he refers to this concept in the short on "Queues"
Same thing here)
The same thing as well for the short on Structures. There's the video on Data Structures that refers to the one on Structures but I couldn't find it on edX, I had to come here on TH-cam to find it.
yeah from 2021 and it still not under the cs50 videos but he mentions this video
@Kyson Talon no one cares
How is Doug so deceptively charismatic?
It's his wry smile
tmp->prev->next = tmp->next;
tmp->next->prev = tmp->prev;
god that was hard. all was +- smooth until Doug mentioned we need to include head and tail cases to remove a node. i rearranged the entire file, added head and tail as global variables and updated their values in functions and main
Wonder why this is not in week five shorts in 2021 or 2022 lesson
it's really hard to understand, thankfully for your explaination^^
How can you say that a search takes linear time?
Not if you are searching for an item in the list with a binary search strategy.
It consumes practically zero time, regardless of the length of the list.
@heinrich You want to use BST for that.
You don't have random access here like in an array (that needs to be sorted for that strategy to work), nor is this a binary search tree, so you'll have to traverse each node in the worst case, henceforth = O(n) linear time.
@ Heinrich you are wrong. Binary Search works well with SORTED lists of items with RANDOM ACCESS. You need to be able to split the list in the middle and either check the left or right half depending on the target you are searching for. You cannot do that with these doubly linked lists, i.e. they do NOT have random access.
@@dm6031 You're right. It must be an sorted list.
@@silberlinie Even if your linked list is sorted, yet you cant do binary search, because you just have only the head of the list, you dont know how many elements in the list, you dont know where is the middle etc. İt is like being blind in the dark and just knowing the friend whose hand you are holding.