Count a Linked List

Next up, figuring out how to count the linked list. This is going to return how many nodes there are. If there is just a head, the count will be 1. If there is a head + node + node + tail (the end), the count will be 4.

This is a straightforward method, so it won’t be long.

Start with a simple test, just to make sure that it can, in fact, be counted

#spec/linked_list_spec.rb

RSpec.describe LinkedList do
  it 'can be counted' do
    list = LinkedList.new
    list.append("A")
    expect(list.count).to eq(1)
  end
end

This is a pretty straightforward test; you’re just appending and counting one thing. And if you run the test, it will be pointed out that we haven’t made this method yet. Off to linked_list.rb

  def count
    count = 1
  end

Step one is setting up a counter. Actually, step one should return 0 if empty? But I will add that after writing a test for it.

Technically, the count = 1 is all you need to pass that test, so we should probably make a more robust test.

it 'can count to 3' do
  list = LinkedList.new
  list.append("A")
  list.append("B")
  list.append("C")
  expect(list.count).to eq(3)
end

And this one fails. Next, assign what needs to be counted. First, you’ll need a starting point.

  def count
    count = 1
    current_node = head
  end

This will temporarily assign the head to the variable current_node, which we’ll be counting. If the next_node of current_node is NOT nil, it will be added to the counter. I used a while statement. So if next_node isn’t nil, the next node becomes the current node, and 1 gets added to the count. Eventually, next_node will be nil, and it will stop counting.

  def count
    count = 1
    current_node = head
      while current_node.next_node != nil
        current_node = current_node.next_node
        count += 1
      end
    count
  end

Add count at the end to ensure that the total gets returned. If you don’t, it won’t pass. This tripped me up frequently when I started at Turing. This should pass the test. As mentioned earlier, you should probably add something to ensure 0 gets returned if the list is empty. So, one more test.

it 'returns 0 if count is 0' do
   list = LinkedList.new
   expect(list.count).to eq(0)
end

If you run this, you should get an error about next_node being an undefined method for nil. One line to the method should resolve it.

def count
  return 0 if empty?
  count = 1
  current_node = head
    while current_node.next_node != nil
      current_node = current_node.next_node
      count += 1
    end
  count
end

And the tests are all passing.