What is the best way to implement a linked list in Ruby without using/extending the Array class? This is an implementation that I've used in the past, but it doesn't seem like the best way to go about it:
class Node
attr_accessor :value, :next_node
def initialize(value = nil)
@value = value
end
def to_s
@value
end
end
class SinglyLinkedList
attr_accessor :head
def initialize(first_value=nil)
@head = Node.new(first_value) if first_value
end
def add(value)
#adds a new node to the list, amakes it the new head and links it to the former head
new_node = Node.new(value)
new_node.next_node = @head
@head = new_node
end
def remove
@head = @head.next_node
end
end
I assume you are implementing this for self-teaching, otherwise it doesn't makes any sense. Just use Array
, that is the list implementation for ruby.
In my opinion, you should write these exercises in C, because the whole point in implementing a linked list is to be closer to the machine and understand better how it works. C is a way better tool for this task, understand how computer works.
This is how a classical linked list is teach on college: O(n)
to insert, O(n)
to search, and O(n)
to delete. Afterwards, most books discuss about improvements on it.
I wrote in in the top of my head, and did no tests on it at all, but this should give you an idea, and hopefully an exercise to correct any bugs you found. (update: @Nitesh found a typo, and fixed it. Hopefully it have some test now).
class Node
attr_accessor :value, :next
def initialize(value = nil)
@value = value
end
def to_s
@value
end
end
class SinglyLinkedList
attr_accessor :head
def initialize(first_value=nil)
@head = Node.new(first_value) if first_value
end
def add(value)
if head.nil?
head = Node.new(value)
else
current_node = @head
while current_node.next
current_node = current_node.next
end
current_node.next = Node.new(value)
end
end
def find(value)
current_node = head
while current_node != nil
return current_node if current_node.value == value
current_node = current_node.next
end
nil
end
def remove(value)
if head.value == value
head = head.next
else
current_node = head.next
prev_node = head
while current_node
if current_node.value == value
prev_node.next = current_node.next
return true
end
prev_node = current_node
current_node = current_node.next
end
nil
end
end
end