Stack Implementation

Key Takeaways

welcome to part two of three in the stack Series this is going to be a short video on one way to implement a stack so Stacks are often implemented as either arrays singly linked lists or even sometimes doubly link lists here I will cover how to push nodes onto a stack with a singly linked list later on we will look at the source code which is actually written using a doubly linked list okay to begin with we need somewhere to start to be in our link list so we're going to point the head to a null node this means that the stack is initially empty then the trick to creating a stack using a singly linked list is to insert the new elements before the head and not at the tail of the list this way we have pointers pointing in the correct direction when we need to pop elements off of the stack as we will soon see the next element however we need to push onto the stack is at two so let's do that so we create a new node adjust the head pointer to be the newest node and then hook on the nodes next pointer to where the head was before and we use the same idea for five and also 13 now let's have a look at popping elements this isn't too hard either just move the head pointer to the next node and deallocate the last node so here we po the first node off the stack and set the nodes reference to be null so that will be picked up by the garbage collector if you're coding in Java and it will since there are no other references pointing to it if you're in another programming language that re requires you to explicitly deallocate and free memory yourself like C or C++ now is the time to do that or you will get memory leaks getting a memory leak in a data structure is one of the worst kinds of memory leaks especially if it's a custom data structure that you intend on reusing so keep watching out for not only in this video but in all the data structures that uh we will be covering if you see in an implementation that I'm not correctly cleaning up my memory please please point it out to me or send a poll request to the GitHub repository so we can patch that okay so we keep proceeding by removing the head and advancing the head pointer down to the next node pop again and pop again and there we go we've stopped popping we've reached last node and the stack is now empty all right time to look at some source code I implemented a stack using a dou link list that we can look at in some detail if you're interested in the source code for the stack in the next video have a link at the code repo provided on the slide it should be provided in the description thanks for watching and I'll see you in the next video