Computer Science‎ > ‎

Basic Data Structures in Ruby - Linked List - ( A Simple, Singly Linked List)



Programming With Ruby



For a general description of the linked list data structure, with C program source code, you might want to take a look at : C Program ( Source Code and Explanation) for a Single Linked List. This program, along with the comments, will hopefully give you a decent idea of how to go about implementing a Linked List in Ruby.

# Quick Example of a Self Referential Data Structure in Ruby 
# NODE -> contains a value and a pointer to (next_node)
# LinkedList -> This class holds the linked list functions - adding a node, traversing and displaying the linked list

class Node

    attr_accessor :value, :next_node

    def initialize val,next_in_line
        @value = val
        @next_nodex = next_in_line
        puts "Initialized a Node with value:  " + value.to_s 
    end
end

class LinkedList

    def initialize val
        # Initialize a new node at the head
        @head = Node.new(val,nil)
    end
    
    def add(value)
        # Traverse to the end of the list
        # And insert a new node over there with the specified value
        current = @head
        while current.next_node != nil
            current = current.next_node
        end 
        current.next_node = Node.new(value,nil)
        self    
    end

    def delete(val)
        current = @head
        if current.value == val
            # If the head is the element to be delete, the head needs to be updated
            @head = @head.next_node
        else
            # ... x -> y -> z
            # Suppose y is the value to be deleted, you need to reshape the above list to :
            #   ... x->z
            # ( and z is basically y.next_node )
            current = @head
            while (current != nil) && (current.next_node != nil) && ((current.next_node).value != val)
                current = current.next_node
            end 

            if (current != nil) && (current.next_node != nil)
                current.next_node = (current.next_node).next_node
            end
        end
    end
    
    def display
        # Traverse through the list till you hit the "nil" at the end
        current = @head
        full_list = [] 
        while current.next_node != nil 
            full_list += [current.value.to_s]
            current = current.next_node
        end
        full_list += [current.value.to_s]
        puts full_list.join("->")
    end

end

# Initializing a Linked List with a node containing value (5)
ll = LinkedList.new(5)

# Adding Elements to Linked List
ll.add(10)
ll.add(20)

# Display the Linked List
puts "Displaying Linked List:"
ll.display

puts "Delete 10 and then display the linked list:"
ll.delete(10)
ll.display

=begin
Output:
Initialized a Node with value:  5
Initialized a Node with value:  10
Initialized a Node with value:  20
Displaying Linked List:
5->10->20
Delete 10 and then display the linked list:
5->20
=end
 


Check out some of our other Ruby Tutorials :

Introduction to Ruby

 Introduction to Ruby and some playing around with the Interactive Ruby Shell (irb) Introduction to Ruby - Conditional statements and Modifiers: If-then, Unless, Case Introduction to Ruby Comments - Single and Multi-Line comments Introduction to Ruby Loops - Using While, Until, For, Break, Next , Redo, Retry
 Introduction to Ruby - Arrays - Sorting, Filtering (Select), Transforming, Multi-Dimensional Arrays Introduction to Ruby - Strings Introduction to Ruby - Making a Script Executable Introduction to Ruby - Regular Expressions, Match, Scan
 Introduction to Ruby - Computing Factorials Recursively : An Example of Recursion Introduction to Ruby - Binomial Coefficients (nCr) : An Example of Recursion Introduction to Ruby - Computing a Power Set : An Example of Recursion Introduction to Ruby - Towers of Hanoi : An Example of Recursion
 Introduction to Ruby - Strings: Substitution, Encoding, Built-In Methods 



Basic Data Structures With Ruby