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 peek, pop, and push method which operate in O(1) time because our stack maintains a that references the last item.
peek()
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 last pointer.
push(item)
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.
pop()
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 null.
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.