Introduction to Linked Lists (Data Structures & Algorithms #5)
Vložit
- čas přidán 11. 04. 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 CZcams 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 CZcams 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 CZcams 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!
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)
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 was struggling with this for ages! Thank you a lot
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
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;
}
Excellent videos! easy to follow and very well organized, awesome job CS Dojo!
You're the Khanacademy of programming! Love this series and your step-by-step explanations.
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*
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.
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
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
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.
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.
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.
By far one of the best tutorials I have seen, thank you so much ❤️
this is the best tutorial for linked lists! this is exactly how it was explained in my data structures course but simpler!
I love this dude!!! He explains this sooo damn well
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!🙌
the best thing about these videos are how simple they are to understand... by far the best tutorials on youtube
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...!!!
I love your teaching! I learned a lot!
YK your amazing I love that you quit your high paying job at google to teach on CZcams 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
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've never been so clear as coming to listen to your explanation.
Thank you!
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..
*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.
Thank you very much for all these awesome videos with the best explanation I have seen so far!
He definitely made it clear. I've been watching several videos to understand Linked list and this fella helped me understand it. Thanks
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.
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?
this was extremely helpful, thank you for making this so clear
I really like your videos!! Thanks for the contribution man!
swift 5.0 recursive function:
func countNodes(_ node: Node) -> Int { // recursive function
if node.next != nil {
return countNodes(node.next!) + 1
}
return 1
}
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 is the easiest and best information about linked lists I have come across so far! Well done 👍
Wow, this is amazing! You're a great teacher. Thank you for making this video!
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.
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...
This helped me understand linked lists really well. Thank you.
Can you please next one do using LinkedList for Stack and Queue?
@B0bby that’s ok, I already graduated 😂
@@HungNguyen-oz1jc 🤣
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
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!
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;
}
}
}
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!
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!
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?
Sir please make more videos on python.
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.
wow! good job ,yk!
keep teaching us!
you're amazing!
Awesome video, glad that I found this. Thank You!
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
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
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.
public int getLength(ListNode head) {
int i = 1; // counter
while(head.next != null ){
i++;
head = head.next;
}
return i;
} // end method getLength
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
Thanks a lot Dojo! So clear explanations
Best video I have seen in learning a concept. Thank you very much!
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
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...
czcams.com/video/_jQhALI4ujg/video.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.
I hope you were my programming language teacher back in the college day, I didn't understand it until watching your explanation
Thanks was waiting for this :)
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
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.
Well explained !! one of the best resources for learning linkedList
Love to see more tree search problems!
*** 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
//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;
}
among all i watched, this explains the idea of linked list briefly! amazingg
Thanks a ton for putting this vid up!
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 excellent you really helped me
To understand.
Thank you very much!
Goodquality as usual!
A very good take on data structures. Interested to see where this goes.
Another good and clear descriptive video from CS Dojo!
Thank you YK for your clear explanation and samples :)
Wow Thank you so much for making the linked list easy to understand. :) You're awesome!
This is great, I'm really enjoying this.
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
Sir ur osm.....
Ur teaching insired me to learn computer science.
Thx for making videos.
Ur videos are liked by each and every computer lovers.
AND FINISH DATA STRUCTURES AND ALGORITHMS SERIES AS SOON AS POSSIBLE SIR..
ITS A HUMBLE REQUEST...
Outstanding explanation! Many thanks, sir!
You are a legend. Thank you so much.
Really helpful and simply explained, thank yoU!
Nice video. I hope to see one explaining what linked lists are used for in the real world so I can conceptualize it better.
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!
Very clear and useful tutorial! Speaking in language everyone can understand..
You simplified things for me and I was able to follow along knowing mostly JavaScript.
Thanks lot, u make everything simple
this was really helpful, thanks!