pop & shift

For this post, I think we are going to do two methods, pop and shift

pop is going to take the last node of the linked list, remove that node and return the data

shift is going to do the opposite, it will take the head of the linked list, remove it, and return the data

These are relatively similar, so we’ll do them together.

First, the tests for pop

describe 'pop' do
  it "removes last element and returns it" do
    list = LinkedList.new
    list.append("a")
    list.append("b")
    list.append("c")
    list.append("d")
    list.append("e")
    expect(list.pop).to eq("e")
    expect(list.stringify).to eq("a, b, c, d")
    expect(list.pop).to eq("d")
    expect(list.stringify).to eq("a, b, c")
  end
  it "returns nil when called on an empty list" do
    list = LinkedList.new
    expect(list.pop).to be_nil
  end
  it "can handle a list with a single element" do
    list = LinkedList.new
    list.append("a")
      
    expect(list.pop).to eq("a")
    expect(list.stringify).to eq([])
  end    
end

The first test is checking for basic functionality, It creates a list of "a, b, c, d, e"and then pops the last one off.

The second test is making sure it knows what to do if the list is empty, and the third test checks for what to do if there is only one element.

The tests for shift are going to follow the exact same structure, and we’ll do those after we figure out this method

First, we’re going to set pop to handle nil at the beginning, that will save some frustration later

def pop
  return nil if head.nil?
end

So that takes care of one of the tests, and now I want to make sure that it know’s what to do if there is only one element. I’ll use an if statement to handle that. By the way, you can write the main part of the method first and add in the error handling later, if you feel so inclined.

This is going to reassign the data in the head to tail_data and then call head on self which we are now going to change to nil. One other thing thing on this, to make it reassign as nil, you will need to change the attr_reader :head at the top to attr_accessor :head, which will allow you to alter the head and make it nil.

def pop
  return nil if head.nil?
  if head.next_node.nil?
    tail_data = head.data
    self.head = nil
    return tail_data
  end
end

This should take care of the other error handling test.

Finally, for the main part of the method. I made the variable new_tail and assigned it count - 2. If you recall, count tells you how long the list is. This is finding the end, and going back 2 nodes. Then, I make the variable old_tail be assigned to new_tail.next_node. After that, I assigned nil to be the next_node of the newly created tail, and return the data from the old_tail

def pop
  return nil if head.nil?
  if head.next_node.nil?
    tail_data = head.data
    self.head = nil
    return tail_data
  end
  new_tail = node_at(count - 2)
  old_tail = new_tail.next_node
  new_tail.next_node = nil
  return old_tail.data
end

And this should make the final pop test pass.

We’re going to do the same general thing for shift, but it is slightly simpler. Here are the tests

describe 'shift' do
  it "removes first element and returns it" do
    list = LinkedList.new
    list.append("a")
    list.append("b")
    list.append("c")
    list.append("d")
    list.append("e")

    expect(list.shift).to eq("a")
    expect(list.stringify).to eq("b, c, d, e")
    expect(list.shift).to eq("b")
    expect(list.stringify).to eq("c, d, e")
  end
  it "returns nil when called on an empty list" do
    list = LinkedList.new
    expect(list.shift).to be_nil
  end
  it "handles a list with a single element" do
    list = LinkedList.new
    list.append("a")
    
    expect(list.shift).to eq("a")
    expect(list.stringify).to eq([])
  end
end

I’m going to just show the method here, because it’s very similar, but simpler.

def shift
  return nil if head.nil?
  former_head = head
  @head = head.next_node
  return former_head.data
end

Edit 2/12/24

If I were going back to this, I would rewrite stringify to return "" instead of an empty array, and test for it that way.