How to Create a Linked List in Ruby?

How to Create a Linked List in C?

A linked list is a form of linear data structure whereby the elements are not positioned closely together in memory. Each element here instead points to the subsequent one, thus leading to a chain-like arrangement.

Creating a linked list in Ruby entails defining an information structure where each node has value and link (or reference) to the next node in the sequence. It is also dynamic meaning it can grow or shrink during runtime making it efficient for specific operations such as insertion and deletion.

Approach to Create a Linked List

Create a class for Node which has an attribute for value and the next node.
Create a class for LinkedList with methods to add elements, remove elements, and other necessary operations.

Node Class

The Node class represents each item of the linked list. It has two attributes: value which stores the data, and next_node which keeps track of what follows after it in the list. The initialize function sets up the beginning value of this node along with initializes next_node as nil.

class Node
attr_accessor :value, :next_node
def initialize(value)
@value = value
@next_node = nil
end
end

Linked List Class

The LinkedList class represents all nodes available in an entire linked list. Initially pointing to first node in a list, @head is its only instance variable at first since there isn’t any item on that list.

class LinkedList
def initialize
@head = nil
end

Adding Nodes

The add method adds an element to the linked list at its end.
If the linked list is empty (the head pointer i.e. @head is nil), we create a new node and make it point to @head.
Otherwise, it traverses the list until it gets to the last node (node.next_node =nil) and then inserts anode after it.

def add(value)
if @head.nil?
@head = Node.new(value)
else
current = @head
while current.next_node != nil
current = current.next_node
end
current.next_node = Node.new(value)
end
end

Removing Nodes

The remove method removes the first occurrence of a node with the given value from the linked list.
If that node is found in the beginning of the list, @head should be updated so that it points to next_node.
Else, go through all nodes starting from start till one before current and update reference for next_node for this previous one to skip over current one being removed.

def remove(value)
current = @head
if current.value == value
@head = current.next_node
else
while (current.next_node != nil) && (current.next_node.value != value)
current = current.next_node
end
if current.next_node != nil
current.next_node = current.next_node.next_node
end
end
end

Displaying Linked List

The display method prints values of all nodes in a linked list.
It starts at @head and goes on outputting each node’s value followed by “->” until reaching nil which means end of a cell structure.

def display
current = @head
while current != nil
print “#{current.value} -> “
current = current.next_node
end
puts “nil”
end

Implementation of Linked List using Ruby

Below Ruby program demonstrates creating a linked list, adding nodes to it, displaying its contents, and removing a node.

Initially ll was created as 1 -> 2 -> 3 -> nil.
Later on, second item in ll whose value is 2 was removed so now ll has become 1 -> 3 -> nil.

Ruby

class Node
  attr_accessor :value, :next_node

  # Initialize a new node with a given value
  def initialize(value)
    @value = value
    
    # Initially, the next node reference is nil
    @next_node = nil  
  end
end

class LinkedList
  
  # Initialize an empty linked list
  def initialize
    
    # Initially, the linked list has no nodes, 
    # so head is nil
    @head = nil  
  end

  # Add a new node with the given value to the 
  # end of the linked list
  def add(value)
    
    # If the linked list is empty
    if @head.nil?  
      
      # Create a new node and set it as the head
      @head = Node.new(value)  
    else
      current = @head
      
      # Traverse the list until the last node
      while current.next_node != nil
        current = current.next_node
      end
      
      # Append the new node to the end of the list
      current.next_node = Node.new(value)
    end
  end

  # Remove the first occurrence of a node with the 
  # given value from the linked list
  def remove(value)
    current = @head
    
    # If the node to be removed is the head
    if current.value == value
      
      # Update head to point to the next node
      @head = current.next_node  
    else
      
      # Traverse the list until the node before 
      # the one to be removed
      while (current.next_node != nil) && 
            (current.next_node.value != value)
        current = current.next_node
      end
      
      # Update the next_node reference to skip 
      # over the node to be removed
      if current.next_node != nil
        current.next_node = current.next_node.next_node
      end
    end
  end

  # Display the values of all nodes in the linked list
  def display
    current = @head
    while current != nil
      print "#{current.value} -> "
      current = current.next_node
    end
    
    # Indicate the end of the list
    puts "nil"  
  end
end

# Example usage:
ll = LinkedList.new
ll.add(1)
ll.add(2)
ll.add(3)
ll.display
ll.remove(2)
ll.display

Output

1 -> 2 -> 3 -> nil
1 -> 3 -> nil

Tags:

#Ruby

How to Create a Linked List in C?