Let's make a Linked List in Ruby

Tutorial: How to Create A Linked List In Ruby

The linked list is one of the simplest data structures in computer science. Let's code one in Ruby! We'll be working off of a fun project from the Turing School of Software Design curriculum (my code school alma mater). This little dandy is given to students in their first week of programming. Into the fire!

Step 1: The Node

The building block of a linked list is a node. The node will be quite simple – a Node needs to have a slot for some data and a slot for a “next node.” Eventually this next_node position will be what we use to link the multiple nodes together to form the list.

Let's start by implementing the following behavior:

> require "./lib/node"
> node = Node.new("Burke")
=> <Node @surname="Burke" @next_node=nil #5678904567890>
> node.surname
=> "Burke"
> node.next_node
=> nil

In the above example we want to be able to instantiate a new node that will store a surname as our example data. At first, calling next_node should return nil because the node has no child node.

Time to make some folders and files to house our projcet:

In the above screenshot, I have a project directory called 'perilous_journey' containing two subfolders - /lib and /test. In lib I create a node.rb file and then in test I create a node_test.rb file. 

Next we'll write a test.

# perilous_journy/test/node_test.rb
require 'minitest/autorun'
require 'minitest/pride'
require './lib/node.rb'

class NodeTest < Minitest::Test
  def test_new_returns_a_node
    subject = Node.new('Burke')
    assert_instance_of Node, subject
  end
end

Here we use minitest to assert that when we call Node.new and pass in the parameter 'Burke' we should get a new instance of a node. Running this test by typing 'ruby test/node_test.rb' will return:

The error says that we have an uninitialized constant, so let's create it!

# perilous_journy/lib/node.rb
class Node
end

And next we'll run our test.

Screen Shot 2018-02-02 at 9.07.18 PM.png

We are still getting an error, but it's an ArgumentError. In our test we are passing in a surname, which now we need to account for in our implementation. When we add the following initialization method our test should pass.

# perilous_journy/lib/node.rb
class Node
  def initialize(surname)
  end
end

Next we'll add a new test right under our first test. In this new test we'll assert that when we call the method 'surname' on our node instance, it should return the name that it was initialized with.

def test_surname_returns_name
  subject = Node.new('Burke')
  assert_equal 'Burke', subject.surname
end

When we run this test we get an undefined method error because we have not defined the surname method yet.

We can add this method by first creating an instance variable called surname in our initialization method and setting it equal to the surname string passed in as a parameter. Next we will add an attribute reader so that we can call this attribute as if it was a method. For more on attribute readers, I recommend this helpful stackoverflow post. After implementing the code below, our test will pass.

# perilous_journy/lib/node.rb
class Node
  attr_reader :surname

  def initialize(surname)
    @surname = surname
  end
end

Next we will write a test asserting that our node is initialized with an empty next node.

def test_next_node_returns_nil
  subject = Node.new('Burke')
  assert_nil subject.next_node
end

Running our test will give us another undefined method error because we have not yet implemented a next_node method.

To fix this error, we'll add another attribute reader, following the same pattern we used for the surname. Running our tests against the code below and we should have a passing test suite.

# perilous_journy/lib/node.rb
class Node
  attr_reader :surname,
              :next_node

  def initialize(surname)
    @surname = surname
    @next_node = nil
  end
end

Step 2: The LInked List

Now that we have a simple node class, we now want to create a linked list with the following behaviors:

  • head - the ability to examine the first node in our linked list
  • append - the ability to add new nodes to our list
  • to_string - the ability to convert our node data into a string
> require "./lib/linked_list"
> list = LinkedList.new
=> <LinkedList @head=nil #45678904567>
> list.head
=> nil
> list.append("West")
=> <Node @surname="West" @next_node=nil #5678904567890>
> list
=> <LinkedList @head=<Node @surname="West" ... > #45678904567>
> list.head.next_node
=> nil
> list.count
=> 1
> list.to_string
=> "The West family"

Let's create two new files to house our new test and linked list class.

We will create a test for new and a test for head.

# perilous_journy/test/linked_list_test.rb
require 'minitest/autorun'
require 'minitest/pride'
require './lib/linked_list.rb'

class LinkedListTest < Minitest::Test
  def test_new_returns_a_linked_list
    subject = LinkedList.new
    assert_instance_of LinkedList, subject
  end

  def test_head_returns_nil_when_first_initialized
    subject = LinkedList.new
    assert_nil subject.head
  end
