Doubly Linked List implementation in Ruby.md

Doubly Linked List implementation in Ruby

Setup

• Install Ruby ~> 2.6
• gem install rspec
• Open an IRB session with irb -r ./linked_list.rb

list = LinkedList.new
list.add_to_front(:first)
list.add_to_back(:second)
list.add_to_back(:fifth)
list.add_to_front(:zero)
list.insert_before(:fourth, :fifth)
list.insert_after(:third, :second)
list.to_a # => [:zero, :first, :second, :third, :fourth, :fifth]
list.length #=> 6
list.contains?(:zero) #=> true
list.remove(:zero)
list.length #=> 5
list.contains?(:zero) #=> false
list.to_a # => [:first, :second, :third, :fourth, :fifth]
sorted_list = list.sort
sorted_list.head.item # => :fifth
sorted_list.tail.item # => :third
sorted_list.to_a # => [:fifth, :first, :fourth, :second, :third]
list.to_a # => [:first, :second, :third, :fourth, :fifth]

Testing

ruby ./linked_list_spec.rb --format=doc

linked_list.rb

# Implement a generic Linked List from scratch with the following interface
#
# AddToFront(itemToAdd)
# AddToBack(itemToAdd)
# InsertAfter(itemToInsert, referenceItem)
# InsertBefore(itemToInsert, referenceItem)
# Remove(itemToRemove)
# uint Length()
# bool Contains(item)
# Sort()

class LinkedList
  attr_reader :length, :head, :tail

  def initialize
    @head = nil
    @tail = nil
    @length = 0
  end

  def add_to_front(item)
    node = Node.new(item)
    @tail ||= node
    set_head(node)
    update_length_and_return_self
  end
  # alias_method :unshift, :add_to_front

  def add_to_back(item)
    node = Node.new(item)
    @head ||= node
    set_tail(node)
    update_length_and_return_self
  end
  # alias_method :push, :add_to_front

  def insert_before(item, reference_item)
    reference_node = find(reference_item)
    if reference_node.nil? || reference_node == @head
      add_to_front(item)
    else
      insert(Node.new(item), reference_node.prev, reference_node)
      update_length_and_return_self
    end
  end

  def insert_after(item, reference_item)
    reference_node = find(reference_item)
    if reference_node.nil? || reference_node == @tail
      add_to_back(item)
    else
      insert(Node.new(item), reference_node, reference_node.next)
      update_length_and_return_self
    end
  end

  def remove(item)
    reference_node = find(item)
    if reference_node
      prev_node = reference_node.prev
      next_node = reference_node.next

      prev_node.next = next_node if prev_node
      next_node.prev = prev_node if next_node

      @head = next_node if reference_node == @head
      @tail = prev_node if reference_node == @tail

      reference_node.prev = reference_node.next = nil
      return update_length_and_return_self(mode: :decrement)
    end
    self
  end

  def contains?(item)
    !find(item).nil?
  end

  def sort
    list = LinkedList.new
    quick_sort(to_a).each do |item|
      list.add_to_back(item)
    end
    list
  end

  def find(item_to_find)
    walk(@head) do |node|
      return node if node.item == item_to_find
    end
  end

  def to_a
    items = []
    walk(@head) do |node|
      items << node.item
    end
    items
  end

  private

  def walk(start)
    node = start
    while !node.nil? do
      yield(node)
      node = node.next
    end
  end

  def quick_sort(items)
    return [] if items.empty?
    pivot = items.first
    groups = items.group_by { |item| item.to_s <=> pivot.to_s }
    quick_sort(groups[-1] || []) +
      groups[0] +
      quick_sort(groups[1]  || [])
  end

  def set_head(node)
    insert(node, nil, @head)
    @head = node
  end

  def set_tail(node)
    insert(node, @tail, nil)
    @tail = node
  end

  def insert(node, prev_node, next_node)
    node.prev = prev_node
    node.next = next_node
    prev_node.next = node if prev_node
    next_node.prev = node if next_node
  end

  def update_length_and_return_self(mode: :increment)
    case mode
    when :decrement
      @length -= 1
    else
      @length += 1
    end
    self
  end
end

class Node
  attr_accessor :item, :prev, :next

  def initialize(item)
    @item = item
    @prev = nil
    @next = nil
  end
end

linked_list_spec.rb

# Ensure rspec gem is installed
# Then run `ruby ./linked_list_spec.rb --format=doc`

require "rspec/autorun"
require_relative "linked_list"

RSpec.describe Node do
  let(:item) { :a }

  subject { Node.new(item) }

  it "sets item attribute from arguments" do
    expect(subject.item).to eq(item)
  end
