best linked list in ruby WITHOUT extending array?

Question

What is the best way to implement a linked list in Ruby without using/extending the Array class? This is an implementation that I've used in the past, but it doesn't seem like the best way to go about it:

class Node

    attr_accessor :value, :next_node

    def initialize(value = nil)
        @value = value
    end

    def to_s
        @value
    end

end

class SinglyLinkedList

    attr_accessor :head

    def initialize(first_value=nil)
        @head = Node.new(first_value) if first_value
    end

    def add(value)
        #adds a new node to the list, amakes it the new head and links it to the former head
        new_node = Node.new(value)
        new_node.next_node = @head

        @head = new_node
    end

    def remove
        @head = @head.next_node
    end
end

Answer 1

I assume you are implementing this for self-teaching, otherwise it doesn't makes any sense. Just use Array, that is the list implementation for ruby.

In my opinion, you should write these exercises in C, because the whole point in implementing a linked list is to be closer to the machine and understand better how it works. C is a way better tool for this task, understand how computer works.

This is how a classical linked list is teach on college: O(n) to insert, O(n) to search, and O(n) to delete. Afterwards, most books discuss about improvements on it.

I wrote in in the top of my head, and did no tests on it at all, but this should give you an idea, and hopefully an exercise to correct any bugs you found. (update: @Nitesh found a typo, and fixed it. Hopefully it have some test now).

class Node
    attr_accessor :value, :next

    def initialize(value = nil)
        @value = value
    end

    def to_s
        @value
    end
end

class SinglyLinkedList

    attr_accessor :head

    def initialize(first_value=nil)
      @head = Node.new(first_value) if first_value
    end

    def add(value)
      if head.nil?
        head = Node.new(value)
      else
        current_node = @head
        while current_node.next
          current_node = current_node.next
        end
        current_node.next = Node.new(value)
      end
    end

    def find(value)
      current_node = head
      while current_node != nil
        return current_node if current_node.value == value
        current_node = current_node.next
      end
      nil
    end

    def remove(value)
      if head.value == value
        head = head.next
      else
        current_node = head.next
        prev_node = head
        while current_node
          if current_node.value == value
            prev_node.next = current_node.next
            return true
          end
          prev_node = current_node
          current_node = current_node.next
        end
        nil
      end
    end
end