end

Running these two tests will give us an uninitialized constant error.

We can define our linked list following a similar pattern used by our node. The linked list initialization method will not take any parameters, but it will initialize an @head instance variable with the value nil. Implementing the following code should pass our two latest tests.

# perilous_journy/lib/linked_list.rb
require './lib/node'

class LinkedList
  attr_reader :head
  def initialize
    @head = nil
  end
end

Now let's write a test that we can append new nodes to our linked list. we want to assert that the append method returns a node with the surname that we give as a parameter to append. We also want to assert that the new node has been stored in the head of our linked list.

def test_append_adds_new_node_to_end_of_list
  subject = LinkedList.new

  result = subject.append('West')

  assert_instance_of Node, result
  assert_equal 'West', result.surname
  assert_equal result, subject.head
end

When we run this test we'll get an undefined method error because we have not yet implemented an append method.

To fix this, we will define an append method that takes in a string name parameter, creates a new node and stores it in our linked list's head. We will change our attr_reader to an attr_accessor (see above stackoverflow link for additional information) so that we can read and write to the @head instance variable. Running the following code will pass our latest test. Notice that we have to use self.head for the attr_accessor to write correctly. In this case, self refers to the instance of the linked list.

# perilous_journy/lib/linked_list.rb
require './lib/node'

class LinkedList
  attr_accessor :head

  def initialize
    @head = nil
  end

  def append(surname)
    self.head = Node.new(surname)
  end
end

Now it is time to write a test for what will be our count method. The count method should return 0 when there is an empty list, and 1 when there is a node in the head of our list.

def test_count_returns_zero_for_empty_list
  subject = LinkedList.new
  assert_equal 0, subject.count
end

def test_count_returns_one_for_list_with_one_node
  subject = LinkedList.new
  subject.append('West')

  assert_equal 1, subject.count
end

Running these two new tests will give as an undefined method error for each test.

For the purpose of developing in small bite sized chunks - which I think is one of the most important skills for new developers, let's take these tests as literally as possible and avoid jumping into implementing a while loop or recursion for just a few more steps.

def count
  if head.nil?
    0
  else
    1
  end
end

The above method will pass the tests that we've written so far, but is not a true count implementation. We'll get there!

For now, let's just pound out a simple to_string method that will take the data in our linked list and concatenate it into a string.

First our test will assert that when we call to_string on our list, we will get a full sentence response.

def test_to_string_returns_correct_sentence_when_one_node_present
  subject = LinkedList.new
  subject.append('West')

  result = subject.to_string

  assert_equal 'The West family', result
end

Running this test will give us an undefined method error so it is now time to implement our to_string method.

Taking the most literal approach to passing this test, we can get away with something like:

def to_string
  "The #{head.surname} family"
end

The purpose for these simple implementations is just to take bite sized chunks out of our link list challenge at a time. Next we'll move into some tougher ground. For now let's celebrate how far we have come by opening a pry session in terminal and flex our linked list implementation.

Screen Shot 2018-02-02 at 10.22.57 PM.png

Step 3: Multiple Nodes

Our linked list is not doing much good for us because at this point it can only store one node. Time to remedy that! Let's first test that we can append multiple nodes to our list.

def test_append_two_nodes
  subject = LinkedList.new
  subject.append('Rhodes')
  subject.append('Hardy')

  result = subject.head.next_node.surname

  assert_equal 'Hardy', result
end

Running this test we get undefined method surname, which is odd because our node has a surname and we have a test to prove it. Let's use a binding.pry right after our second append and before our result in our test so that we can pause our test run and see what is happening. Before running our test let's remember to add require 'pry' at the top of our test file.

def test_append_two_nodes
  subject = LinkedList.new
  subject.append('Rhodes')
  subject.append('Hardy')
  binding.pry
  result = subject.head.next_node.surname

  assert_equal 'Hardy', result
end

When we run our test it will pause and give us the power to step through the code like so:

As we can see, the second append call completely over wrote the first append rather than actually adding the 'Hardy' node as the next node on the original 'Rhodes' node.

Let's take a quick detour back to our node class. We are going to want to add tests and implementation for two behaviors that will help us get our linked list append method just right.

