Time complexity for size call on a linked list in ruby

Question

I'm a newbie to ruby. Pardon me for asking such a simple question.

While I know that Ruby doesn’t include a LinkedList class so we need to create our own, therefore I created my own class as shown below:

class Node
    attr_accessor :data, :next
    def initialize(data, next_node = nil)   
        @data = data
        @next = next_node
    end
end

class Linkedlist

    def empty?
        @head == nil  
    end

    def size
        count = 0
        if self.empty?
            return count
        else
            current_node = @head
            while current_node.next !=nil
                count += 1
                current_node = current_node.next
            end
            return count
        end
    end
        
    ...
    ...

    def add
        if self.empty?
            @head = Node.new(data)
        else
            while current_node.next != nil
                current_node = current_node.next
            end
            current_node.next = Node.new(data)
        end
    end
end

My implementation for size call clearly shows a time complexity of O(n). while looking at the Java implementation in this answer, it seems Java keeps a track of size of the linked list such that time complexity for size call is O(1).

How do I make this possible using ruby?

Answer 1

Add attr_accessor :size to your Class Linkedlist and manipulate size in your add method like below:

class Linkedlist
    attr_accessor :size

    def add
        if self.empty?
            @head = Node.new(data)
        else
            while current_node.next != nil
                current_node = current_node.next
            end
            current_node.next = Node.new(data)
        end
        modify_size("add")
    end

    def remove
        .
        . 
        # after removing node
        modify_size("remove")
        return removed_node
    end

    def modify_size(arg)
        case arg
        when 'add'
            self.size += 1
        when 'remove'
            self.size -= 1
        else
        end
    end

end

l1 = Linkedlist.new.add(1)
puts l1.size