Last active
June 27, 2021 15:20
-
-
Save t0yohei/0587827ec14bb773693169ebb85511f4 to your computer and use it in GitHub Desktop.
Singly Linked List with ruby
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Node | |
def initialize(value, next_node = nil) | |
@value = value | |
@next_node = next_node | |
end | |
attr_reader :value | |
attr_accessor :next_node | |
end | |
class LinkedList | |
def initialize | |
@first_node = nil | |
end | |
attr_accessor :first_node | |
def add(value) | |
if @first_node | |
find_last_node.next_node = Node.new(value) | |
else | |
@first_node = Node.new(value) | |
end | |
end | |
def add_with_index(index, value) | |
prev_node = get(index - 1) | |
return if !prev_node | |
new_node = Node.new(value) | |
new_node.next_node = prev_node.next_node | |
prev_node.next_node = new_node | |
end | |
def delete(index) | |
target_node = get(index) | |
return if !target_node | |
if target_node == @first_node | |
@first_node = target_node.next_node | |
return | |
end | |
prev_node = get(index - 1) | |
prev_node.next_node = target_node.next_node | |
end | |
def get(index) | |
node = @first_node | |
return node if index == 0 | |
counter = 0 | |
while counter < index | |
if !node.next_node | |
return nil | |
else | |
node = node.next_node | |
end | |
counter += 1 | |
end | |
return node | |
end | |
private | |
def find_last_node | |
node = @first_node | |
return node if !node.next_node | |
while node.next_node | |
node = node.next_node | |
end | |
return node | |
end | |
end | |
# test code | |
linked_list = LinkedList.new | |
linked_list.add(10) | |
linked_list.add(20) | |
linked_list.add(30) | |
linked_list.add_with_index(1, 15) | |
linked_list.add_with_index(3, 25) | |
linked_list.delete(2) | |
# p linked_list #=> #<LinkedList:0x00007f9fe6090a78 @first_node=#<Node:0x00007f9fe6090a28 @value=10, @next_node=#<Node:0x00007f9fe60908e8 @value=15, @next_node=#<Node:0x00007f9fe6090898 @value=25, @next_node=#<Node:0x00007f9fe6090960 @value=30, @next_node=nil>>>>> | |
# Comparison with array | |
require 'benchmark' | |
# insert | |
Benchmark.bm 30 do |r| | |
arr = Array.new | |
r.report "insert Array(ArrayList)" do | |
(1..10000).each do |num| | |
arr.insert(0, num) | |
end | |
end | |
linked_list = LinkedList.new | |
r.report "insert LinkedList" do | |
(1..10000).each do |num| | |
linked_list.add_with_index(0, num) | |
end | |
end | |
end | |
# delete | |
Benchmark.bm 30 do |r| | |
arr = (1..10000).to_a | |
r.report "delete Array(ArrayList)" do | |
(2..1000).each do |num| | |
arr.delete_at(num) | |
end | |
end | |
linked_list = LinkedList.new | |
(1..10000).each { |num| linked_list.add(num) } | |
r.report "delete LinkedList" do | |
(2..1000).each do |num| | |
linked_list.delete(num) | |
end | |
end | |
end | |
# find | |
Benchmark.bm 30 do |r| | |
arr = (1..10000).to_a | |
r.report "find Array(ArrayList)" do | |
arr = Array.new | |
(1..1000).each do |num| | |
arr.index(num) | |
end | |
end | |
linked_list = LinkedList.new | |
(1..10000).each { |num| linked_list.add(num) } | |
r.report "find LinkedList" do | |
(1..1000).each do |num| | |
linked_list.get(num) | |
end | |
end | |
end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Below is the result of benchmarks. The benchmark of
delete LinkedList
could be improved if we use Doubly Linked List.