We want the node to be able to report back to the list if it is the tail of the list. In other words, if the node does not have a next node, it is at the end of the list. At issue here is the notion of encapsulation and separation of concerns. Rather than reaching into the Node to determine if the next node is nil, our linked list will just nicely ask the node, 'Hey, Node, are you the tail?'

We also want to make sure that we can set the next_node to be a new node.

Let's write some tests (this is back in the node_test.rb file).

def test_tail_returns_true_if_next_node_is_nil
  subject = Node.new('Burke')
  assert_equal subject.tail?, true
end

def test_next_node_can_change_node_state
  subject = Node.new('Burke')
  data = 'pants'

  subject.next_node = data
  result = subject.next_node

  assert_equal data, result
end

In the above code we assert that when we call tail? on a node that has no next node it should return true. Next we test that we can set our node's next_node to be some type of data. I used the word 'pants' to signify that this variable's data does not actually matter. The use of the word pants originates from a Justin Searls conference talk. Typically the next_node would be set to be an actual node and not the string 'pants', but for the purpose of unit testing the node object it seems unnecessary to actually create a second node.

To get these tests to pass, we can make two changes to our code. First we need to move next_node from our attr_reader to an attr_accessor. This will allow us to both get and set the next node.

Next we need to define our tail? method. Implementing the following code will pass the latest two node tests.

# perilous_journy/lib/node.rb
class Node
  attr_reader :surname
  attr_accessor :next_node

  def initialize(surname)
    @surname = surname
    @next_node = nil
  end

  def tail?
    next_node.nil?
  end
end

Now, back at our linked list it is time to append new nodes properly. In order to append, we are going to need our linked list to be able to quickly get us the last node in a list. Let's write a test for this behavior:

def test_last_node_returns_the_tail
  subject = LinkedList.new
  subject.append('Rhodes')

  result = subject.last_node(subject.head)

  assert_instance_of Node, result
  assert_equal 'Rhodes', result.surname
end

Currently our append can handle adding one node to our list. So whatever node we last append should be returned by the last_node. I also want to make this method a bit more flexible for down the road. As a result, this method will take an argument of a starting node. Typically we'll start at the head, but as we go on to implement recursion, the starting node will recurse over the entire linked list of nodes.

In our linked list class let's add the following implementation.

def last_node(node)
  return node if node.tail?
  last_node(node.next_node)
end

The first line says return the node passed in as the node argument if this node is the tail node. Here we leverage the method we just added to the node class. If node.tail? is true, then by definition that node must be the last node.

Now, here's the recursive part. If the node we are starting at is not the tail of the linked list we move to the next line in which we call the method we are currently in (last_node) and pass it the argument of node.next_node.

In your mind's eye try to imagine the next step. We have the second node in our linked list (node.next_node) as the input for our last_node method call. If this node is the tail, our method will return it up the call stack and our original call of last_node will return the node that responds true to node.tail? 

Our last_node test should be passing with the above code, but our append two test is broken.

Before we jump back into append, we are going to want another helper method. In the case that our list is empty, we'll just use the implementation that we currently have in append. To do so, let's write a test that will assert that when we call .empty? on an empty linked list, we get true. The same method should return false if the linked list has one or more nodes.

def test_empty_returns_true_when_head_is_nil
  subject = LinkedList.new
  assert_equal true, subject.empty?
end

def test_empty_returns_false_when_head_is_not_nil
  subject = LinkedList.new
  subject.append('Rhodes')

  assert_equal false, subject.empty?
end

The implementation to get these two tests to pass is just to check whether or not the @head instance variable is nil. The following code will pass both of these tests:

def empty?
  head.nil?
end

Now we have what we need to go back into our append method. For these types of problems, I think it is helpful to try to say in words exactly what we want to have happen. Pseudocoding is also useful. 

  • Create a new node with the input string - list.append('Rhodes')
  • Check if the linked list is empty
  • If it is empty, assign the new node to the head of the list
  • If it is not empty, find the last_node in the list
  • Assign the last_node's next node to be our new node
def append(surname)
  node = Node.new(surname)
  if empty?
    self.head = node
  else
    last_node(head).next_node = node
  end
end

The above implementation gets our tests all passing. Now let's clean it up just a smidge. There are really two things going on in this method - the creation of a new node and then adding it to the linked list. We should strive to write methods that do one thing, so let's pull the node creation functionality out into its own first class method. First a test:

