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

Question

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

linked_list.rb

class LinkedList
 attr_reader :nodes
 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"
require_relative "./linked_list"
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)
linked_list1 = LinkedList.new(
 nodes: [n1, n2, n3, n4]
)
puts <<~HEREDOC
 Rotating #{linked_list1.to_s} by 2 places.
 :: #{linked_list1.rotate(2).to_s}
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)
linked_list2 = LinkedList.new(
 nodes: [n5, n6, n7, n8, n9]
)
puts <<~HEREDOC
 Rotating #{linked_list2.to_s} by 3 places.
 :: #{linked_list2.rotate(3).to_s}
HEREDOC

Thoughts?

• fabOnReact: My thoughts are that your code is perfect. There is no need to refactor it... It is very elegant and very beautiful :-)

Answer 1

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:

class LinkedList
 attr_reader :length
 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
 @head.?value
 end
 # Technically incomplete
 # if !block_given?, then it should return an enumerator
 def each
 node = @head
 while !node.nil?
 yield node.value
 node = node.next
 end
 end
 def to_a
 values = []
 each { |v| values << v }
 values
 end
end
def LinkedList(values)
 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:

class LinkedList
 # ...
 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)
 if @head.nil?
 @head = Node.new(value)
 @length = 1
 else
 @head.value = value
 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

rotate_left and rotate_right aren't bang methods, so we don't expect to be able to change the underlying linked list. You demonstrate this understanding in how you initialize and return a new linked list for those methods. But, returning a new linked list isn't enough. rotate_right(1) is the equivalent of taking the tail of the linked list and placing it at the head. This can be done fairly trivially by moving some of the nexts around and then setting @head. But, if you share Nodes between LinkedLists, then that .head = 4 will modify the original list. I'm not sure that's the behavior you want. You'll have to think about the semantics you desire. It's clear that the bang methods should modify the existing LinkedList in place. But, it's less clear what an example like the one above should do. On the one hand, you could copy all of the nodes so that each Node belongs to only one LinkedList. However, this incurs a high memory penalty, especially if you didn't actually need the copy (say for some reason you just did a.rotate_right(10).head, you don't actually need the copy, this is equivalent to just getting the 11th element in the list). On the other hand, you could have Nodes belong to multiple LinkedLists. In this way a LinkedList behaves much more like a view than an independent collection. What I mean by this is my_list.rotate_right(10) isn't a new LinkedList really, it's just a different way of looking at my_link. Specifically, it's looking at my_list as if it started 11 elements in instead of where it's head currently is. I feel like the first approach doesn't make the copying obvious enough. You may want to avoid it entirely for something more explicit like requiring something like:

new_list = my_list.copy
new_list.rotate_right!(10)

If you prefer the second approach, I'd recommend making the Node's value immutable and severely limiting mutation on the lists. This is a space that functional programming languages have explored extensively. Mutation and multiple aliases often lead to disaster. It's best to pick one or the other.