current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 4 down vote favorite

The #traverse_until method is a helper function that traverses the linked list and returns the node and index of the node once a condition (in a block) is met or until the end of the list. I would greatly appreciate feedback about verbosity, efficiency, readability, etc. 

module DataStructures
  class Node
    attr_accessor :value, :next_node

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

  class LinkedList
    attr_accessor :head

    def initialize(element = nil)
      element.nil? ? @head = nil : @head = Node.new(element)
    end

    def append(data)
      prepend(data) if @head.nil?
      current = @head
      until current.next_node.nil?
        current = current.next_node
      end
      current.next_node = Node.new(data)
    end

    def prepend(data)
      @head = Node.new(data, @head)
    end

    def find(data)
      result = traverse_until { |node, index| node.value == data }
      result[:node].value == data ? result[:index] : "Data not found."
    end

    def contains? (data)
      result = traverse_until { |node, index| node.value == data }
      result[:node].value == data
    end

    def node_at_index(index)
      result = traverse_until { |node, i| i == index }
      "Node at index #{index}: #{result[:node].value}"
    end

    def head
      @head.nil? ? "Empty list" : @head.value
    end

    def tail
      last_node = traverse_until { |node, index| node.next_node.nil? }
      last_node[:node].value
    end

    def size
      last_node = traverse_until { |node, index| node.next_node.nil? }
      "List Size: #{last_node[:index] + 1}"
    end

    def insert_at(data, index)
      current = @head

      (index - 1).times do |n|
        current = current.next_node
      end

      node_shifted_right = current.next_node
      current.next_node = Node.new(data, node_shifted_right)
    end

    def remove_at(index)
      node_after_index = @head
      previous = node_after_index
      (index + 1).times do |n|
        node_after_index = node_after_index.next_node
      end

      (index - 1).times do |n|
        previous = previous.next_node
      end

      previous.next_node = node_after_index
    end

    def pop
      node_before = nil
      current = @head
      until current.next_node.nil?
        node_before = current
        current = current.next_node
      end
      node_before.next_node = nil
    end

    def to_s
      result = ""
      current = @head
      loop do
        result += "(#{current.value}) -> "
        break if current.next_node.nil?
        current = current.next_node
      end
      result += "nil"
    end

    private

    def traverse_until
      current = @head
      index = 0
      until current.next_node.nil? || yield(current, index)
        current = current.next_node
        index += 1
      end
      {node: current, index: index}
    end
  end
end
share|improve this question
up vote 3 down vote accepted

Firstly, your code's broken. If you instantiate a list with no initial value, and then append to it, it creates two nodes:

list = LinkedList.new
list.append("foo")
list.size #=> "List size: 2"

Secondly, implement an #each method to iterate through values and include Enumerable. That'll give a ton of methods for free: #find, #count, #to_a, and many others. Something like this should do:

def each
  node = @head
  until node.nil?
    yield node.value
    node = node.next_node
  end
end

Thirdly, return useful values. #size should not return a string. Neither should #head, #node_at_index, or #find. #size should return an int, and the others should return nil. Never ever return easy-to-print strings unless that's explicitly called for. Currently, you can get puzzling stuff like this (both return values are accurate):

some_list.head #=> "Empty list"
some_list.size #=> "List size: 2"

And you can get useless stuff like this:

if some_array.count < some_list.size # ArgumentError: comparison of Fixnum with String failed
  ...

I trust you see the problem here.

Speaking of return values, you seem to have taken some care that you methods don't return a raw Node instance (which is smart, since nodes are internal/private to the linked-list)... but you made @head accessible from anywhere with attr_accessor. So some_list.head = "foo" is perfectly legal, and will break things. Also, #append and #prepend implicitly return Node instances.

Fourth, you might want to keep track of the tail as well as the head. Many of your methods rely on finding the tail one way of another, so why not keep it around? Or at least use your own #tail method for these cases, rather than do it different each time.

Other stuff:

  • Check the indices passed to #insert_at and #remove_at and raise an appropriate error if the index is out-of-bounds. Otherwise you'll just get a NoMethodError which doesn't explain much.

  • Don't put assignments into ternary branches; use the branch to determine the value to assign. I.e. this

    element.nil? ? @head = nil : @head = Node.new(element)

    should be

    @head = element.nil? ? nil : Node.new(element)

    of course, in this particular case, @head will be nil by default, do you could just as well do:

    @head = Node.new(element) unless element.nil?

  • Your #to_s would be a lot cleaner if you collected all the values in an array, used map to add parentheses, and join to add the "->" arrows. If you include Enumerable as described above, your #to_s could just be:

    def to_s
  values = map { |value| "(#{value})" }
  values << "nil"
  values.join(" -> ")
end
share|improve this answer
    
Thank you, based on my code sample above, what would be a rough estimate of the gap between my current skill level and the level of skill expected of an entry level junior developer? I know I still have a while to go, but I am just looking for a metric of some sort. Again, thank you. – Adrian DeRose Jan 16 at 6:52
1  
@AdrianDeRose That depends; different places have different ideas of "entry level/junior dev". Yes, you have some way to go, but you're def on your way. But I'd encourage you work on actual projects, like a gem or something. Find something to contribute to or build a Rails site, etc.. Implementing a linked list in Ruby is a somewhat pointless exercise; just use Array. Or get a gem for it instead of reinventing the wheel. Code challenges are like crosswords: Solving them won't make you a writer; writing will. Also, read more Ruby code; dig around in popular, proven code and learn from it – Flambino Jan 16 at 9:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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