def test_new_node_returns_a_new_node
  subject = LinkedList.new

  result = subject.new_node('Rhodes')

  assert_instance_of Node, result
  assert_equal 'Rhodes', result.surname
end

Running this test get's us an undefined method error, so let's implement a method that will return a new node for us.

def new_node(surname)
  Node.new(surname)
end

Now we can refactor our append method to look something like this:

def append(surname)
  if empty?
    self.head = new_node(surname)
  else
    last_node(head).next_node = new_node(surname)
  end
end

There is still a little bit we could DRY up in the above method. Let's extract setting the head and tail, the two branches of our conditional, into their own private methods. Private methods are used internally on the instance, and are tested indirectly already so we do not need to write an additional test for either of these two methods.

private

  def set_head(surname)
    self.head = new_node(surname)
  end

  def set_tail(surname)
    last_node(head).next_node = new_node(surname)
  end
en

Using these private methods, we now can refactor append to look like this:

def append(surname)
  if empty?
    set_head(surname)
  else
    set_tail(surname)
  end
end

And because I'm a fan of one line methods, let's use a ternary statement to short the above code to:

def append(surname)
  empty? ? set_head(surname) : set_tail(surname)
end

Glorious. And just for our own personal edification, we'll write a test to confirm that our append method can append three nodes, which will pass without any additional implementation.

def test_append_three_nodes
  subject = LinkedList.new
  subject.append('Rhodes')
  subject.append('Hardy')
  subject.append('Smith')

  result = subject.head.next_node.next_node.surname

  assert_equal 'Smith', result
end

Step 4: Count For Real

Let's return to our count method and now get it working such that it actually counts each node. To do so we can set up a linked list just like we did in the most recently added test and assert that our count should equal three. This test will fail because our current implementation should only return a 1. Here's that current implementation:

def count
  if head.nil?
    0
  else
    1
  end
end

And here's the test to break it:

def test_count_three_nodes
  subject = LinkedList.new
  subject.append('Rhodes')
  subject.append('Hardy')
  subject.append('Smith')

  result = subject.count

  assert_equal 3, result
end

Similar to our append method we are going to need the additional help of a count method that we can call recursively. Since this method will only be called inside of our count method we can make it private. I have in mind a method that takes in a counter and a node. The counter is an integer to keep track of how many nodes we've counted. The node is the current node to count.

def count_node(node, counter)
  return counter if node.tail?
  count_node(node.next_node, counter += 1)
end

If the node is the tail of our list, return the counter. Otherwise, call count node, but pass in the next node and increment the counter. So if we start at the head and give the counter a 1 to start from (because if the node is not empty, there is at least one node) and discover that the head is also the tail of our list, this method will return the counter, a 1. Otherwise it will move to the next node in the list, increment the counter to two and run the check again. If this second node is in fact the tail, we'll get the counter returned, which will be two.

Let's use this private count_node method in our count method:

def count
  return 0 if empty?
  count_node(head, 1)
end

Our count method will return 0 if the linked list is empty, otherwise it will call the count_node private method, passing in the head as the node parameter and the integer 1 as the counter. This will pass our tests!

Screen Shot 2018-02-03 at 2.36.36 PM.png

Step 5: To STring for Real

We've handled append properly. We've recursively counted our nodes. Now it's time to get our to_string method working as intended. Our desired behavior is that if we append three nodes onto our list with names 'Rhodes, Hardy, and Smith' and call to String we should get:

