Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Persistent list implemented in Ruby.
require_relative "./linked_list.rb"
class LinkedList
# Reuses list nodes from the specified node
# to the end of the list.
# The complexity of this method is O(n) where n
# is the distance from the target node to the
# end of the list.
def reuse_from_node node
self.tail.next = node
# len from target node to the end.
len = 1
tmp = node
while tmp = tmp.next
len += 1
end
self.length += len
end
def insert data
node = PList::Node.new data
unless head
self.head = node
else
self.tail.next = node
end
self.tail = node
self.length += 1
end
end
class PList
class Node
attr_accessor :data
def initialize data
self.data = data
self.data.freeze
end
def next=(node)
@next = node
end
def next
@next
end
def to_s
self.data&.to_s || "nil"
end
end
# Creates an empty list.
# Complexity O(1).
def self.empty
list = LinkedList.new
list.freeze
end
# Inserts a new item into a copy of the
# specified list. The original list remains
# untouched.
# The complexity of this method is O(n).
def self.insert list, data
ret = self.copy list
ret.insert data
ret.freeze
end
# Updates an item from a copy of the specifed
# list and returns that copy. The original list
# remains untouched.
# The complexity of this method is O(n).
def self.update list, node, data
# copy until we get to the target node.
# reuse from node to end of list.
ret = LinkedList.new
reuse = false
found = false
list.each do |nd|
unless found
found = (nd.data == node.data)
if found
ret.insert(data)
reuse = true
next
end
end
unless reuse
ret.insert(data)
else
# Reuse nodes from target to tail.
ret.reuse_from_node(nd)
break
end
end
ret.freeze
end
# Removes an item from a copy of the specifed
# list and returns that copy. The original list
# remains untouched.
# The complexity of this method is O(n).
def self.remove list, node
ret = LinkedList.new
reuse = false
found = false
list.each do |nd|
unless found
found = (nd.data == node.data)
if found
reuse = true
next # skip the target node.
end
end
unless reuse
ret.insert(nd.data)
else
# Reuse nodes from target to tail.
ret.reuse_from_node(nd)
break
end
end
ret.freeze
end
# Concatenates two lists.
# Complexity: O(n) where n is the length of lhs.
def self.cat lhs, rhs
ret = self.copy lhs
ret.cat rhs
ret.freeze
end
# Returns the length of the specified list.
# Complexity: O(1).
def self.len list
list&.length || 0
end
# Finds first occurence of the given predicate.
# Complexity: O(n).
def self.find_first list, &predicate
return nil unless list
return list.find_first &predicate
end
# Loops over the specified list.
# Complexity: O(n).
def self.each list, &block
return nil unless list
list.each &block
end
# Prints the contents of the specified list.
# Complexity: O(n).
def self.print list
unless list
print "empty"
else
list.print
end
end
private
# This is the only method that mutates a list and it's not
# intended for external use.
def self.copy src
dst = LinkedList.new
src.each { |node| dst.insert node.data }
dst
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.