Building a simple Stack in Java. (Part 2)
- 4 minsIn the post yesterday we started putting together a simple Stack using Java and we stopped at the last failing test which was this:
To make the test pass and not break any previous ones we’ll put the right implementation in place and will use a Linked List for that. I’ll post the full code and explain each part individually. Before that I put together a small diagram which can be found here, that explains the browser example I gave in yesterdays post in a more visual way.
The final code implementing a Linked List and making the final test pass follows:
There’s a few things going on. First of a new class was introduced Link
which has two attributes; A value
which will be a string and next
which will be an Item
. When a new Link
is created it takes a string as an argument which sets the value of the value
attribute. We then create two getters getValue
and getNext
plus a setter setNext
, for the next
attribute.
Next up is the part which took me a while to wrap my head around, possibly because I was visually imagining it from the wrong perspective. Lets start with the push
method. When a new item is pushed in, it does the following:
- Creates a new
Item
and stores it into the local variablenewItem
. The string that comes through sets thevalue
of thatItem
- Assigns the
head
attribute to the local variableoldHead
which will be of typeLink
- Set the value of
head
tonewItem
- Then set the
head
’snext
value to theoldHead
value
If you are confused don’t worry, I’m pretty sure most people including me are when they look at the above, at least the first couple of times. To help I’ve put together another diagram continuing with the browser example which hopefully make things more clear. The only part from the above that is there from before is the increment of size
.
The pop
method is a bit more straightforward:
- Create
oldHead
local variable with the value ofhead
- Set the value of
head
tooldHead
’snext
value - Return the value of
oldHead
Again this diagram might be helpful in order to understand the chain of events. I also found looking at both events, push
and pop
, together helps even more so this is a shot of both diagrams combined. The one thing that initially confused me was thinking about a Linked List as an array. That’s the first thing I was thinking we would need to implement at some point and that thought didn’t leave me even after we had done the final solution. Once I went through it a couple more times and drew some diagrams it became more clear.
Implementing the above was an interesting challenge but it helped me understand a commonly used data structure which in turn increased my knowledge of the fundamentals of programming significantly. I would definitely encourage anyone to do the same in any language they’re learning. Practising these sort of things is essential and will be doing more of these as I move forward.