3
\$\begingroup\$

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?

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

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.