Implementing a Linked List in Ruby
I am learning… actually relearning since I used these things in another life. So let me take a shot at a brief explanition. You should definitly take a look at the Wikipedia - Linked List article, though as they do a much better job of describing it than I do.
For one, a linked list is one of many ways of storing and organizing data. If you have been writing code for anything longer than a few months you probably already know a couple of data structures: Array, Dictionary & Hash to name a few. A linked list (at least a basic instance, and the instance I will demonstrate) is a class with two attributes: node and next. Node is just a generic type and can actually be a Ruby class like: String or Integer. Next is really a link to the next node.
Simple enough huh? Lets instantiate a few. I am going to use irb here so if you want to follow along now is the time to open your terminal and launch irb from the command prompt.
So what happened there? First I required the ruby file that contained the node class. Next I instantiated a node object called node with the node property “Oh Hai” (a String). I created a second node called node_2 with a node property of “How are you?”. Here is where the actual linking takes place. I set node’s next property to node_2. Then I just check the node’s and their links as well as the type of class that the node property is an instance of.
This is all well and fine, but it would be nice if we could see some type of visual representation of the structure. So lets implement a node_list method that will accept a starting node and return a string that should help make sense of this a bit more.
I forgot to mention that it will be a recursive method (see my article on the topic of Recursion). You’ll need to quit irb and require the ruby script again. Then create a few node instances and link them together via the nodes next property. Once you’ve completed that go ahead and call the Node class method node_list.
You should see node followed by -> followed by another node. Great so we have a linked list in Ruby. Now what? Well I actually was working on a code challenge where I had to reverse a linked list in Ruby. Honestly, I had a hard time with this. So much so that I started tearing tiny pieces of paper, labeling them and organizing them to figure out an algorithm.
Finally I figured one out, and while there is definitely a better solution I am burnt out and giving it a rest. That said I do want to walk through it with you. So here is the code:
How bout that… Now for the breakdown: well if we only have one node simply return it and were finished! Yay! That was the easy part. For the actual meat of this thing lets get a bit more visual. To set the stage I am going to create 4 nodes (numbers: 1, 2, 3 & 4) and link them together.
This is a kinda/sorta snapshot of what the memory might look like. Now we call the reverse method. Passing it node_1.
So inside the reverse method again we check to see if node.next is nil. Next we create three local variables swap, head & link. We set:
* swap to node which is currently pointed at node_1
* head to node.next which is currently pointing at node_2
* node.next to nil
* this breaks the link node_1 has to node_2 and points it at nil
* link to head.next which is pointing at node_3
Now in the while loop we begin actually reversing the linked list. We set:
* head.next to swap which is pointing at node_1 * swap to head which is pointing at node_2 * head to link which is pointing at node_3 * link to link.next which is pointing at node_4.
So if you printed the node listing it would look something like:
(in human words please)
* node_1’s link is broken/nil
* node_2 links to node_1
* node_3 links to node_4
* node_4’s link is broken/nil
Lets loop again since link is not nil (its pointing to node_4). We set:
* head.next to swap which is pointing at node_2
* swap to head which is pointing at node_3
* head to link which is pointing at node_4
* link to link.next which is pointing at nil
Lets loop again? No, link is nil so instead we do our final swap and return head.
Here is the complete code for my linked list implementation. If you have any improvements don’t hesitate to let me know. Feedback/comments are always welcome!