Introduction to Linked Lists (Data Structures & Algorithms #5)
ฝัง
- เผยแพร่เมื่อ 11 เม.ย. 2018
- Learn the basics of linked lists. Java & Python sample code below.
Check out Brilliant.org (brilliant.org/CSDojo/), a website for learning math and computer science concepts through solving problems. First 200 subscribers will get 20% off through the link above.
Special thanks to Brilliant for sponsoring this video.
Find sample code in Python and Java here: www.csdojo.io/linked
This was #5 of my data structures & algorithms series. You can find the entire series in a playlist here: goo.gl/wy3CWF
Also, keep in touch on Facebook: / entercsdojo
Hey everyone! If you are looking for more practice problems for arrays and linked lists, I’d also recommend my Udemy course, “11 Essential Coding Interview Questions” here: goo.gl/v35LCa
It’s supposed to be for programming interview questions, but it should be a good resource for improving your problem-solving skills in general.
Anyway, thanks as always for watching! If you don’t want to pay for the course, remember that I have a ton of other free videos right here on this TH-cam channel :)
make a video on hash tables and hashing please
Thank you very much for another good quality lesson!
Please consider making a complete computer science course!
Even on Udemy, very interested to buy it!
CS Dojo hey there! I like your videos and would like to ask you something, so here goes:
"How do you learn something new, so that you don't forget it sometime soon?"
Because I often find myself forgetting stuff that I have just learned a few days or weeks ago. For example I learn about lists, maps and dictionaries. Then a few days later I want to realize a Programm and start cracking my head what I should use and how it worked. Then I have to Google again and look it up. I have this kind of problem for many things except the absolute basics.
How did you Crack everything in your head so you don't forget it again?
i had the exact same solution like you and now i'm happy :)
Thanks bro. You are providing us a very great and simple knowledge about programming. Keep going.
When a TH-cam video teaches you better than your programming professor at University lol
Exactly!
it always to be like that
@Xiogenes You're paying money for the syllabus....lol
Cant agree more. My professor explains it so terribly that my brain went spaghetti ...
@@ysheepy4907 tasty lol
I've been a developer for 25 yrs and i got 2 weeks to prepare for a Google technical interview and I'm relying on your videos to help me prepare. I have to relearn alot of stuff I haven't used in years. You have to go into teaching. America's kids need somebody that can teach as well as you. Thanks kid.
did you get the job?
Don't leave us hanging Armando. It's been two years.
Armando now works for the Government of Texas ;)
@@snoudoubts1745 how u know?
@@DanNjeru1 hahahaahahah dead
You're an incredible teacher. Hope these videos never end and stretch across even the most advanced of topics. Very enjoyable.
You have the best explanation of all the TH-cam tutorials out there! Keep up with the good work. I had so much trouble understanding and learning Linked List. If I would have had watched your videos earlier, it would have had definitely made my struggle period shorter. Thank you very much and keep up with the good work. :D
You're doing a great job CS. I have already recommended your channel to a dozen friends.
Keep up the good work!
Really proud of myself for doing this without looking at any hints. I don't get a lot of exercise questions. I love your method of teaching
My Java Code:
public class LinkedList {
public static void main(String[] args) {
Node head = new Node(6);
Node nodeB = new Node(5);
Node nodeC = new Node(5);
Node nodeD = new Node(5);
Node nodeE = new Node(5);
head.next = nodeB;
nodeB.next = nodeC;
nodeC.next = nodeD;
nodeD.next = nodeE;
System.out.println(countNodes(head));
}
static int countNodes(Node head){
int count = 1;
Node current = head;
while(current.next != null){
count++;
current = current.next;
}
return count;
}
}
it doesn't run tho
@@user-bn9ee1jg4i his code is fine
12:04 a three-line solution from python
def countNodes(head, count = 1):
if head.next != None: return countNodes(head.next, count + 1)
return count
a great solution but butting the "if" expression in the same line with the statement doesn't actually reduce a line.
@@zydiz its not if, its ternary operator with combination of recursion(but yeh logic is same)
My solution, writing before watching the solution:
int countNodes(Node head){
var count = 1; //As head is not null
while(head.next.data != null){
count++;
head = head.next;
}
return count;
}
I was struggling with this for ages! Thank you a lot
best video i ever see about linked list, my teacher explained TWO weeks and THIS MAN EXPLAINS IT IN 18 MINUTES, AND IM STUDYING C++!!!
Best and simplest teaching ever...thanks.
Bless Up.
I wish I learned programming at high school, all I did was play video games...
@@heavysaber9431 I feel lucky now
@@aryanshmahato I envy you brother, dedicate that time to programming!
divide by 2 each time and pick higher / lower half. its ez
You're the Khanacademy of programming! Love this series and your step-by-step explanations.
Excellent videos, thank you for this great tutorial.
My solution in Java is to add the following function to the Node class:
int countNodes() {
if (this.next == null)
return 1;
else
return this.next.countNodes()+1;
}
This will recursively search for child nodes and return the count.
I like the fact that he uses visual examples and actual code to explain the concepts. Most of the time books only have visual examples, and I would understand them, but once it came down to coding it I would just blank out.
This is the best explanation of a Linked List BY FAR. Great job!
You're just amazing, what I like the most is, you just go straight to the point with very clear examples and NO MUMBO JUMBO...!!!
An old timer Cobol programmer from last century... *lol*
In JavaScript
function countNode(node) {
let totalNodes = 1;
let myNode = node;
while(myNode.next) {
total++;
myNode = myNode.next;
}
return totalNodes;
}
inside while loop it will be totalNodes++ . Rest everything is absolutely correct.
Excellent videos! easy to follow and very well organized, awesome job CS Dojo!
watched your video twice. This time finally get the "head" idea. Thank you !!! You simplify everything yet does not lose the key point!!!! Great Work!!!!
I love this dude!!! He explains this sooo damn well
Thanks a lot man! You have explained it precisely for a beginner to understand. I would request you to post video for doubly and circular Linked list too.
the best thing about these videos are how simple they are to understand... by far the best tutorials on youtube
this is the best tutorial for linked lists! this is exactly how it was explained in my data structures course but simpler!
*Think of arrays as one box with many partitions, whereas a linked list is many boxes tethered together.
*Head = first node,
*Linked lists can be represented in one direction (singly LL) or both (doubly LL)
Great video, thanks for the clear explanation!
only think i consider is your blasphemous image.
try to be educated and ethical as a computer science student.
Christ the king image has changed and it's so blasphemous.....
@@finncollins5696 Dude, I'm a born-again Baptist Christian. I'm not mocking Jesus, it's just a meme.
I have been trying to learn LinkedList from yesterday, watched many tutorials, read many blogs but I was not getting the clarity as even the code of LinkedList is very intimidating. this video helped a lot!! I am finally a bit confident and ready to learn more about it and solve problems. Thank You Dojo!🙌
I've never been so clear as coming to listen to your explanation.
Thank you!
I'm taking an online course for school on data structures and it's very hard to learn complex topics without audio (yes my professor just posts reads and doesn't record herself explaining it). This really helped me out
I love your teaching! I learned a lot!
I really liked all of your visuals. They all really helped me. Especially having drawn out images next to the code. I really like how you explain everything as well.
By far one of the best tutorials I have seen, thank you so much ❤️
He definitely made it clear. I've been watching several videos to understand Linked list and this fella helped me understand it. Thanks
YK your amazing I love that you quit your high paying job at google to teach on TH-cam I hope your channel blows up and you become famous!
looks like your wish became true. he has more than a million followers in 2020 =)
@@UnrecycleRubdish yeah lol
Hey CS Dojo, I absolutely loved how you gave us a practice question.
I felt really good after solving it !
My Solution in python:
class Node:
def __init__(self, data):
self.data = data
self.next = None
def countNodes(self):
while(self.next != None):
print(self.data)
class LinkedList:
def __init__(self):
self.Head = None
def push(self, data):
new_node = Node(data)
new_node.next = self.Head
self.Head = new_node
def countNodes(self):
temp = self.Head
count = 0
while(temp):
count += 1
temp = temp.next
return count
linked_list = LinkedList()
linked_list.push(1)
linked_list.push(2)
linked_list.push(3)
linked_list.push(4)
print(f"The LinkedLists has {linked_list.countNodes()} Nodes.")
AaaAAAAaaaAAAAAAAAAaAAaaaaaAAAAAAAAAAAAAAAaaaaaAaAaAAAAAAaaaaaaaaaaaa
Aaa
Aaaa
Aaa
Aa
This helped me understand linked lists really well. Thank you.
Love to see more tree search problems!
Nicely explained, can you please show this class, linkedlist in memory as you did for video of array inside memory...
That was fun to know what's inside..
My code for java:
static int countNodes(Node head){
int i = 1;
while (head.next != null){
i++;
head = head.next;
}
return i;
}
Node-object is defined as in the video.
For the sake of understandability, it could make sense to add a 'cursor' variable like:
Node cursor = head
before the while-loop, since it is not really the head you are using for the rest.
*Like done in the video with current.
You can simplify the while statemet to:
while (head.next) {
...
It will loop while the statement in parentheses is True. Null is always False when using in conditional statements, thus as long as there's something in head.next, it will report it as True.
@@psionicxxx In Java that's gonna give you an error. Null doesn't evaluate to false and an object that isn't null doesn't evaluate to true.
Thank you! I am taking Algorithm and data structure in community college. I think spending 900 dollars on that course the professor can not do half of what you do. BRAVO!
Ayy..!! GentleMan.. Its amazing and mind blowing. Im impressed. Literally its highly valuable for me at this time. i need your videos on all the topics of data structure. im searching but i didnt find anything.. your way of conveying knowledge is awesome. BTW thanks for this one...!!!
swift 5.0 recursive function:
func countNodes(_ node: Node) -> Int { // recursive function
if node.next != nil {
return countNodes(node.next!) + 1
}
return 1
}
hi sir, u explained it very well!
just a small doubt- how does the doubly linked list prev node work?
how will it know that prev is the previous one?
Another good and clear descriptive video from CS Dojo!
Thank you very much for all these awesome videos with the best explanation I have seen so far!
int countNode(Node head){
int count = 1;
Node temp = head;
while(temp.next != NULL){
count++;
temp = temp.next;
}
return count;
}
So how do you solve that problem in the case with 1 Node
@@dungletien4676 if there is only 1 Node, temp.next will always be null, so while loop never executed,hence returned 1
def countNodes(head):
count = 0
node = head
while node.next != null:
count +=1
node = node.next
return count
Hello! I'm new to the coding scene, and am mostly self taught. I was working with Data Structures but most of my test cases would time out from being too long, and so I tried learning more about Linked Lists but I'm having some trouble with the syntax for Python. You obviously are familiar with it, could you please suggest some tutorials or material I could get a basic idea from?
I'd really appreciate it, Thanks!
wow! good job ,yk!
keep teaching us!
you're amazing!
Thanks a ton for putting this vid up!
Did it recursively:
int countNodes(Node head) {
if (head.next == null) { return 1;}
else {return 1 + countNodes(head.next);}
at the last node, when the head reaches its end, and there are no other nodes, your count will just return 1.
if you have a single line statement screw the skwigglies
if(head.next==null) return 1;
@@leelakrishna5815 ..plus 1 for every node before it. It checks out.
.
why would you do it recursively if you can do it using a while loop in a few lines?
Hey guys, I'm not sure if anyone has posted this before but if you wanted to solve this recursively you could use this:
static int countNodes(Node head)
{
if(head.next == null)
{
return 1;
}
else
{
return countNodes(head.next) + 1;
}
}
I'm very late, but this is extremely helpful. Thank you.
I really like your videos!! Thanks for the contribution man!
Hello YK,
This is my first self learned small program to find the numbers of nodes. Your teaching is really excellent.
I have written it in C# as following,
namespace ConsoleApp1
{
public class Node
{
int data;
public Node next;
public Node(int data)
{
this.data = data;
}
}
class Program
{
static void Main(string[] args)
{
Node head = new Node(4);
Node nodeA = new Node(2);
Node nodeB = new Node(3);
Node nodeC = new Node(10);
Node nodeD = new Node(2);
Node nodeE = new Node(23);
Node nodeF = new Node(123);
head.next = nodeA;
nodeA.next = nodeB;
nodeB.next = nodeC;
nodeC.next = nodeD;
nodeD.next = nodeE;
nodeE.next = nodeF;
System.Console.WriteLine($"Total numbers of nodes are : {CountNodes(head)}");
}
static int CountNodes(Node head)
{
int totalCount = 1; // consider count of head as 1
Node currentNode = head;
while (currentNode.next != null)
{
totalCount++;
currentNode = currentNode.next;
}
return totalCount;
}
}
}
Can you please next one do using LinkedList for Stack and Queue?
@B0bby that’s ok, I already graduated 😂
@@HungNguyen-oz1jc 🤣
My Java Code:
int countNodes(Node head) {
Node tmp = head;
int counter = 0;
while(tmp != null) {
counter++;
tmp = tmp.next;
}
return counter;
}
I was looking at this and I confused myself. I was trying to challenge myself and was thinking this code might be one count short because you werent accounting for the first head. You would either need to start counter at 1 or increment counter by one at the end. Very well done though, and easy to read!
Counter=1
Not 0
@@SureshKumar-kd3fx it works when counter is set to 0 because it stills loops through and increments it.
@@SureshKumar-kd3fx in the video the loop was based on current.next and not current, that is the difference between his and Murat's code.
@@SureshKumar-kd3fx @Chance Bechly Actually, it is correct. Look closely at the order of the code; counter++ happens Before the jump to the next item. So starting at head, you increment the counter from 0 to 1 (thus counting the head), then you go to head.next, check if it is null, if not, increment counter from 1 to 2, and so on till you hit a null.
If you started the counter at 1, in the case where there -is no list at all-, you would incorrectly count 1 node, when no nodes exist in the first place.
Best video I have seen in learning a concept. Thank you very much!
this was extremely helpful, thank you for making this so clear
*** C++ CODE ***
// there are many ways to do that
// You can make it by using Recursive way
// if you want to append strings or another arguments you can do it ~
// You can add any function except mine like remove etc
// ~ by using Templates
// I would recommend you boos *** C++ Early Objects
// Any questions, leave comment
// *** GOOD LUCK ***
#include
using namespace std;
class LinkedList // name of a class
{
protected: // our struct would be protected so we could manipulate data with Child Classes
struct Node{
double data; // value in the node
Node *next; // next pointer which points to the next node
// Constructor
Node (int data1, Node *next1 = NULL)
{
data = data1;
next = next1;
}
};
Node * head = NULL; // pointing the head front of the node(Make it to point first node)
public:
void add(double); // adding function when we add the new value to our node
int getSize(); // getting the size of a Node
void DisplayList(); // Displaying the list
};
// Adding function with argument double *** We can make it with template so we can ~
// ~ append any type of an argument
void LinkedList::add(double number) //
{
Node *ptr = head; // both ptr and head points to the first node of the Node list
if (head==NULL)
head = new Node(number); // when it is empty just append the number
else
{
while (ptr->next!=NULL) // Compile it if the first node not point to the NULL ***not next node
{
ptr = ptr->next; // go to the next node
}
ptr->next = new Node(number); // append the number instead of NULL
}
}
// Displaying the LIST
void LinkedList::DisplayList()
{
Node * ptr = head; // both of them begin from front Node list
if(!head) // if it is empty
return;
while (ptr!=NULL) // while it is not empty
{
coutnext!=NULL)
{
len++;
ptr= ptr->next;
}
return len+1; // since last node is NULL it would not add consider the last value ~
// ~ so we added it by ourselves
}
}
int main()
{
class LinkedList list;
list.add(1);
list.add(2);
list.add(3);
list.add(5);
list.add(12);
// you can add your own code
// code~~~
list.DisplayList();
cout
Thanks!
Nice
thank you, going to analysis the code in an IDE appreciate it
class Node:
def __init__(self, data, next=None):
self.data = data
self.next = next
Head = Node(5,Node(1,Node(2,Node(8))))
def count_Nodes(head):
count = 0
a = head
while True:
count += 1
if a.next == None:
return count
a = a.next
print(count_Nodes(Head))
I used a different Generator because this way it's much more compact
Short and sweet
Love the way you explain things, dude! Thanks for sharing knowledge!
This is the easiest and best information about linked lists I have come across so far! Well done 👍
def count_nodes(linked_list):
count_nodes = 0
while linked_list is not None:
count_nodes +=1
linked_list = linked_list.next
return (count_nodes)
Thx
exactly same solution. Now io dont feel stupid
public int getLength(ListNode head) {
int i = 1; // counter
while(head.next != null ){
i++;
head = head.next;
}
return i;
} // end method getLength
Thank you CS Dojo.
Best Linked List video i have seen. Thank you so much mate
my solution:
int countNodes(Node head){
int result = 1; //should always start with one because if you have a head then 1 node by default, NOT 0
Node currentNode = head;
while( currentNode.next != null){
result ++ (can also do += 1, style thing)
try{currentNode = currentNode.next}
catch (Exception e){break;}
}
return result;
}
try catch may not even be necessary, but can never be too careful lol, written in c# btw
python implementation :::
def countNodes(head):
if head.Next != None:
countNodes.count += 1
ConsecutiveNode = head.Next
countNodes(ConsecutiveNode)
return countNodes.count
class Node:
def __init__(self,data):
self.data = data
self.Next = None
head = Node(4)
nodeB = Node(2)
nodeC = Node(3)
nodeD = Node(10)
nodeE = Node(34)
countNodes.count = 1 # Assuming head is not null
head.Next = nodeB
nodeB.Next = nodeC
nodeC.Next = nodeD
nodeD.Next = nodeE
print(countNodes(head))
what should it really print?
Aditya Mandal no of nodes
It prints out 1
Aditya Mandal there might be problem with the indentation while copying and pasting
replace the if with a while
Wow, this is amazing! You're a great teacher. Thank you for making this video!
I actually deeply get it finally, thank you
Sir please make more videos on python.
I learned in 20 minutes what my teachers were trying to teach me for 2 hours...
my teacher trying to teach me this for last 2 years😂😂
@@suman-majhi nah fundamentals shouldnt go for 2 years your teacher brain damaged
Awesome video, glad that I found this. Thank You!
Well explained !! one of the best resources for learning linkedList
hey sir. a 12 year old boy is inspired by you
Keep it up!
Are you still coding? I wish I started as early as you. I was only interested in games (although I still love games) kudos to u kid
im 13 :D
Me too
16 here, keep it up man
This is cool and all. But what is the practical use of linked lists? Easier to understand the concept if we know what its used for.
dynamic allocation in memory, i guess. items of same collection can be stored in different locations of memory...
th-cam.com/video/_jQhALI4ujg/w-d-xo.html
One of the most widely used data types in computing is hash tables. If you would like to create one from scratch, linked lists are the easiest way to implement them. First learn how to implement a linked list from scratch and then learn how to use that to create a hash table.
Thank you so much. your explanation was very clear and excellent. this was the first video that I learned about a linked list. your video helped me to understand linked Lists very well. Keep up the good work.
dude you are really good at explaining this stuff. Don't teach so people can understand, teach so that nobody can misunderstand. You follow that perfectly. I don't think there is enough emphasis on good teachers, you just kind of have to get lucky.
But why should we use a linked list?
Depends on use case. Like when you need fast (constant time) insert/delete in a list but you are not looking for dynamic access to any element of that list.
Its the same like an array, but with the advantage of being able to not having to insert the amount of objects you want to enter in the List. But tbh its just way too much work so i'd always go with the array
If you do not know any better the least you can do is not spread misinformation.
It's NOT like an array. Instead a linked list is maintained using pointers to next node/element. And I'm not even sure what "being able to not having to insert the amount of objects you want to enter in the List" means.
saying that it’s LIKE an array doesn’t means it is an array dumbass.
And if you don’t understand my sentences bcs in your poor country the education system is fucked I’m not to blame..
Please think before writing some shit
Appreciate your intellectual responses. Real class.
"saying that it’s LIKE an array" is wrong by itself! And no, "being able to not having to insert the amount of objects you want to enter in the List" - does not make any sense in whichever language you try.
//Method returns count of Nodes
int countNodes(Node head){ //This method returns the number of Nodes
int count = 0;
while(head != null){
head.next;
count ++;
}
return count;
}
Thanks a lot Dojo! So clear explanations
among all i watched, this explains the idea of linked list briefly! amazingg
Really very helpful. Saw a lot of videos on LL but this code made concept very clear and the code was so simple.
Thanks.plz complete this whole DS series...
Best simple explanation about linked list thusfar on TH-cam.
Most simplest video to lear from. Thanks so much!
This is really great, I was looking for a video but did not understand until now
Thank you so much CS Dojo! May God bless you!
I hope you were my programming language teacher back in the college day, I didn't understand it until watching your explanation
Thank you YK for your clear explanation and samples :)
Thank you very much!
Goodquality as usual!
Outstanding explanation! Many thanks, sir!
Simplifying teaching of complex topic in Java , . The way explaining things what is happening inside the linked list side by side code details are simply great . One of the best teaching oh the topic. Thanks friend.
This is great, I'm really enjoying this.
Helping people 5 years later. Thank you!
You're great at breaking things down to an understandable level. The "friendly" naming of variables before changing them to best practices is helpful.
What is one real world example of a situation where you would want to use this? Quickly expanding data without a predictable end point?
You are a legend. Thank you so much.
A very good take on data structures. Interested to see where this goes.
This is the best video on data structure. Thanks a lot for beautiful explanation.
You simplified things for me and I was able to follow along knowing mostly JavaScript.
This is by far one of the best explanations I've ever seen about Linked Lists, especially for people like me that don't have a CS background.
Hi
Really man ur explaination was much better than all the site lecture I have gone through
Thanks was waiting for this :)