2
\$\begingroup\$

I was working on Leet code design a Linked List problem. My solution with a @tail pointer, althought it added complexity it made adding to tail O(1), also having a variable size @size made it easier to counter edge cases. Here are some of the stats:

Success Details Runtime: 100 ms, faster than 84.62% of Ruby online submissions for Design Linked List. Memory Usage: 9.6 MB, less than 100.00% of Ruby online submissions for Design Linked List.

If there is any enhancements or feedback please share some. Could the Linked List be optimize? Are you able to understand how is design when reading the code? 

class MyLinkedList
    attr_accessor :head, :size, :tail
=begin
    Initialize your data structure here.
=end
    def initialize()
      @head = nil
      @size = 0
      @tail = nil
    end


=begin
    Get the value of the index-th node in the linked list. If the index is invalid, return -1.
    :type index: Integer
    :rtype: Integer
=end
    def get(index)
      return -1 if @head == nil
      return -1 if index > @size - 1
      return @head.val if index == 0
      return @tail.val if index == @size - 1

      i = @head
      j = 0

      while i != nil
        if j == index
          return i.val
        end
        i = i.next
        j += 1
      end
      -1
    end


=begin
    Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
    :type val: Integer
    :rtype: Void
=end
    def add_at_head(val)
      new_node = Node.new(val)
      new_node.next = @head
      @tail = new_node if @head == nil
      @head = new_node
      @size += 1
    end


=begin
    Append a node of value val to the last element of the linked list.
    :type val: Integer
    :rtype: Void
=end
    def add_at_tail(val)
      return add_at_head(val) if @head == nil
      node = Node.new(val)
      @tail.next = node
      @tail = node
      @size += 1
    end


=begin
    Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted.
    :type index: Integer
    :type val: Integer
    :rtype: Void
=end
    def add_at_index(index, val)
      return add_at_head(val) if index == 0
      return add_at_tail(val) if @head == @tail
      return add_at_tail(val) if @size == index
      return if index > @size

      i = @head
      j = 0

      while i != nil
        if j == index - 1
          tmp = i.next
          node = Node.new(val)
          i.next = node
          node.next = tmp
          @size += 1
          return
        end
        i = i.next
        j += 1
      end

    end


=begin
    Delete the index-th node in the linked list, if the index is valid.
    :type index: Integer
    :rtype: Void
=end
    def delete_at_index(index)
      return if index < 0 || index > @size - 1
      return delete_at_head if index == 0
      return delete_at_tail if index == @size - 1

      i = @head
      j = 0

      while i != nil
        if j == index - 1
         i.next = i.next.next
         @size -= 1
         return
        end
        i = i.next
        j += 1
      end

    end

    def delete_at_head
      if @head == nil
        return nil
      elsif @head == @tail #one element in the linked list
        @head = nil
        @tail = nil
        @size -= 1
        return
      else
        @head = @head.next
        @size -= 1
      end
    end

    def delete_at_tail
      if @head == nil
        return nil
      elsif @head == @tail
        return delete_at_head
      end

      current = @head
      prev = nil

      while(current != tail)
        prev = current
        current = current.next
      end
      prev.next = nil
      @tail = prev
      @size -= 1
      return
    end

    private

    class Node
        attr_accessor :val, :next
        def initialize(val)
            @val = val
            @next = nil
        end
    end
end
\$\endgroup\$

1 Answer 1

Reset to default
1
\$\begingroup\$

My solution with a @tail pointer, althought it added complexity it made adding to tail O(1), also having a variable size @size made it easier to counter edge cases.

Having a tail pointer and a size variable makes totally sense.

Could the Linked List be optimize?

I don't think you can improve performance much here, you already cover most / all of the corner cases. Well done to implement add_at_index with one iteration.

Are you able to understand how is design when reading the code?

Here are some suggestions to make the code more readable

Extract helper methods

In your code you do several times if @head == nil to check if the list is empty. What about extracting an empty? method?

def empty?
  head.nil?
end

Same goes for instance with increasing the size.

  def increase_size
    @size += 1
  end

Use getter / setter methods

You already define getter and setter methods in your class but then fail to use them.

attr_accessor :head, :size, :tail

Instead of doing @head you should use head etc. Another problem is that the getter / setter are public, move them to the private section of the class. There is no need that consumer of this class know about these implementation details.

Implement the Enumerable interface

At several places in your code you need to iterate over your list with a while loop. If you implement the Enumerable interface of Ruby, you only need to do this once.

class MyLinkedList
  include Enumerable

  def initialize
    @head = nil
    @size = 0
    @tail = nil
  end

  def each
    current = head
    until current.nil?
      yield current
      current = current.next
    end
  end

  def [](index)
    each_with_index do |item, i|
      return item.val if i == index
    end
  end

https://ruby-doc.org/core-2.7.1/Enumerable.html

Use Ruby method names

You probably use the method stubs provided from LeetCode but I think it's still worth mentioning. Whenever possible you should use similar methods as already in the Ruby standard library. If we look at the Array class, we see for instance these methods.

def [](index) # get(index)
def unshift(value) # add_at_head(val)
def <<(value) # add_at_tail(val)
def append(value) # add_at_tail(val)
def [](index, value) # def add_at_index(index, val)
def shift # delete_at_head
def pop # delete_at_tail

Summary

Here are some of my suggestions applied

class MyLinkedList
  include Enumerable

  def initialize
    @head = nil
    @size = 0
    @tail = nil
  end

  def [](index)
    return if empty?
    return if index > size - 1
    return head.val if index.zero?
    return tail.val if index == size - 1

    each_with_index do |item, i|
      return item.val if i == index
    end
  end

  def unshift(value)
    node = Node.new(value)
    node.next = head

    @tail = node if empty?
    @head = node
    increase_size

    value
  end

  def <<(value)
    return unshift(value) if empty?

    node = Node.new(value)
    tail.next = node
    @tail = node
    increase_size

    value
  end

  def []=(index, value)
    return add_at_head(value) if index == 0
    return add_at_tail(value) if head == tail
    return add_at_tail(value) if size == index
    return if index > size

    each_with_index do |item, i|
      insert_node(item, value) if i == index - 1
    end
  end

  def each
    current = head
    until current.nil?
      yield current
      current = current.next
    end
  end

  private

  attr_accessor :head, :size, :tail

  def insert_node(item, value)
    tmp = item.next
    node = Node.new(value)
    item.next = node
    node.next = tmp
    increase_size
  end

  def empty?
    @head.nil?
  end

  def increase_size
    @size += 1
  end

  class Node
    attr_accessor :val, :next

    def initialize(val)
      @val = val
      @next = nil
    end
  end
end
\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.