Understanding Linkedlist Data Structure (Ruby)

Yair Fernando
Apr 17, 2020 · 6 min read
Image for post
Image for post

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.

Image for post
Image for post
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

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.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
privatedef 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
privatedef 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.

Image for post
Image for post

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.

The Startup

Medium's largest active publication, followed by +753K people. Follow to join our community.

Yair Fernando

Written by

I'm a passionate and motivated developer with three years of experience and a knack for creating software applications. I like the changing nature of the web

The Startup

Medium's largest active publication, followed by +753K people. Follow to join our community.

Yair Fernando

Written by

I'm a passionate and motivated developer with three years of experience and a knack for creating software applications. I like the changing nature of the web

The Startup

Medium's largest active publication, followed by +753K people. Follow to join our community.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store