3,935 reads

How to Implement Singly Linked List with Ruby

by Addo Boakye ForisonSeptember 7th, 2019

Too Long; Didn't Read

A linked List is a list in which each element in the list contains both data and a pointer to one or both neighboring items. Linked List is made up of elements(nodes) which are connected doubly or singly. Each node in a singly linked list has a.next attribute to indicate the next node after it (the current node) This discussion focus on singly-linked list would be discussed in my subsequent article. I am a passionate Fullstack developer skilled in JavaScript and Ruby on Ruby.

Company Mentioned

featured image - How to Implement Singly Linked List with Ruby

A list is a collection of elements. A linked List is a list in which each element in the list contains both data and a pointer to one or both neighboring items. Linked List is made up of elements(nodes) which are connected doubly or singly. When the nodes are connected doubly, we refer to such a list as a doubly-linked list. However, a singly linked list is a sequence of the element where the first node links to the second and the second links to the third and so on in one direction… On the other hand, a singly-linked list has nodes with pointers which always point to the next element in the list. This discussion focus on singly-linked list. Doubly-linked list would be discussed in my subsequent article.

Let us consider the list: 10 →20 →30

We can say 10 points to 20, 20 points to 30. The element of a list is referred to as a Node. So in this case 10 →20 →30, we would say Node10 points to Node20, and Node20 points to Node30. Each node in a singly linked list has a .next attribute to indicate the next node after it (the current node).

"NOTE: each node has .value for the current value and .next for next node(element)in the list. The first node is the head, in this case, head.value =10 and head.next=20"

Why use linked List?

Most people are used to using Arrays. The nature of arrays makes them efficient when we want to read data at a given position in the array, as this operation is run in constant time. Arrays are inefficient when it comes to insertion and deletion. Deletion and insertion are implemented efficiently with Linked List. Adding or deleting at the beginning of a list runs at constant time O(1). Adding at the given position also runs at linear time O(n). For instance, after deleting an element from an array the indexes of each element of the array would have to be readjusted because arrays are ordered collections of items indexed by contiguous integers.

How to Add or remove a node(element) from a singly-linked list

First, we would create a node to store the data. Nodes of a singly-linked list have two attributes: value( value of current node) and next_node(node after current)

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 storage let us add elements at the end of the list. This operation is an O(n) operation, to do.

For example, let us place

after 10 the list below

"Note: The algorithm for this would be to: create a new node. Make the node with value 10(head), point to the new node in this case the node with value 15 and make the new node with value 15 point to the node with value 20 (point head.next) which was the .next of the head before 15 was added."

Before beginning adding to the list, consider where in the list you intend to add to. 1. Add to an empty list(in our case list is not empty)2. Add at the first position3. Add at any position aside the first position (somewhere in the middle) 4. Add at the end of the list

Add at the end of the list

#create a new node 
      
   #if the head is nil it means the list is empty
      
   #this would imply that the new node is the head
    
   #if head is not nil then there are element in the list 
   # make a copy of head 
   #loop through the list from the head using the copy of the head
   #note when .next_node is nil current node is the last element
        
  
#add an element at the end of the list by pointing its to the new          node(the node you intend to insert) instead of nil
class LinkedList
    #setup head ,remmember we traverse a linkedlist from the head
    def initialize
      @head = nil
      @tail = nil
    end
    def add(number)
      
      #create a new node 
      this_node = Node.new(number)
      if @head.nil?
         @head = this_node
        return
      end
 
      current = @head  
      #until current.nil means until we reach the last node
      until current.next_node.nil?
        current = current.next_node
      end
   
      #point current(last node) to our new node
      current.next_node = this_node
      end
    end

Now let us consider adding an element at a specific position rather than adding at the end. The only difference between the two is that instead of looping to the end(till current.next.nil?), we will loop up to the position we want to insert at.

#if the node is empty the new node becomes the head
#to insert at 0 or first position pass a second argument to the node
#the second argument then becomes the second node and the first argument becomes the new head
#Otherwise loop to the desired position an make the insertion
class LinkedList
def add_at(index,item)
      if @head.nil? 
        #if list is empty, the head is the new node             
        this_nod=Node.new(item)
        @head=this_nod
      end
      if index==0 
        # if index is 0, we insert in the first position
        this_nod=Node.new(item,@head)
        @head=this_nod
      end
      if index >0
      #insert at desired position if index is greater than 0 
      ind=index-1
      current=@head
      before_current=@head
 
      #loop to the desired position before where you wish to insert
      ind.times do
          before_current=current.next_node
      end 
      #loop to the desired position where you wish to insert
      index.times do
          current=current.next_node
      end 
      #create a new node you wish to insert
      this_nod=Node.new(item) 
      after_current=before_current.next_node
      #point node before current to new node
      before_current.next_node=this_nod 
      #point new node to the old current node 
      this_nod.next_node=after_current
      
    
      end
    end 
end

Remove at a given position

let us consider deleting or removing an element from the a list. Assuming we want to delete(remove) 20 from our list

"Note: Make the node with value 10, point to the node with value 30. Afterwards, we make the node with value 20 point to itself(OR NIL). Once the head, in this case, points to the node with value 30, 20 is said to have been removed since it would no longer be accessible from the list."

Now let us try to remove an element from the list.

#if list is empty head.nil? is true so return "storage is empty"
#to insert at first position make a copy of the head 
#make the copy of the head .next point to the head thus making the head the second element
#insert at given position by looping to the said index make the previous node point to the .next value of the current node
#make the current node point to itself 
class LinkedList
def remove(index)
      if @head.nil?
        puts "the storage is empty"
      end
      if (index==0) 
        #remove the first element from the list
        current=@head 
        #get the element after the head and make head equal to it
        current.next=new_current 
        @head=new_current
      end
      if (index>0)
        current= get_node(index) #(desired node to be removed)
        before_current= get_node(index-1) 
        after_current=current.next_node
        before_current.next_node=after_current
      end
 end
end

"Note: the get_node method is a customized private method that get the node at a given position.This is to prevent repetition."

def get_node(index)
    current=@head
    index.times do
      current=current.next_node
    end
    return current
  end
#this returns a given node based on the index given as argument

In my next article, I will discuss how to implement a doubly linked list with Ruby.