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. , @value = value @next_node = next_node class Node attr_accessor :value :next_node def initialize (value, next_node = ) nil end end Now that we have our Node class we can create our LinkedList class. , @head = @tail = class LinkedList attr_accessor :tail :head def initialize nil 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. = puts list . LinkedList new list Then in the console run our ruby file and see the output. user@PC/desktop/ ~$ ruby linked_list.rb Ruby: #<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. @head = Node.new(data, @head) def add_first (data) 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. node = Node.new(number) !@head @head = node @tail = node last_node = get_last() last_node.next_node = node @tail = node private !@head node = @head node.next_node. ? node = node.next_node node def add_last (data) if return end end def get_last return if until nil end return 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. !@head @head = Node.new(data) index == add_first(data) previous = get_node(index — ) get_last() node = Node.new(data, previous.next_node) previous.next_node = node private !@head @head index === node = @head counter = node.next_node. ? node = node.next_node counter+= node counter === index def add_at (index, data) if return end if 0 return end 1 || end def get_node (index) return if return if 0 0 until nil 1 return if 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 , and . remove_first remove_last remove_at !@head @head = @head.next_node !@head !@head.next_node @head = prev = @head node = @head.next_node node.next_node node = node.next_node prev = prev.next_node @tail = prev prev.next_node = !@head index == @head = @head.next_node previous = get_node(index- ) !previous !previous.next_node previous.next_node = previous.next_node.next_node def remove_first return nil if end def remove_last return nil if if nil return end while do end nil end def remove_at (index) return if if 0 return end 1 if || return end 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. @head = @tail = !@head node = @head counter = node node = node.next_node counter += counter @head.value def clear nil nil end def size return 0 if 0 while do 1 end end def get_first 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.
