If you are familiar with data structures you may have heard about a LinkedList.
In this article, we will create a singly LinkedList from scratch and explain how this data structure works and what it is useful for.
Let’s first illustrate the concept of a linked list.
In simple words, a LinkedList is a data structure that consists of a collection of data.
The values in a LinkedList represents nodes and each node contains a pointer to the next node. In a LinkedList, the data of each node can be anything. We called the first node the head and the last one the tail.
This data structure is similar to an array because we can use both to store linear data. Though they have some differences, let’s dive into it.
First, in a LinkedList, the Big O time complexity to retrieve elements is 0(n). The reason is that with a linked list we can not retrieve an element by its index like in arrays.
We need to iterate through the list from the head until we find the element that we want to retrieve.
At this point, you may be thinking that it is better to use arrays instead of a LinkedList. Because we have better runtime complexity accessing elements with arrays.
Now let’s talk about deletion and insertion.
These operations in arrays consume a lot of time. On the other hand, the performance of these operations in a LinkedList is fast. Also, arrays have a fixed size and Linked lists are dynamic and can expand its size.
Ultimately linked lists need less space in memory than arrays.
Now we are ready to start implementing a Linked list…
First, we will create the node class that will help us to append new nodes to our Linked list.
class Node attr_accessor :value, :next_node def initialize(value, next_node = nil) @value = value @next_node = next_node end end
Now that we have our Node class we can create our LinkedList class.
class LinkedList attr_accessor :tail, :head def initialize @head = nil @tail = nil end end
For our LinkedList class, we also define two accessors(tail, head). The head will be the first element inside the LinkedList and the tail will be the last one.
We also used the constructor method to assign the initial values.
This is the basic set up to create a LinkedList, to test it we can create an instance of our LinkedList class.
list = LinkedList.new puts list
Then in the console run our ruby file and see the output.
user@PC/desktop/Ruby:~$ ruby linked_list.rb #<LinkedList:0x00000000051ff9a0>
Now we can create our first method to add a new element to our LinkedList. We will start by adding the add_first method.
def add_first(data) @head = Node.new(data, @head) end
With this method now we can append elements at the beginning of our LinkedList. Since we are setting the @head to the new node and we are passing the data and the @head as the second parameter. The results will be that the element will be inserted in the first position of the list.
Let’s create now a new method to append at the end of the list.
def add_last(data) node = Node.new(number) if !@head @head = node @tail = node return end last_node = get_last() last_node.next_node = node @tail = node end private def get_last return if !@head node = @head until node.next_node.nil? node = node.next_node end return node end
In this case, we have two methods. One that helps to get the last node and that is private, and the other adds the node to the end of the list. In the first method, we first create a new node and pass the data.
Then we check if the @head is nil and if it is we set the @head and @tail to the new node and return so the execution stops. If the @head is not nil then we get the last node by calling the get_last method. Then set the next_node to the new node and lastly, we assign the node to the @tail.
Great now we can append new elements to the end and to the front of the list. But we can do even better by creating a method that appends elements at a specific position so let’s see how we can do this.
def add_at(index, data) if !@head @head = Node.new(data) return end if index == 0 add_first(data) return end previous = get_node(index — 1) || get_last() node = Node.new(data, previous.next_node) previous.next_node = node end private def get_node(index) return if !@head return @head if index === 0 node = @head counter = 0 until node.next_node.nil? node = node.next_node counter+=1 return node if counter === index end end
Here again, we have another private method that helps us to get a node at a specific index. In the add_at method, we take the index and the data and if the @head is nil we assign the @head to a new node. Then return to stop the execution. If the @head is not nil we check if the index is equal to 0 and if it is we called the add_first method and pass the data. This way we are reusing methods which is always a good practice.
Then if the index is not 0 we create a variable called previous and assign it to the resulting value of the get_node or get_last methods. If one of them returns nil then the previous variable will take the value of the other method. Then we create a new node and pass the data and the previous.next_node as a second parameter. Lastly, we assign the previous.next_node to the just created node.
Now we can basically append elements to our list at any specific position..Great!!
We will do the same to remove elements. We’ll have three methods remove_first, remove_last and remove_at.
def remove_first return nil if !@head @head = @head.next_node end def remove_last return nil if !@head if !@head.next_node @head = nil return end prev = @head node = @head.next_node while node.next_node do node = node.next_node prev = prev.next_node end @tail = prev prev.next_node = nil end def remove_at(index) return if !@head if index == 0 @head = @head.next_node return end previous = get_node(index-1) if !previous || !previous.next_node return end previous.next_node = previous.next_node.next_node end
These three methods follow the same logic that the ones that we used to append. The only difference is the operation (remove/add).
Lastly, we want to get the first element, clear our LinkedList and also get the size, let’s put in place these methods.
def clear @head = nil @tail = nil end def size return 0 if !@head node = @head counter = 0 while node do node = node.next_node counter += 1 end counter end def get_first @head.value end
In the clear method, we just assign the @head and @tail to nil. Pretty easy. In the get_first method, we return the value of the @head. In the size method, we iterate through the head and create a counter until the node is nil, then return the counter. Really straightforward as well.
Awesome we have implemented a Linked list data structure with different methods.
LinkedList is a great data structure that is implemented in computer since. Also with queues and stacks. It is quite important to understand how it works since many applications use linked lists to store data because they can perform constant operations that arrays can not.
See different uses of a LinkedList here.
In the real world, the space in memory that your data structure uses could determine a huge change. That is why LinkedList is so helpful in some cases. It is important to know that there are cases where it is better to use arrays so everything depends on your needs.
I hope you enjoyed and learned something new, share this article if you like it and thank you for reading.