Linked Lists

Getting ready for mod3, we were instructed to review one of our old linked list projects. This was one of the very first projects we did, and I remember it being…challenging. But when I went back to it after finishing mod2, it wasn’t quite so bad. As I was going through it, I focused on documentation and taking notes so I could write something like this.

For this, you’re going to need to create two separate classes. The first class is a node, which is the building block of a linked list. There are a ton of great resources out there about what a Linked List is, so I’m going to skip that explanation and just dive in. I’ll post a link later.

I’m a big fan of Test Driven Development, so I am going to write some tests first. I use RSpec, so that is how I will be describing them here. The first couple tests are going to just make sure that the node exists, it can have data, and it links to another node (I’ll call that next_node)

require './lib/node'
RSpec.describe Node do
  describe 'initialize' do
    it 'exists, has data, and links to another' do
      node = Node.new("A")
      expect(node).to be_instance_of(Node)
      expect(node.data).to eq("A")
      expect(node.next_node).to eq(nil)
    end
  end
end

Honestly, I would probably write that as a few different tests, but it seems OK to just do it that way for this. I am going to change the data in the tests/methods of this particular set of posts so I’m not just writing that project online. When I make notes like this, I try to make them as simple as possible, so I will probably just make a linked list of the alphabet.

So, how do I make this pass. First, I need to initialize a node class.

class Node
  def initialize

  end

That will make the first expect statement pass. It looks like for this test, some data needs to be passed into it, so I will add that as well as the instance variable it gets passed into. You’re going to want an attr_reader in this to make sure that the data can be read.

class Node
  attr_reader :data
  def initialize(data)
    @data = data
  end

This should make the second test pass. Finally, I’m going to add in the next_node instance variable, and have it default as pointing to nil. This will also need to be added to the attr_reader.

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

There you go, that should make those first three tests pass, and you have a node to start building the linked list. That’s next time though.