end

RSpec.describe LinkedList do
  let(:item) { :my_new_item_value }
  let(:existing_item) { :existing_item_value }
  let(:some_other_head) { :some_other_head }
  let(:some_other_tail) { :some_other_tail }
  let(:list) { described_class.new }

  shared_context "a list containing existing_item" do
    before { list.add_to_front(existing_item) }
  end

  shared_context "a list containing item" do
    before { list.add_to_back(item) }
  end

  shared_examples "inserting a node as head" do
    context "when the list contains items" do
      include_context "a list containing existing_item"
      include_examples "a head node with next node"
    end

    context "when the list is empty" do
      include_examples "a singular node that is both tail and head"
    end
  end

  shared_examples "inserting a node as tail" do
    context "when the list contains items" do
      include_context "a list containing existing_item"
      include_examples "a tail node with prev node"
    end

    context "when the list is empty" do
      include_examples "a singular node that is both tail and head"
    end
  end

  shared_examples "a head node with next node" do
    it "adds the new item to the list" do
      expect { subject }.to change { list.length }.by(1)
    end

    it "sets the new item as head" do
      subject
      expect(list.head).to eq(list.find(item))
    end

    it "sets the new item's prev node to nil" do
      subject
      expect(list.find(item).prev).to be_nil
    end

    it "sets the new item as the prev node of the former head" do
      subject
      expect(list.find(existing_item).prev).to eq(list.find(item))
    end

    it "sets the former head as the next node of the new item" do
      subject
      expect(list.find(item).next).to eq(list.find(existing_item))
    end
  end

  shared_examples "a tail node with prev node" do
    it "adds the new item to the list" do
      expect { subject }.to change { list.length }.by(1)
    end

    it "sets the new item as tail" do
      subject
      expect(list.tail).to eq(list.find(item))
    end

    it "sets the new item's next node to nil" do
      subject
      expect(list.find(item).next).to be_nil
    end

    it "sets the new item as the next node of the former tail" do
      subject
      expect(list.find(existing_item).next).to eq(list.find(item))
    end

    it "sets the former tail as the prev node of the new item" do
      subject
      expect(list.find(item).prev).to eq(list.find(existing_item))
    end
  end

  shared_examples "a middle node with prev and next nodes" do
    it "adds the new item to the list" do
      expect { subject }.to change { list.length }.by(1)
    end

    it "sets the prev node of the new item to the reference item's prev node" do
      subject
      expect(list.find(item).prev).to eq(list.find(prev_item))
    end

    it "sets the next node of the new item to the reference item" do
      subject
      expect(list.find(item).next).to eq(list.find(next_item))
    end

    it "sets the prev node of the reference item to the new item" do
      subject
      expect(list.find(next_item).prev).to eq(list.find(item))
    end

    it "sets the next node of the reference item's prev node to the new node" do
      subject
      expect(list.find(prev_item).next).to eq(list.find(item))
    end
  end

  shared_examples "a singular node that is both tail and head" do
    it "adds the new item" do
      expect { subject }.to change { list.length }.from(0).to(1)
    end

    it "sets the new item as both head and tail" do
      subject
      expect(list.head).to eq(list.find(item))
      expect(list.tail).to eq(list.find(item))
    end

    it "sets the new item's prev node to nil" do
      subject
      expect(list.find(item).prev).to be_nil
    end

    it "sets the new item's next node to nil" do
      subject
      expect(list.find(item).next).to be_nil
    end
  end

  describe "#add_to_front" do
    subject { list.add_to_front(item) }
    include_examples "inserting a node as head"
  end

  describe "#add_to_back" do
    subject { list.add_to_back(item) }
    include_examples "inserting a node as tail"
  end

  describe "#insert_before" do
    subject { list.insert_before(item, existing_item) }

    context "when the list contains the reference item" do
      include_context "a list containing existing_item"

      context "when the reference item is head" do
        include_examples "a head node with next node"
      end

      context "when the reference item is not head" do
        before { list.add_to_front(some_other_head) }
        include_examples "a middle node with prev and next nodes" do
          let(:prev_item) { some_other_head }
          let(:next_item) { existing_item }
        end
      end
    end

    context "when the list does not contain the reference item" do
      include_examples "inserting a node as head"
    end
  end

  describe "#insert_after" do
    subject { list.insert_after(item, existing_item) }

    context "when the list contains the reference item" do
      include_context "a list containing existing_item"

      context "when the reference item is tail" do
        include_examples "a tail node with prev node"
      end

      context "when the reference item is not tail" do
        before { list.add_to_back(some_other_tail) }
        include_examples "a middle node with prev and next nodes" do
          let(:prev_item) { existing_item }
          let(:next_item) { some_other_tail }
        end
      end
    end

    context "when the list does not contain the reference item" do
      include_examples "inserting a node as tail"
    end
  end

  describe "#remove" do
    subject { list.remove(item) }

    context "when the list contains the item" do
      include_context "a list containing item"

      it "reduces the list length by one" do
        expect { subject }.to change { list.length }.by(-1)
      end

      context "when the item is head and tail" do
        it "sets the head to nil" do
          subject
          expect(list.head).to be_nil
        end

        it "sets the tail to nil" do
          subject
          expect(list.head).to be_nil
        end
      end

      context "when the item is head" do
        before { list.add_to_back(some_other_tail) }

        it "sets the head to the next node" do
          subject
          expect(list.head).to eq(list.find(some_other_tail))
        end

        it "sets prev of the next node to nil" do
          subject
          expect(list.find(some_other_tail).prev).to be_nil
        end
      end

      context "when the item is tail" do
        before { list.add_to_front(some_other_head) }

        it "sets the tail to the prev node" do
          subject
          expect(list.head).to eq(list.find(some_other_head))
        end

        it "sets next of the prev node to nil" do
          subject
          expect(list.find(some_other_head).next).to be_nil
        end
      end

      context "when the item is neither head nor tail" do
        before do
          list.add_to_front(some_other_head)
          list.add_to_back(some_other_tail)
        end


        it "sets prev of the next node to the removed item's prev node" do
          subject
          expect(list.find(some_other_head).next).to eq(list.find(some_other_tail))
        end

        it "sets next of the prev node to the removed item's next node" do
          subject
          expect(list.find(some_other_tail).prev).to eq(list.find(some_other_head))
        end
      end
    end

    context "when the list does not contain the item" do
      include_context "a list containing existing_item"

      it "does not remove anything" do
        expect { subject }.to_not change { list.length }
      end
    end

    context "when the list is empty" do
      it "does not remove anything" do
        expect { subject }.to_not change { list.length }
      end
    end
  end

  describe "#contains?" do
    subject { list.contains?(item) }

    context "when the list contains the item" do
      include_context "a list containing item"

      it "returns true" do
        expect(subject).to be_truthy
      end
    end

    context "when the list does not contain the item" do
      include_context "a list containing existing_item"

      it "returns false" do
        expect(subject).to be_falsey
      end
    end
  end

  describe "#sort" do
    subject { list.sort }

    it "returns a new linked list" do
      expect(subject).to be_a(LinkedList)
      expect(subject).to_not be(list)
    end

    context "when the list is empty" do
      let(:expected_list) { LinkedList.new }

      it "returns an empty list" do
        expect(subject.length).to eq(0)
      end
    end

    context "when the list contains one item" do
      include_context "a list containing item"

      it "returns a list containing the item" do
        expect(subject.length).to eq(1)
        expect(subject.head.item).to eq(item)
      end
    end

    context "when the list contains more than one item" do
      let(:items) { [nil, :b, "a", false, :bbb, :b, "aaa", 4] }

      before do
        items.shuffle.each { |item| list.add_to_back(item) }
        expect(list.length).to eq(items.size)
      end

      it "returns a list containing the original items sorted naturally" do
        expect(subject.length).to eq(items.size)
        expect(subject.to_a).to eq([nil, 4, "a", "aaa", :b, :b, :bbb, false])
      end
    end
  end

  describe "#find" do
    subject { list.find(item) }

    context "when the item exists in the list" do
      include_context "a list containing item"

      it "returns the node of the item" do
        expect(subject).to be_a(Node)
        expect(subject.item).to eq(item)
      end
    end

    context "when the item does not exist in the list" do
      include_context "a list containing existing_item"

      it "returns nil" do
        expect(subject).to be_nil
      end
    end

    context "when the list is empty" do
      it "returns nil" do
        expect(subject).to be_nil
      end
    end
  end

  describe "#to_a" do
    subject { list.to_a }

    context "when the list is empty" do
      it "returns an empty array" do
        expect(subject).to eq([])
      end
    end

    context "when the list contains items" do
      before do
        list.add_to_back(item)
        list.add_to_back(existing_item)
        list.add_to_back(some_other_head)
        list.add_to_back(some_other_tail)
      end

      it "returns an array of items" do
        expect(subject).to contain_exactly(item, existing_item, some_other_head, some_other_tail)
      end
    end
  end
end