Linked List – Append

Now for the fun stuff. We will figure out how to write a method to add something to the list. I learned this method is called append, but I’ve seen several other names. But, I’ll stick with append. First, in the spirit of TDD, we will write a test. It will be the head if something gets appended to an empty list. So, we will need to pass the data in and ensure it goes to the head of the list. Because only one thing gets appended at first, next_node will equal nil.

  describe 'append' do
    it 'can append one thing' do
      list = LinkedList.new
      list.append("A")
      expect(list.head.data).to eq("A")
      expect(list.head.next_node).to eq(nil)
    end

When you run this, you’re going to get the familiar undefined method 'append' error. That means it is time to make a method. We’re going to start with just enough to make the test pass, and then go from there. Technically, this is all you need to make it pass.

  def append(data)
      @head = Node.new(data)
  end

Cool, that passes. Next up, what happens if you append a second thing to the list? The next test will append multiple nodes.

    it 'can append more than one' do
      list = LinkedList.new
      list.append("A")
      expect(list.head.data).to eq("A")
      expect(list.head.next_node).to eq(nil)
      list.append("B")
      expect(list.head.next_node.data).to eq("B")
    end

This is going to start with an empty list, add "A" as the data to the head, then add "B" as the data for the next_node. I’m probably going to need a count method later to figure out how long the list is, but we can worry about that after this works.

The way it stands, this is going to overwrite the head, so the head will briefly be "A", and then be overwritten to be "B". So the test fails, and that needs to be solved. This is where the empty? method from earlier may come in handy.

  def append(data)
    if empty?
      @head = Node.new(data)
    end
  end

This will keep it from being overwritten, but it won’t add the second node. We’re going to need to add an else statement, and here is where it gets a little tricky. If it is, in fact, not empty, then we need to assign the head to a variable so something can be added to the head.

def append(data)
    if empty?
      @head = Node.new(data)
    else
      current_node = head
    end
  end

That’s not enough to get the test to pass, but it does assign the head somewhere. Next, add the new node to be the next_node of the head

def append(data)
    if empty?
      @head = Node.new(data)
    else
      current_node = head
      current_node.next_node = Node.new(data)
    end
  end

To make this work, you need to go back to the node class and add an attr_writer, so that next_node can be changed. It should look like this

class Node
  attr_reader :data, :next_node
  attr_writer :next_node
  def initialize(data)
    @data = data
    @next_node = nil
  end
end

And now that test should pass.
One more test, so you can add even more. In the previous test and method, it doesn’t test for what happens if there is something in the next node. Here is the test, just adding another append.

    it 'can append three' do
      list = LinkedList.new
      list.append("A")
      expect(list.head.data).to eq("A")
      expect(list.head.next_node).to eq(nil)
      list.append("B")
      expect(list.head.next_node.data).to eq("B")
      list.append("C")
      expect(list.head.next_node.next_node.data).to eq("C")
    end

The expect on that last one is kind of long, but I want you to see how they’re linked. So now we need to solve that problem, and we will use while to do it. I’m going to add this to the method

while current_node.next_node != nil
        current_node = current_node.next_node
      end

This is saying that if the next_node is NOT nil, then reassign the variable current_node to what was previously the next_node of the current_node, and so on and so forth until the next_node is nil. Here is the final method.

def append(data)
    if empty?
      @head = Node.new(data)
    else
      current_node = head
      while current_node.next_node != nil
        current_node = current_node.next_node
      end
      current_node.next_node = Node.new(data)
    end
  end

And everything should pass.