Singly Linked Lists in Ruby
What is a Linked list?
A Linked list is a linear data structure that is an organized set of nodes. These nodes contain two elements, a value that is that data you want to store, as well as a pointer that will point to the next node in line. The first node in a linked list is referred to as the head, and the last node in a link list is referred to as the tail. Linked lists are null-terminated, meaning that when we hit the tail node and that node’s pointer points to null, we’ve reached the end of the list. Here is a visual representation of what's going on in a linked list:
Why use Linked lists?
Linked lists are a lot more efficient for actions like inserting or removing data as you just need to traverse the list and create a new node at the index we want, as opposed to if we wanted to do so in an array we should have to shift the index of each element in the array which can take up a lot more time. You may be asking “Why not just use a hash table then?” well lists are doing similar actions to hash tables, the one benefit it has is that linked lists that there is order within linked lists so we can have sorted data, which hash tables cannot. Now that we have an idea of linked lists conceptually and know why we would use them, let's start with some code.
Some languages have a linked list class out of the box, Ruby does not, but we can make our own first thing we’re going to need to do is to create a node class so that we’re able to create new instances of nodes.
On the creation of a new node, we want to set the value of the node as well as point to the next node.
Now that our node class is all set up, let’s build the LinkedList class.
Upon creating a new linked list we are creating a new node that will be the head node and contain the value we pass in as well as point to nil as we only have one node. The tail is being assigned to the head node because at the time of creation there is only one node and the same with length, upon creation of a new linked list the length will always start at 1. But as it is this linked list doesn’t do much so let's start creating some actions such as appending(adding to the end of the list) and prepending(adding to the front of the list).
With the append method, we are getting our current tail, assigning that node’s next value to be a new instance of a node containing the value that is being passed in, we are then assigning the tail to be that same node. So if we wanted to check our work through our irb console, we would input:
my_list = LinkedList.new(10)
my_list.append(16)
my_list#should return:
#<LinkedList:0x000055f3f8bf5828 @head=#<Node:0x000055f3f8bf5800 @value=10, @next=#<Node:0x000055f3f89a0910 @value=16, @next=nil>>, @tail=#<Node:0x000055f3f89a08e8 @value=16, @next=nil>, @length=2>
Awesome! it’s showing our initial head node pointing to that new node we created and that our tail is also that new node and it’s increasing our length, perfect! Now onto our prepend, here we’re just assigning head to be a new node where it’s value is the value being passed in and it’s next node points to the previous head and increase the length of our list by 1. We run :
my_list.prepend(20)
my_list#output:
#<LinkedList:0x000055f3f8bf5828 @head=#<Node:0x000055f3f833b188 @value=20, @next=#<Node:0x000055f3f8bf5800 @value=10, @next=#<Node:0x000055f3f89a0910 @value=16, @next=nil>>>, @tail=#<Node:0x000055f3f89a08e8 @value=16, @next=nil>, @length=3>
Those seem pretty straight forward, adding to the beginning and end of the list, these actions are in constant time(O(1)) so they’re very fast. now let’s move onto something a little bit trickier, find, insert, and remove. These actions are all going to include some traversal so they will be in linear time(O(n)).
For these methods we want our find method to do is given a number, give us the node matching that index, our insert to insert a new node at a given index, and for remove to remove a node at a given index.
Whenever you need to traverse through a linked list you always want to have a starting point which is typically going to be your head node and we’ll be doing such with the following methods. Starting off with our find method, the first thing we want to check is the number being passed in greater than our links length? because if it is, we’re obviously not going to have a node to return. so we run the check on the first line and return a string letting the user know that there is no node tied to that index. As stated before we are creating a variable called current_node and assigning it to our starting point which is the head node. we’re also assigning i = 0 because as we go through our nodes we’re going to increase the number of i until it matches the passed in value, once it does that, return that node as it is the one being requested. So we set our while loop, while i is not equal to index our current_node is equal to the next node it’s pointing to. That how we traverse the linked list!
For the insert method, just like the find method, we have to do some checks first. If the index being passed in is equal to 0, we don’t have to do any traversal at all, let’s use the handy method we made earlier to add the value to the front of the list. Our second check is if say if someone inputs an index of 1000 to our my_list linked list. Since our list isn’t that long let’s just put the value to the end of the list using our append method. Now that our checks have been set let’s get to the meat and potatoes. The leader variable is using our find method to return us the previous node of the index that was passed in. We want to do this because we want that node’s pointer to point to this new node we’re inserting. To do that we say, leader.next = the new node we want to create, passing in a value, and have that next be the previous leader.next. To test this out let's go back to our my_list and insert a new node.
my_list.insert(1, 32)
my_list#output:
#<LinkedList:0x000055d6892fb088 @head=#<Node:0x000055d689306f28 @value=20, @next=#<Node:0x000055d689076e70 @value=32, @next=#<Node:0x000055d6892fb060 @value=10, @next=#<Node:0x000055d6893e3d38 @value=16, @next=nil>>>>, @tail=#<Node:0x000055d6893e3d10 @value=16, @next=nil>, @length=4>
And would you look at that, we have the node with the value of 32 at the index of 1!
Last but not least we have our remove method, which is going to take in an index and remove that node from the list. We do our check to make things easier on ourselves. if the index passed in is 0, then we’re assigning the head node to equal head.next which is the node that it is pointing to. If that isn't the case then we’ll do the same action as the insert. let’s find the node previous to the node of the passed in index. We want to assign the node we want to remove to a variable to we do to_remove = leader.next. We then assign leader’s pointer to point to the node to be removed’s pointer, taking the to_remove node out from the list. LEt’s test it out and see if it works:
my_list.remove(1)
my_list#output:
#<LinkedList:0x000055d6892fb088 @head=#<Node:0x000055d689306f28 @value=20, @next=#<Node:0x000055d6892fb060 @value=10, @next=#<Node:0x000055d6893e3d38 @value=16, @next=nil>>>, @tail=#<Node:0x000055d6893e3d10 @value=16, @next=nil>, @length=3>
And would you look at that, we had removed the node we had inserted before which held the value of 32. There you have it, we’ve created a singly linked list from scratch. I can’t wait to see what you do with this newfound power.
Happy Coding!
