# Linked List implementation in Ruby

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
=begin
=end
def initialize()
@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

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
new_node = Node.new(val)
@tail = new_node if @head == nil
@size += 1
end

=begin
Append a node of value val to the last element of the linked list.
:type val: Integer
:rtype: Void
=end
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
return add_at_tail(val) if @size == index
return if index > @size

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

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

return nil
@tail = nil
@size -= 1
return
else
@size -= 1
end
end

def delete_at_tail
return nil
end

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


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?
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
@size = 0
@tail = nil
end

def each
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 [](index, value) # def add_at_index(index, val)
def pop # delete_at_tail


## Summary

Here are some of my suggestions applied

class MyLinkedList
include Enumerable

def initialize
@size = 0
@tail = nil
end

def [](index)
return if empty?
return if index > size - 1
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)

@tail = node if empty?
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_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
until current.nil?
yield current
current = current.next
end
end

private

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

def empty?
end

def increase_size
@size += 1
end

class Node
attr_accessor :val, :next

def initialize(val)
@val = val
@next = nil
end
end
end