# Understanding Linkedlist Data Structure (Ruby)

Apr 17, 2020 · 6 min read

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.

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  endend`

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  endend`

or 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.newputs 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 = nodeendprivatedef get_last  return if !@head  node = @head  until node.next_node.nil?    node = node.next_node  end  return nodeend`

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 = nodeendprivatedef get_node(index)  return if !@head  return @headif index === 0   node = @head  counter = 0  until node.next_node.nil?    node = node.next_node    counter+=1    return node if counter === index  endend`

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_nodeenddef 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 = nilenddef 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_nodeend`

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 = nilenddef size  return 0 if !@head  node = @head  counter = 0  while node do    node = node.next_node    counter += 1  end  counterenddef get_first  @head.valueend`

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.

Written by

Written by