data structures - best linked list in ruby WITHOUT extending array? -

what best way implement linked list in ruby without using/extending array class? implementation i've used in past, doesn't seem best way go 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 new node list, amakes new head , links former head         new_node = node.new(value)         new_node.next_node = @head          @head = new_node     end      def remove         @head = @head.next_node     end end 

i came across interesting implementation of linked lists (not sure unfortunatly) node class implemented insert , removal methods. following node class double linked list, same principles apply single linked list.

class node   protected   attr_writer :prev, :next    public   attr_reader :value, :prev, :next    def initialize(value)     @value = value   end    def remove     @prev.next = @next if @prev     @next.prev = @prev if @next     @next = @prev = nil   end    def insert_after(node)     remove      @next = node.next     @next.prev = self if @next     @prev = node     node.next = self   end end 

i find implementation interesting because i've found quite versatile. nothing more node needed start building out list , manipulating it.

head = node.new(1)  middle = node.new(2) middle.insert_after(head)  tail = node.new(3) tail.insert_after(middle)  middle.remove 

on top of implementation can build more advanced api that's pretty easy understand. following more complete version of linkedlist or deque. list subclasses node , links head , tail of list.

class listnode < node   protected :remove # prevent incorrect access node methods    def initialize     @next = @prev = self   end    def head     @next unless @next == self   end    def tail     @prev unless @prev == self   end    def add_to_head(node)     node.insert_after(self)   end    def add_to_tail(node)     node.insert_after(self.prev)   end    def each(&block)     return enum_for(:each) unless block_given?     node = @next     while node != self       yield node       node = node.next     end   end    def to_a     each.collect {|node| node.value }   end end 

and here how can used in practice:

# create new list list = listnode.new  # add items head or tail list.add_to_head(node.new('hello')) list.add_to_tail(node.new('world')) list.to_a # => ["hello", "world"]  # remove items head list.head.remove list.to_a # => ["world"] list.head == list.tail # => true  # remove items tail list.tail.remove list.to_a # => [] 

even better each method allows use of enumerable functions search , iterate through nodes:

list = listnode.new list.add_to_head(node.new(1)) list.add_to_head(node.new(2)) list.add_to_head(node.new(3)) list.add_to_head(node.new(4))  # list each value list.each {|node| puts node.value }  # select nodes values greater 2 list.each.select {|node| node.value > 2 }  # find first node value of 4 list.each.find {|node| node.value == 4 }