Following on from the last post, tonight I am going to try and implement the stack using a linked list instead of an array.
As explained in the course, a linked list might be preferred over an array, because in languages like C, an array has to be of fixed size. Adding a one more element to a full stack will cause an overflow error at best and overwrite random memory addresses at worst. Each element of the linked list is dynamically allocated on the heap, which means that the stack’s size is unbounded. The tradeoff of using a linked list is increased memory size. The memory structure of each stack item needs to hold a pointer to the next item in the list, as well as the stored value.
Ruby implementation first
Ruby is a language I have far more experience in, so I’m going to start there. I’m going to reuse the
Stack interface from the last post.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
I’m going to supplant the
store parameter with a linked list implementation. The linked list needs to have two things, a place to store the value and a pointer to the next item in the list.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
The implementation of a linked list in an object-oriented language is straightforward. You need a
Node that holds a
value and a pointer to the next
Node. A stack on top of a linked list consists of the following steps:
- Add a new
- Set its
next_nodepointer to the current value of
headto point to the new
With these steps completed,
pop mean reading the value of
head and setting
head to the next node in the list, respectively. An empty check is just checking that
head points to nothing.
Here’s how that looks like:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
I suspect that writing a linked list in Clojure will be just as awkward as trying to hide the array as the implementation detail in Ruby. I am going to try anyway.
Firstly, I’ll define a record to hold my data. The data held is the same, a
value and a
Then, I’ll define functions that manipulate the stack. I need a helper function to resolve the top of the stack, as well as the expected ones.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
I’m storing the current state in an
atom, like before, which is there are
reset! calls in the
pop* functions. The logic for
push* is fairly simple. If the
nil, it means we don’t have anything on the stack, so create a new instance of the defined record. If there is something there, create a new instance of the defined record and set its
next-node value to the old instance.
pop* does nearly the opposite. It saves the value of the current instance, then resets the atom such that it points to the next instance, effectively discarding the current one.
top* should be self-explanatory. I wanted to use
defprotocol to define the
empty? methods as in the Ruby version, but I still don’t fully understand how that works. Here is my desired implementation, so maybe someone can point me in the right direction.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
That’s it for tonight. Next up, I’ll try on the queues for a size.