`=> "The rhodes family, followed by the Hardy family, followed by the Smith family"

Let's write our test and get started!

def test_to_string_works_with_three_nodes
  subject = LinkedList.new
  subject.append('Rhodes')
  subject.append('Hardy')
  subject.append('Smith')
  expected = 'The Rhodes family, followed by the Hardy family, followed by the Smith family'

  result = subject.to_string

  assert_equal expected, result
end

Our current to_string implementation does not pass this new test:

Screen Shot 2018-02-03 at 2.41.47 PM.png

We can follow our recursive pattern yet again. First let's start with a simple private concat method that we will use to add sentence fragments together.

def concat(sentence, node)
  "#{sentence}, followed by the #{node.surname} family"
en

This concat method takes in a sentence and a node. It concatenates ", followed by the <node.surname>" onto the passed in string.

Next let's add a stringify_node private method that we can call recursively from within our to_string method.

def stringify_node(node, sentence)
  return concat(sentence, node) if node.tail?
  stringify_node(node.next_node, concat(sentence, node))
end

This method will take in a node and a sentence string. It will concat the passed in node to the passed in sentence if this is the last node. Otherwise, we will recursively call stringify_node and pass in the next node as well as an updated sentence that has the current node concatenated onto the end.

Since the start of our sentence string is a little different than the string concatenated for subsequent nodes, we can extract that bit into it's very own private method like this:

def sentence_starter
  "The #{head.surname} family"
end

Backing out to the public to_string method we can put all these pieces together and go with something like this:

def to_string
  return "" if empty?
  return sentence_starter if head.tail?
  stringify_node(head.next_node, sentence_starter)
end

Step 6: Prepend

Let's add a prepend method to our linked list. Prepend is the opposite of append in that it adds a new node to the front or head of our linked list. First, let's start with a test.

def test_prepend_appends_to_head
  expected = 'The McKinney family, followed by the Brooks family, followed by the Henderson family'
  subject = LinkedList.new
  subject.append('Brooks')
  subject.append('Henderson')
  subject.prepend('McKinney')

  result = subject.to_string

  assert_equal expected, result
end

Here we are going to use our to_string method to infer the order of our linked list nodes. Since we append two nodes (Brooks, Henderson) and then prepend a new node (McKinney) our to_string call should give us our families in the order described in the expected variable above.

To implement we do not need to worry about recursion. All we have to do is create a new node, take the head and set that as the next node after our new node and finally add our new node to the head of our linked list. Again, we must use the self call to reference the instance of the linked list and take advantage of our attr_accessor.

def prepend(surname)
  node = new_node(surname)
  node.next_node = head
  self.head = node
end

Step 7 Insert

Now we want to implement an insert method which adds a new node with the given name at a specified position.

> require "./lib/linked_list"
> list = LinkedList.new
> list.append("Brooks")
=> <Node @surname="Brooks" @next_node=nil #5678904567890>
> list.to_string
=> "The Brooks family"
> list.append("Henderson")
=> <Node @surname="Henderson" @next_node=nil #5678904567890>
> list.prepend("McKinney")
=> <Node @surname="McKinney" @next_node=<Node @surname="Brooks" ... > #5678904567890>
> list.to_string
=> "The McKinney family, followed by the Brooks family, followed by the Henderson family"
> list.count
=> 3
> list.insert(1, "Lawson")
=> <Node @surname="Lawson" @next_node=<Node @surname="Brooks" ... > #5678904567890>
> list.to_string
=> "The McKinney family, followed by the Lawson family, followed by the Brooks family, followed by the Henderson family"

The position should be 0 indexed, so if we wanted to insert a node at the head of the list we would input a 0. To insert to the second position we would input a 1 and so on.

def test_insert
  expected 'The Brooks family, followed by the Lawson family, followed by the Henderson family, followed by the McKinney family'
  subject = LinkedList.new
  subject.append('Brooks')
  subject.append('Henderson')
  subject.append('McKinney')

  result = subject.insert(1, 'Lawson')

  assert_instance_of Node, result
  assert_equal expected, subject.to_string
end

In the above test we create a linked list with three nodes and then test the insertion of a new node at position 1 (the second node of our list). We are asserting that the insert method returns the node it has created. And then we use our to_string method to make sure our linked list has the desired order.

First let's implement a private method to return a node at a given position because in the case of insert we are going to need the node directly before and after the given insertion position.

def node_at(node, position, counter=0)
  return node if position == counter
  node_at(node.next_node, position, counter += 1)
end

We continue with our recursive pattern and say node_at takes in a starting node, a destination position and a counter. If no counter is given, the counter defaults to 0. We will return the node if position equals counter. So if we pass in the head, position 0, and counter 0, we will get the head returned to us. If position and counter are not equal, then we call node_at and pass in the next node, the original position and our incremented counter. So if originally we pass in the head, position 1 and counter 0, on our second pass through the function the counter will be incremented to 1, which equals our destination position and so the head's next node will be returned.

def insert(position, surname)
  node = new_node(surname)
  prior_node = node_at(head, position - 1)
  next_node = node_at(head, position)
  prior_node.next_node = node
  node.next_node = next_node
  return node
en

Now we use our recently implemented private node_at method to get the prior node and the next node surrounding the desired position. For our test, our position parameter is 1 so the prior node's position should be 0 (desired position - 1). We also want to get the next node (e.g. the node that will follow our soon to be inserted node), which is at the desired position.

Next we set the prior_nodes's next node to be our new node. And then we can set our new node's next node to be the remaining nodes in the linked list (next_node). We will then return our next node.

The above method can be paired down a bit as follows:

def insert(position, surname)
  node = new_node(surname)
  next_node = node_at(head, position)
  node_at(head, position - 1).next_node = node
  node.next_node = next_node
  return node
end

Step 8: Find

Next we want to implement a find method that takes in two arguments - a starting position and a count of the number of nodes to return. For example:

> list.to_string
=> "The McKinney family, followed by the Lawson family, followed by the Brooks family, followed by the Henderson family"
> list.find(2, 1)
=> "The Brooks family"
> list.find(1, 3)
=> "The Lawson family, followed by the Brooks family, followed by the Henderson family"

Let's write two tests. The first will test the find method with a starting position of 1, the second will test the find method when the position is greater than 1.

def test_find_from_start
  expected = 'The Lawson family, followed by the Brooks family, followed by the Henderson family'
  subject = LinkedList.new
  subject.append('McKinney')
  subject.append('Lawson')
  subject.append('Brooks')
  subject.append('Henderson')
  subject.append('Davis')

  result = subject.find(1, 3)

  assert_equal expected, result
end

def test_find_from_middle
  expected = 'The Brooks family'
  subject = LinkedList.new
  subject.append('McKinney')
  subject.append('Lawson')
  subject.append('Brooks')
  subject.append('Henderson')
  subject.append('Davis')

  result = subject.find(2, 1)

  assert_equal expected, result
end

The first test will help us check to make sure that if we want to find from position 1, we can stop our find 3 nodes later (before the end of the linked list). The second test will help us check that we can find starting from position 2, and we can stop immediately by passing in a 1 for the count argument.

We can re-use the node_at, sentence_starter, and stringify_node methods with a few augmentations. We can update sentence_starter to take in a node parameter. By default we can set this to be the head of the linked list so as not to break our other tests.

def sentence_starter(node=head)
  "The #{node.surname} family"
end

We can update stringify_node to take in two additional arguments, a terminal - e.g. the position we would like to stop at - and a counter. We will assign both of these parameters default values so as not to break our other tests.

def stringify_node(node, sentence, terminal=nil, counter=1)
  return concat(sentence, node) if node.tail? || terminal == counter
  stringify_node(node.next_node, concat(sentence, node), terminal, counter += 1)
end

Now in addition to ending our sentence concatenation if the node is the tail of the linked list we add an additional or condition that says we should stop concatenating if the terminal is equal to the counter. In other words, stop if we have traversed down the linked list the number of times equal to the terminal parameter.

def find(start, count)
  found_node = node_at(head, start)
  sentence = sentence_starter(found_node)
  return sentence if count == 1
  stringify_node(found_node.next_node, sentence, count -= 1)
end

Our find method leverages our node_at method by immediately grabbing the 'found_node' which corresponds to the node at the position defined by the start parameter. In the case of our first test, that would be Lawson. In the case of our second test where we want to find the node at position 2, we return Brooks. Our linked list is zero indexed, so the node at position 0 is the head.

Next we begin our sentence by calling sentence_starter and passing in the found node. This will return 'The Lawson family' for our first test or 'The Brooks family' for our second test.

Now, if our count is 1, meaning we only want to return 1 node, our job is finished. We can just return the sentence as is. So in the case of the second test, we return 'The Lawson family' and our test passes.

If, on the other hand, we want to return additional stringified nodes (e.g. the count is greater than 1), then we call stringify_node with our newly updated interface and pass in the count argument minus 1. We subtract 1 because we have already found one node of the total number of nodes we need to return.

The above code will pass all our tests, so let's refactor and clean it up:

def find(start, count)
  node = node_at(head, start)
  return sentence_starter(node) if count == 1
  stringify_node(node.next_node, sentence_starter(node), count -= 1)
end

Step 9: Includes?

Let's add an includes? method that takes in a surname argument and returns true if there is a node containing that surname in our linked list. First, let's write two tests - one for the happy path where our list does include the particular node and one for the sad path.

def test_includes_returns_true_when_given_surname_is_present
  subject = LinkedList.new
  subject.append('McKinney')
  subject.append('Lawson')
  subject.append('Brooks')
  subject.append('Henderson')
  subject.append('Davis')

  result = subject.includes?('Henderson')

  assert_equal true, result
end

def test_includes_returns_false_when_given_surname_is_not_present
  subject = LinkedList.new
  subject.append('McKinney')
  subject.append('Lawson')
  subject.append('Brooks')
  subject.append('Henderson')
  subject.append('Davis')

  result = subject.includes?('Williams')

  assert_equal false, result
end

In our first test, our result should be true because Henderson is included in the list. In our second test, our result should be false because Williams is not included in the list.

We'll next need to define a private method that we can call recursively to find a node by the surname. If a node is found we should get true as a result.

def find_by_surname(node, surname)
  return true if node.surname == surname
  return false if node.tail?
  find_by_surname(node.next_node, surname)
end

We will pass our find_by_surname method a starting node and a surname to find. First, we will want to return true if the node has the sought after surname. Next, we will want to return false if the node is the tail of our linked list. If that is the case it means we have gotten to the end of our linked list and have not found the sought after surname. Finally, if neither of those conditions are met, recursively call find_by_surname on the next node.

We can add an includes? public method to wrap this find_by_surname and that will pass our tests!

def includes?(surname)
  find_by_surname(head, surname)
end

Step 10: PoP

Our last new method to implement will be pop, which will remove the last node from our list with the following behavior.

....
> list.to_string
=> "The McKinney family, followed by the Lawson family, followed by the Brooks family, followed by the Henderson family"
> list.pop
The Henderson family has died of dysentery
=> <Node surname="Henderson" next_node=nil #5678904567890>
> list.pop
The Brooks family has died of dysentery
=> <Node surname="Brooks" next_node=nil #5678904567890>
> list.to_string
=> "The McKinney family, followed by the Lawson family"

First let's write a test.

def test_pop
  subject = LinkedList.new
  subject.append('McKinney')
  subject.append('Lawson')
  subject.append('Brooks')
  subject.append('Henderson')

  result = subject.pop

  assert_equal 'Henderson', result.surname
end

Here we create a linked list. We call pop and expect to be returned a node with surname 'Henderson', which corresponds to our tail node's surname. Notice that we are not making assertions about messages printed to console. We can manually test those after we create our pop implementation.

def pop
  new_tail = node_at(head, count - 2)
  old_tail = new_tail.next_node
  new_tail.next_node = nil
  puts "The #{old_tail.surname} family has died of dysentery"
  old_tail
end

Here we first find the new tail of our linked list, which is the node two less than the entire count of nodes. In our test, our linked list has 4 nodes. If we try to find the node_at(head, 4) we will get nil because our count is zero indexed. If we try to find the node_at(head, 3) we will get the tail of our list, which is not what we want. We want to find the new tail, which is the second to last node on our list, or node_at(head, 2) or node_at(head, count - 2).

We next want to grab our old tail, which we can get easily by calling new_tail.next_node. Next we want to clear out the new_tails's next node, effectively making it the new tail of our linked list.

After that we print our message and then return the old_tail.

To refactor this, let's remember the principles of encapsulation and separation of concerns. I kind of like the idea that a node should be able to empty itself rather than have the linked list set it's next_node to be nil.

So let's jump back to our node test. First we will need a node. We will add some dummy data to the next node attribute of our node. We will then call clear on our node and assert that it should now respond true to tail?, which means that its next node is nil.

def test_it_can_remove_next_node
  subject = Node.new('Burke')
  data = 'pants'

  subject.next_node = data
  subject.clear!

  assert_equal true, subject.tail?
end

The implementation for this test could be something like:

def clear!
  self.next_node = nil
end

We can now use this clear method in our linked list:

def pop
  new_tail = node_at(head, count - 2)
  old_tail = new_tail.next_node
  new_tail.clear!
  puts "The #{old_tail.surname} family has died of dysentery"
  old_tail
end

conclusion

It is great to use the expressiveness and fun of the Ruby programming language to practice algorithmic thinking, recursion, and building data structures.

You can find the completed project described in this post in my Perilous Journey Github repository.