Data Structures: Linked List implementation of stacks
ฝัง
- เผยแพร่เมื่อ 11 ต.ค. 2024
- See complete series on data structures here:
• Data structures
In this lesson, we have discussed linked list based implementation of stack data structure.
For practice problems and more, visit: www.mycodeschoo...
Like us on Facebook: / mycodeschool
Follow us on twitter: / mycodeschool
7 year's ago he explained ,but still the best explanation
this channel is evergreen
true
10 yrs ago
I'm Taiwanese and thank you for making this video!!
Your videos not only CLEAR but HAVE SUBTITLES!
It's very helpful for those native language are not English.
taiwan belongs to china so u r chinese
@@zackdon264 No Taiwan is Independent from China . Do not hurt their soverignity .
@@mehularora3234 u r a idiot
@@zackdon264 but he is not xi ping ping
@@zackdon264 U look more like one
Thanks Micheal !! We are working hard to get all the videos for you. :)
A man telling the definition of linked list and explaining it in detail even he taught in his previous lectures......Superb Bro!!!
western education is haram....stop coding, spread islam
@@maitahom9958show me the proof of your word and tell me does your religion taught you to behave like this?
no hes just ignorant@@muhammadfurqanalam
After wasting 2 weeks I finally found a data structures playlist which I needed, LinkedIn Learning, Pluralsight everything failed but TH-cam saved me. Thank you!
Finally here....After watching countless YT channels and visiting countless websites .... Finally this is the best explanation that I have ever found...❤️
this course is 9 years old still the best explanation topic wise and time saving as well as easy to understand.
Hi Bro, you make the stack of Linked List very clear and straightforward, like it very much, and I enjoy your accent a lot! Keep up to it!
Thank you so much for your tutorials, they are so clear and visual which helps me understand the concepts!
i just saw your stack implementation with Arrays, made my day!
You can also reuse IsEmpty() function inside the Pop() function, so instead of:
if (top == NULL)
you could write
if (IsEmpty())
nice solution
In point of reusability and maintainable its good to have IsEmty call, but will degrade performance of code since it’s additional function call. Correct me if needed.
Depends on the language and compiler, a function that simple/short is likely to be inline. If not, you're correct, we'll have the cost of the stack frame allocation, etc.
10 years ago, Really better explanation than 2 hour lecture
Such clarity! This is the answer to our midterms in Data Struct last time. How I wished I watched this video earlier. TT ~TT
He explained 10years ago still no one can beat him
the best explanation of topics in youtube🙌🙌
Much more clear than my professor (and eng is not my first language)
you sir, teach very well and know your job
i hope u will make this type of video again n again.
Obviously
Really helpful and well made video. Also, cool accent, reminds me of my Finnish friend :)
UrbanTarzan Duh It's an Indian accent btw..
wonderful explanation, btw on 07:36 you got to correct sizeof to be just sizeof(struct Node)) , please note it may get compiled but you won't be able to loop and print values, i just figured it when i ran into the problem
Here is my complete code with a switch function to use it properly :)
Btw, thank you so much mycodeschool !
#include
#include
struct Node {
int data;
struct Node* link;
};
struct Node* top = NULL;
void Push(int x) {
struct Node* temp = (struct Node*)malloc(sizeof( struct Node*));
temp->data = x;
temp->link = top;
top = temp;
}
void Pop(){
struct Node *temp;
if(top == NULL) return;
temp = top;
top = top->link;
free(temp);
}
int isEmpty(){
if(top == NULL)
return 1;
else
return 0;
}
int Top(){
return top->data;
}
int Print(){
struct Node* temp = top;
if(isEmpty == 1){
printf("Stack is Empty");
return;
}
printf("Top| ");
while(temp != NULL){
printf("%d > ",temp->data);
temp = temp->link;
}
printf("|End");
}
int main()
{
int choice,enter;
printf("--------- Welcome to Stach ---------
");
while(choice =! 0){
printf("
Please ENTER your choice
");
printf("1. Push
");
printf("2. Pop
");
printf("3. What is Top ?
");
printf("4. Is Stack Empty ?
");
printf("5. Print Stack
");
printf("Choice: ");
scanf("%d",&choice);
printf("
");
switch(choice){
case 1: printf("Enter the number for Push
");
scanf("%d",&enter);
Push(enter);
break;
case 2: Pop(enter);
printf("It's popped!
");
break;
case 3: enter = Top();
printf("Top is = %d
",enter);
break;
case 4: enter = isEmpty();
if(enter == 1)
printf("Yes, It's empty
");
else
printf("Nope, It contains elements
");
break;
case 5: printf("Stack Elements:
");
Print();
break;
default : printf("Enter numbers between 1 and 5 !");
break;
}
}
system("PAUSE");
return 0;
}
+Mangoser thanks man!
This explanation is very clear .Thank you
Good job explaining the relevance of big O in the stack implementation on the linked list.
to set the first node instead of the last one as top is totally brilliant
very clear and straight to the point. Thank you!
great explanation, quick and simple
Sir, how can you be so good.
If you make a doubly-linked-list, the cost of inserting an element at the end would be also O(1), since you could just call the global tail variable.
i.e.: head -> n1 n2 n3.... nn
D. Refaeli we can also use singlly link list and the cost of operation will be o(1) only by creating two new pointer variables which will point to last two nodes..
Although this will require space for two more pointer variables but this will be more efficient then your solution...
Nice tutorial.
why do use malloc(sizeof(struct node*))? i thought (struct node*) is a pointer of value 4 byte but our structure (struct node) is ( 4 + 4 ) = 8 bytes . isn't it the allocation is short?
is it enough memory allocated by doing so? thanks
It's gotta be malloc(struct Node) without the star. On one of the previous videos while I was testing doubly linked list, my code was failing due to this. I scratched my head for over an hour and found I was malloc'ing size of pointer (i.e. address) rather than the Node itself. This is a classic example where debugging won't give you what you are doing wrong since it's a logical mistake. :)
From this video I conclude that if I want speed and less space I should better stick with array stacks
thankyou so much man for making this video. It cleared all my doubts
Thanks alot! Tried so long to understand this, i finally did today😄
awesome explanation
Shouldn't the dynamic memory allocation statement be
struct Node *temp=(struct Node*)malloc(sizeof(struct Node)) ? While using the sizeof operator here our intention is to get the size of "Node" and not the "pointer to Node".
yes
Naval saini Hey mister,I was right in pointing out the error.You,however,are just an ignorant guy who likes pulling people down.And just so you know,I got job offers from two IT firms a few weeks ago as a full-time programmer.Cheers :D
Naval saini Good sense of grammar dude :p Infosys and Cognizant.I am sure they'll be happy to see that I make an effort to learn new things and point out errors in order to help other people :)
:)
I was about to correct you for not putting the asterisks, but then realized that you used them and youtube used them to make part of the comment bold.
Thank you so much sir.........this vedio helps me alot.............
U saved my sem sir! Thanks :-)
thank you for making this. you teach really well.
Implementation in C++
#include
using namespace std;
class Stack
{
private:
struct Node
{
int data;
Node* link;
};
struct Node* top;
public:
Stack()
{
top=NULL;
}
void Push(int x)
{
Node* NewNode = new Node();
NewNode->data = x;
NewNode ->link = top;
top = NewNode;
}
void Pop()
{
Node* temp= top;
if (top==NULL)
return;
top=top->link;
delete (temp);
}
void Print()
{
Node* temp = top;
while(temp!=NULL)
{
cout
you prefer writing the class definition inside the class or outside the class.....in our school it is preferred to write the function definition using scope resolution operator
kya baaattt
if we are also storing address of tail as we are doing with head then we can do insertion/deletion at end too in o(1)
Exactly! the malloc shud be allocating sizeof(struct node) right? o_O
Yes, I also think so.
you are right
god BLESSS
Very helpful video. Thank you very much
Indian can tell you are also one of them
keep the great work up brrro
Really nice videos. very helpful
Your code will work, but it will cause memory leak.. you are just moving your top pointer to next node. The previous head node is still occupying space in memory. because it is dynamic memory which is not freed automatically. In pointers series, check the lesson on dynamic memory allocation and memory leak to understand this concept.
You teach well.thumbs up.
i love your explanations :')
nice video sir thank u so much for the clear explanation
really great work. thanks a lot
Thanks, sir. Very useful.
very good explanantion.
Hello sir why r not uploading the vedios on the channel? u r teaching style is awesome.where r u?
Great video thank you sir !
good explanation
good explanation..
You are truly amazing! Thanks so much :)
We miss you sir
explanation, btw on 09:58 you got to correct top=250 and not 100, otherwise in temp the 100 value will get copied and not 250
Puja Bhattacharya top=250,got delete by calling free function.
I'm VietNamese,Thank you so much :)
Thank you so much
Thanks a lot!
be hepfull please make some vedios on competitive coding
kya hum data structures ke exam mai stack explain krte tym uske saath programs lihk sakte h ya sirf algorithm hi lihkne h.
it's really very helpful & i nice try. thank u so much.:-)
how you look back to this point ?
why did you declare the variable temp using the size of the pointer instead of the size of struct nodes itself ???
how would this look if you used string instead of int
Nicely done. :)
How would I implement a stack using a LinkedList object? Would I need to create an instance of the LinkedList class in my stack.h and call the constructor for the LinkedList object in the stack's constructor (if there is only a default constructor for LinkedList)?
2 corrections (I guess)-
1 malloc(sizeof(struct Node)) instead of malloc(sizeof(struct Node*)) PUSH function
2 top = temp -> link instead of top = top -> link POP function
basically top and temp both are pointing to the same address field i.e. 250 in the video. So, top = top->link is same as top = temp->link in that particular scenario. And for that number 1 point, yes you are correct. It was a typo.
Cant thank you enough sir :)
Come back please 🙏
I don't understand about constant time or O(n) , O(1),.... Can you explain for me?
*rest in peace sir :(*
which compiler are you using?
When popping from the stack why do you need to declare a temp variable. Can't you just set top = top->link; instead of top = temp->link; ? I know that is what you showed in your video but I feel like it's a mistake because you declared temp, but what's the point of declaring a temp just to free it. I feel like it's redundant.
you can`t mario as if you use top=top->link then the value to which top was pointing earlier will be lost so it can`t be freed after that. so first a temp variable must be declared so that after top=top->link the memory can be freed by using free(temp) as temp will still be pointing at the value to be popped
Is
struct Node* temp=(struct Node*)malloc(sizeof(struct Node));
the same as
struct Node* temp=(struct Node*)malloc(sizeof(struct Node*));
... the code works same for both ways
@Peterolen yes thankyou!
arre mere college mei aaja padane
he can't visit your college dear, this person was died in a road accident in 2015 :'(
Khawar Mehmood Are you serious? oh my god how do you know?
Bro you said he died in 2015 last video he uploaded was oct 24, 2016. I did a little bit research and found out the person who died was humblefool(harsha), india greatest red coder, He was friend of mycodeschool(this guy name is animesh) and also a co-founder of mycodeschool. Bro half knowledge is dangerous!! Please just don't shoot arrows in the dark!!
@@VS-ey2lf yes Harsha was his senior in IIIT Allahabad
@Atharva Wankhede I think he was just making a joke.
at 9:53 when we free temp,we are just freeing only the reference to the node but not node temp is pointed to? and isn't this way memory of machine wasted
Hello, I need help.
How do I expand the stack capacity?
Eg every time the stack has overflow expand another 8 capacity positions.
Excuse me for bad english.
What if we write instead:
top= temp->link
temp=top
free(temp)
?
10:56 Thanks for teaching..
so stack in linkedlist doesn't follow LIFO rule.
جامد ⚡
thanks
Do we need to set a temp = NULL; after free(temp); ?
Sir why did you stopped making videos????
Does adress 0 in memory point to NULL* memory location??
In pop function, in line 4 shouldnt it be
Top= temp->link
rather than
Top=top->link ??
Both are correct...Both top and temp are pointing to 1st node
Is there any good reason why we do explicit type casting here.
[i.e: struct Node* temp = (struct Node*)malloc(sizeof(struct Node*));]
My code works without the type cast.
[ i.e: struct Node* temp = malloc(sizeof(struct Node*); ]
Sairam D malloc returns void pointers generally
here is the implementation on c plus plus via OOPs!!
#include
using namespace std;
class node
{
public:
int data;
node* next;
};
node* top = NULL;
class linkedList
{
private:
public:
void push(int x)
{
node* newNode = new node();
newNode->data = x;
newNode->next = top;
top = newNode;
}
void pop()
{
if (top == NULL)
{
return;
}
else
{
node* temp;
temp = top;
top = temp->next;
delete temp;
}
}
void print()
{
node* temp = top;
if (top == NULL)
{
return;
}
else
{
while (temp != NULL)
{
cout data next;
}
}
}
int topData()
{
if (top == NULL)
{
return -1;
}
else
{
return top->data;
}
}
};
int main()
{
linkedList ll1;
ll1.push(10);
ll1.push(10);
ll1.push(10);
ll1.print();
ll1.pop();
cout
thank you veeeeeeeeeeeeeeery much
But what is the use of temp in pop function?
have you code for this concept in c ?
Instead of top=top->link
It should be top=temp->link.
SARVESH KAUSHIK you r right it can be like that .. but if u look at it carefully,both temp and top are pointing to same node.he declared temp and initialized to top only to store its address so he can free the memory after.dats what he had done after.
+Rishabh Shirke both are pointing to the same address.
+Satyendra Jaiswal Same address of what?.....The node. :)
int a;
int *p=&a
p stores the address of the variable a;
i.e pointer p is pointing to a;
Satyendra Jaiswal thank you so much
how do you implement the print function?
I see that pop implementation of stack using linkedlist is not right. As you should add or remove elements from the top. The implementation illustrated in this video is removing the element which is not on top.
But for now, you need to modify the code to be something like this
struct node* temp= head;
while(temp->next_node != top)
{
new_top = temp; // you will use it to get the element right before the one you want to remove
temp = temp-> next_node; // you will update the temp to be looking for the next element, and then enter the loop again to check if it's the top or not
}
free(temp);
NOICE SIR...
But this is not following the property of stack.. The lifo property
thx
how to use stack using circular linked list ?
Implementation in C++ :
#include
using namespace std;
// Creating a NODE Structure
struct node
{
int data;
struct node *next;
};
// Creating a class STACK
class stack
{
struct node *top;
public:
stack() // constructure
{
top=NULL;
}
void push(); // to insert an element
void pop(); // to delete an element
void show(); // to show the stack
};
// PUSH Operation
void stack::push()
{
int value;
struct node *ptr;
coutnext=NULL;
if(top!=NULL)
ptr->next=top;
top=ptr;
cout
C++ (Object Oriented implementation)
class Node {
public:
int data;
Node* next;
};
class Stack {
public:
Stack(int N)
{
this->head = NULL;
size = N;
}
Stack()
{
this->head = NULL;
}
Node* head;
int size;
void pop()
{
if (!isEmpty())
{
Node* temp = head;
head = head->next;
delete(temp);
size++;
}
else
{
cout data;
else
{
cout data = data;
temp->next = head;
head = temp;
size--;
cout