Implement a Stack
With stacks, we only care about fast operations at the end. This makes a linked list the perfect data structure to implement them.
Stacks can also be implemented using a dynamic array, but we will gain a better understanding of how it functions by maintaining the stack ourselves. When you are answering an interview question, you are totally fine to use a dynamic array as stack for simplicity.
Our linked list will be built using
Node objects that stores
data and use the
prev attribute to reference the node behind it in the stack.
We will implement a
push method which operate in O(1) time because our stack maintains a that references the
Peek allows us to view the last item that is at the top of the stack.
This is the newest item added to the stack.
We simply return the value in our
This adds an item to the end of the list.
We create a new linked list node and point its
prev to the item previously at the top.
The previous last item would be
null if this is the first item added to the list.
This function removes the last item from the list and returns it.
If the list is empty, or it is the last item in the list, the function will return
Complete Stack Implementation
Putting it all together, we have the following implementation. If you want to see it in action, you can use it in this REPL.
Stack Built with Array
Stacks can be implemented very simply using a dynamic array. Operations at the end of an array all happen in O(1) time, so we haven't sacrificed any Big O complexity. See the implementation in this REPL.
Table of Contents