(Ruby version) Rotate linked list to the right by k places

I saw this question (javascript - rotate linked list to the right by k places) the other day and I tried implementing it in Ruby in a totally different way. Here's the code (I also created a REPL if you want to test it - https://repl.it/repls/PrimeSomeBlock):

node.rb

class Node
attr_accessor :value, :next_node

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

def initialize(nodes: [])
@nodes = nodes
end

def rotate(k)
self.class.new(nodes: rotate_nodes(k))
end

def rotate!(k)
@nodes = rotate_nodes(k)
end

def to_s
@nodes.map(&:value).join("->")
end

private

def rotate_nodes(k)
if !k.between?(1, @nodes.length) || !k.is_a?(Integer)
raise "k must be an integer between 1 and the length of the list"
end

@nodes.map do |node|
n = @nodes.find_index(node)
@nodes[n - k].next_node = n - k == 1 ? nil : @nodes[n - k + 1]
@nodes[n - k]
end
end
end

main.rb

require_relative "./node"

n4 = Node.new(value: 5)
n3 = Node.new(value: 3, next_node: n4)
n2 = Node.new(value: 7, next_node: n3)
n1 = Node.new(value: 7, next_node: n2)

nodes: [n1, n2, n3, n4]
)

puts <<~HEREDOC
Rotating #{linked_list1.to_s} by 2 places.

HEREDOC

n9 = Node.new(value: 5)
n8 = Node.new(value: 4, next_node: n9)
n7 = Node.new(value: 3, next_node: n8)
n6 = Node.new(value: 2, next_node: n7)
n5 = Node.new(value: 1, next_node: n6)

nodes: [n5, n6, n7, n8, n9]
)

puts <<~HEREDOC
Rotating #{linked_list2.to_s} by 3 places.
HEREDOC

Thoughts?

• My thoughts are that your code is perfect. There is no need to refactor it... It is very elegant and very beautiful :-) – Fabrizio Bertoglio Apr 27 at 9:33

My ruby is a little rusty, but I can give you some general pointers.

First off, this isn't really a linked list. You use an array in LinkedList. That is not how a linked list works. A linked list does not maintain an array of all of its nodes. If it is singly linked (usually the forward direction, which is what you're doing with next_node) then LinkedList should only hold the head of the list. So, first thing's first let's fix that. You also shouldn't expose Node. Your constructor is also a little strange. I'd expect it to work like the builtin Array. Namely, you don't pass nodes. You pass a size and a value or a size and a block to Array.new or through a separate method (Array()) something that is to_ary or to_a-able.

Again my ruby is rusty, but that would probably look something like this:

alias_method :count, :length

def initialize(length: 0, value: nil)
@length = length

(0..@length).reduce(Node.new) do |last_node, i|
node = Node.new(if block_given? yield i else value end)
last_node.next = node
@head = node if i == 0
node
end
end

def first
end

# Technically incomplete
# if !block_given?, then it should return an enumerator
def each
while !node.nil?
yield node.value
node = node.next
end
end

def to_a
values = []
each { |v| values << v }
values
end
end

values = values.to_ary if values.respond_to?(:to_ary) else values.to_a end
LinkedList.new(values.length) { |i| values[i] }
end

There may be a more elegant way to build the list from an arrayable (without needing to first construct the array), but it's not coming to me now. For completeness's sake, you probably want to also define the usual Enumerable methods (particularly each) so that you can test this. I provided first and each as examples of following the Enumerable convention.

Differentiating between rotate and rotate! is good. And your code reuse there is pretty nice (although given my qualms with the use of the array, I'm not a fan of rotate_nodes, more on that in a second). However, I'd recommend some further refactoring. It's unclear to me whether rotate is left or right. How about making it explicit: rotate_left, rotate_left!, rotate_right, and rotate_right!? And why not accept 0 or negative rotations? Let's say we defined right rotation. We could then define left rotation like this:

# ...

def rotate_left(delta)
rotate_right(-delta)
end

def rotate_left!(delta)
rotate_right!(-delta)
end

That feels much cleaner to me. I also wouldn't put the restriction that delta must be less than the length of your list (something you should definitely store by the way, don't rely on storing all the nodes in an array!). Instead, modulo the delta by the list length. So if the list has 5 elements and you rotate right by 7, that's the same as rotating right by 2. And if it isn't clear, rotating left by a negative amount should rotate right and vice versa.

Now, onto a more core problem. We'll start with your map in rotate_nodes:

def rotate_nodes(k)
# ...

@nodes.map do |node|
n = @nodes.find_index(node)
# ...
end

find_index is O(n). There's no reason to do this. This ends up being O(n^2). Instead use @nodes.each_with_index.map { |node, index| # ... }. But, like I've mentioned before, you shouldn't have @nodes in the first place. Without it, you have some concerns to deal with regarding the differences between your bang rotate methods and non-bang rotate methods. Namely this:

Let's say you added a first= method so you could change the value of the first element in the list:

def first=(value)
@length = 1
else
end
end

This could be used like so:

> a = LinkedList([1, 2, 3])
> a.head = 4
> a.to_a
[4, 2, 3]

Now, what do you expect when we do the following:

> a = LinkedList([1, 2, 3])
> a.rotate_right(1).rotate_left(1).head = 4
> a.to_a