Includes & Find

These are the last two methods I’ll probably write about in this linked list series. You know the drill by now, so here are the tests (I’m giving you all of them at once, apologies for the big code block)

describe 'find' do
  it "where to look and how many to return" do
    list = LinkedList.new
    list.append("a")
    list.append("b")
    list.append("c")
    list.append("d")
    list.append("e")
    expect(list.find(2, 1)).to eq("c")
  end
  
  it "can return multiple nodes" do
    list = LinkedList.new
    list.append("a")
    list.append("b")
    list.append("c")
    list.append("d")
    list.append("e")
    expect(list.find(1, 2)).to eq("b, c")
    expect(list.find(1, 3)).to eq("b, c, d")
  end
  it "returns nil if index doesn't exist" do
    list = LinkedList.new
    list.append("a")
    list.append("b")
    expect(list.find(5, 1)).to be_nil
  end

  it "returns nil if empty" do
    list = LinkedList.new
    expect(list.find(0, 1)).to be_nil
  end

  it "returns what you have if request is too high" do
    list = LinkedList.new
    list.append("a")
    list.append("b")
    list.append("c")
    expect(list.find(1, 5)).to eq("b, c")
  end

  it "returns empty string if return is 0" do
    list = LinkedList.new
    list.append("a")
    list.append("b")
    expect(list.find(1, 0)).to eq("")
  end

  it "returns nil for a negative number" do
    list = LinkedList.new
    list.append("a")
    list.append("b")
    expect(list.find(1, -1)).to be_nil
  end
end

describe 'includes' do
  it "gives true or false if the value is in the list" do
    list = LinkedList.new
    list.append("a")
    list.append("b")
    list.append("c")
    list.append("d")
    list.append("e")
    expect(list.includes?("a")).to be true
    expect(list.includes?("f")).to be false
  end
  it "returns false when the list is empty" do
    list = LinkedList.new
    expect(list.includes?("anything")).to be false
  end
end

Alright, so there are quite a few edge cases for find, so we will start there.

First, I want to take care of the empty list test

def find(start, how_many)
  return nil if head.nil?
end

And that should pass. Now I’m going to take care of negative numbers as well, using the and/or operator ||That will go in the same line, for the sake of space.

def find(start, how_many)
  return nil if head.nil? || how_many < 0
end

Now that that is out of the way, lets get into the main parts of this

I want a counter, to make sure that it can keep track of how many nodes are being returned, and I am going to use the node_at method from earlier to deal with the starting point.

def find(start, how_many)
  return nil if head.nil? || how_many < 0
  counter = 0
  new_string = []
  current_node = node_at(start)
  return current_node.data if how_many == 1
end

So counter is going to start at 0, we’re making an array of new_string to store what needs to be returned, and current_node is going to use node_at and the starting point to show it where to start. I also added in that if statement, in case we only need to return one piece of information. There is no point going through the next steps if just one piece of data is to be returned.

I want to make sure that the counter doesn’t become a larger number than how_many, so I am going to use that in a while loop to keep track of where I am. When the counter does become larger, that will be done.

It is going to shove the data from the current_node into the new_string array, and then reassign the variable to the next_node of the current_node it is on. Once that is done, it is going to add one to the counter, and go through the while loop again. Once the counter is no longer less than how_many, then it will skip that, take the new_string array, and join it, with a comma and space in between.

def find(start, how_many)
  return nil if head.nil? || how_many < 0
  counter = 0
  new_string = []
  current_node = node_at(start)
  return current_node.data if how_many == 1
  while counter < how_many
    new_string << current_node.data
    current_node = current_node.next_node
    counter += 1
  end
  new_string.join(", ")
end

Almost everything should work now, but I need to account for that last tests that aren’t passing. I can add a check to make sure the current_node is not nil, and that should take care of that. On the while loop, add this

while counter < how_many && current_node

If it has run out of nodes and current_node is nil, then it will leave the while loop.

And if the starting point is too big of a number and it has nowhere to start, add this conditional at the beginning, that utilizes the count method.

return nil if head.nil? || how_many < 0 || start > count

Includes is pretty straight forward. We’re going use the same thing to check if the head is nil. Then we will assign current_node to the head. If the current_node is not nil, then we’ll use this while loop. At any point, if the data in a node equals that which is passed in, it will return true. Otherwise it will reassign and keep searching. If it gets to the end and doesn’t find it, then it will return false

def includes?(data)
  return false if head.nil?
  current_node = head
  while current_node != nil
    return true if current_node.data == data
    current_node = current_node.next_node
  end
  false
end

I think that pretty much covers it. Next time I’ll post the entire thing together so you can see the layout, if you want.