Best linked list in ruby ​​WITHOUT array expansion?

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 have used in the past, but this does not seem to be the best way:

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 recently came across an interesting implementation of linked lists (not sure where unfortunately), where the Node class implemented insert and delete methods. The following is the Node class for a double linked list, but the same principles apply to a 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 this implementation interesting because I found it pretty universal. To start creating a list and processing it, no more than Node is required.

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

In addition to this implementation, you can create a more advanced API that is pretty easy to understand. Below is a more complete version of LinkedList or Deque . The list itself is a subclass of Node and links to the head and tail of the list.

 class ListNode < Node protected :remove # prevent incorrect access to 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's how to use it in practice:

 # create a new list list = ListNode.new # add some items to the head or tail list.add_to_head(Node.new('Hello')) list.add_to_tail(Node.new('World')) list.to_a # => ["Hello", "World"] # remove items from the head list.head.remove list.to_a # => ["World"] list.head == list.tail # => true # remove items from the tail list.tail.remove list.to_a # => [] 

Even better is the each method, which allows us to use any Enumerable function to search and 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 all nodes with values greater than 2 list.each.select {|node| node.value > 2 } # find the first node with a value of 4 list.each.find {|node| node.value == 4 } 

Answer 2

I assume that you are implementing this for self-study, otherwise it makes no sense. Just use Array , i.e. a list implementation for ruby.

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

Here's how a classic linked list teaches in college: O(n) for insertion, O(n) for search, and O(n) for delete. Subsequently, most books discuss improvements on it.

I wrote at the top of my head and did not conduct any tests at all, but this should give you an idea and, hopefully, an exercise to correct the errors found. (update: @Nitesh discovered a typo and fixed it. I hope she now has a test).

 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