Persistent list implemented in Ruby.

plist.rb

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