Data Structures: Linked List implementation of stacks
HTML-код
- Опубликовано: 9 окт 2013
- 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.mycodeschool.com
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
Thanks Micheal !! We are working hard to get all the videos for you. :)
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
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 RUclips 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...❤️
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!
this course is 9 years old still the best explanation topic wise and time saving as well as easy to understand.
i just saw your stack implementation with Arrays, made my day!
very clear and straight to the point. Thank you!
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
Good job explaining the relevance of big O in the stack implementation on the linked list.
Such clarity! This is the answer to our midterms in Data Struct last time. How I wished I watched this video earlier. TT ~TT
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.
He explained 10years ago still no one can beat him
Much more clear than my professor (and eng is not my first language)
you sir, teach very well and know your job
thank you for making this. you teach really well.
Really helpful and well made video. Also, cool accent, reminds me of my Finnish friend :)
UrbanTarzan Duh It's an Indian accent btw..
Thanks alot! Tried so long to understand this, i finally did today😄
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!
the best explanation of topics in youtube🙌🙌
great explanation, quick and simple
awesome explanation
You are truly amazing! Thanks so much :)
thankyou so much man for making this video. It cleared all my doubts
This explanation is very clear .Thank you
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)
U saved my sem sir! Thanks :-)
Thank you so much sir.........this vedio helps me alot.............
Thanks, sir. Very useful.
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. :)
You teach well.thumbs up.
Really nice videos. very helpful
nice video sir thank u so much for the clear explanation
really great work. thanks a lot
very good explanantion.
i hope u will make this type of video again n again.
Obviously
Very helpful video. Thank you very much
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...
to set the first node instead of the last one as top is totally brilliant
Sir, how can you be so good.
good explanation..
i love your explanations :')
Great video thank you sir !
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.
From this video I conclude that if I want speed and less space I should better stick with array stacks
Indian can tell you are also one of them
keep the great work up brrro
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
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)?
Hello sir why r not uploading the vedios on the channel? u r teaching style is awesome.where r u?
it's really very helpful & i nice try. thank u so much.:-)
how you look back to this point ?
Thank you so much
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.
Exactly! the malloc shud be allocating sizeof(struct node) right? o_O
Yes, I also think so.
you are right
god BLESSS
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.
why did you declare the variable temp using the size of the pointer instead of the size of struct nodes itself ???
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
good explanation
I don't understand about constant time or O(n) , O(1),.... Can you explain for me?
What if we write instead:
top= temp->link
temp=top
free(temp)
?
Do we need to set a temp = NULL; after free(temp); ?
Nicely done. :)
Thanks a lot!
I'm VietNamese,Thank you so much :)
thanks
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
which compiler are you using?
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.
how would this look if you used string instead of int
We miss you sir
10:56 Thanks for teaching..
Does adress 0 in memory point to NULL* memory location??
Come back please 🙏
be hepfull please make some vedios on competitive coding
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
Cant thank you enough sir :)
But what is the use of temp in pop function?
*rest in peace sir :(*
how do you implement the print function?
kya hum data structures ke exam mai stack explain krte tym uske saath programs lihk sakte h ya sirf algorithm hi lihkne h.
have you code for this concept in c ?
thx
جامد ⚡
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
how to use stack using circular linked list ?
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.
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
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
NOICE SIR...
why at push 09:28 you malloced memory and at pus you just created a new node
thank you veeeeeeeeeeeeeeery much
so stack in linkedlist doesn't follow LIFO rule.
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!
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
thank you
Sir why did you stopped making videos????
07:14
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.
Waiting for DS and Algo in Java/Python..
He is no more . He died in an accident. We lost this beautiful soul. U can read about this on Google as well