Understanding Linkedlist Data Structure (Ruby)

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.

Run time complexity Big O Notation

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 @headif 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.