Doubly Linked Circular List in Ruby

09 Dec 2018 - by 'Maurits van der Schee'

For part 2 of the puzzle on day 9 of Advent of Code I needed an array with cheap insertion and removal. That was a perfect excuse to implemented a doubly linked circular list (in Ruby). It has 5 methods (append, remove, read, rotate and length) and a constructor. You can also convert to string, something that comes in handy for tests and during debugging.

Methods

These are the 5 methods:

append(x) - adds value x at the end of the list.
remove() - removes an item from the end of the list.
read() - reads the item at the end of the list.
rotate(x) - moves the head x steps forward.
length() - gives you the length of the list.

Below you find the test cases that show these methods in action.

Tests

By reading the tests you can understand how the DoublyLinkedCircularList works. Note that even though chaining is used in the API the implementation is not immutable (for performance reasons).

assert_equal('[]', DoublyLinkedCircularList.new.to_s)
assert_equal('[0]', DoublyLinkedCircularList.new.append(0).to_s)
assert_equal('[]', DoublyLinkedCircularList.new.append(0).remove.to_s)
assert_equal('[]', DoublyLinkedCircularList.new.append(0).remove.remove.to_s)
assert_equal('[0,1,2]', DoublyLinkedCircularList.new.append(0).append(1).append(2).to_s)
assert_equal('[0,1]', DoublyLinkedCircularList.new.append(0).append(1).append(2).remove.to_s)
assert_equal('[0]', DoublyLinkedCircularList.new.append(0).append(1).append(2).remove.remove.rotate(-1).to_s)
assert_equal('[0]', DoublyLinkedCircularList.new.append(0).append(1).append(2).remove.remove.rotate(1).to_s)
assert_equal('[2,0,1]', DoublyLinkedCircularList.new.append(0).append(1).append(2).rotate(-6).rotate(5).to_s)
assert_equal('[0,1,2]', DoublyLinkedCircularList.new.append(0).append(2).rotate(-1).append(1).rotate(1).to_s)
assert_equal('[0,]', DoublyLinkedCircularList.new.append(0).append(nil).to_s)
assert_equal(nil, DoublyLinkedCircularList.new.read)
assert_equal(nil, DoublyLinkedCircularList.new.append(0).append(nil).read)
assert_equal(0, DoublyLinkedCircularList.new.append(0).read)
assert_equal(1, DoublyLinkedCircularList.new.append(0).append(1).read)
assert_equal(1, DoublyLinkedCircularList.new.append(0).append(1).append(2).rotate(-1).read)
assert_equal('[1,2]', DoublyLinkedCircularList.new.append(0).append(1).append(2).rotate(-2).remove.to_s)
assert_equal(0, DoublyLinkedCircularList.new.length)
assert_equal(0, DoublyLinkedCircularList.new.remove.length)
assert_equal(1, DoublyLinkedCircularList.new.append(0).length)
assert_equal(2, DoublyLinkedCircularList.new.append(0).append(1).length)
assert_equal(1, DoublyLinkedCircularList.new.append(0).append(1).append(2).remove.remove.length)

These tests can also be found here.

Implementation

Ruby is quite an elegant language to write these kind of things in. Below you find the class that implements the DoublyLinkedCircularList. Note that the class has no dependencies:

class DoublyLinkedCircularList
    attr_reader :length

    class Node
        attr_accessor :previous
        attr_accessor :next
        attr_reader     :value

        def initialize(_value)
            @previous = nil
            @next = nil
            @value = _value
        end

        def to_s
            @value.to_s
        end
    end

    def initialize
        @head = nil
        @length = 0
    end

    def rotate(steps)
        return self if @head.nil?
        steps.abs.times do
            @head = if steps < 0
                        @head.previous
                    else
                        @head.next
                    end
        end
        self
    end

    def append(value)
        node = Node.new(value)
        if @head.nil?
            node.previous = node
            node.next = node
        else
            node.previous = @head
            node.next = @head.next
        end
        node.previous.next = node
        node.next.previous = node
        @head = node
        @length += 1
        self
    end

    def remove
        return self if @head.nil?
        node = @head.previous
        node.next = @head.next
        node.next.previous = node
        @head = if @head == @head.next
                    nil
                else
                    @head.previous
                end
        @length -= 1
        self
    end

    def read
        if @head.nil?
            nil
        else
            @head.value
        end
    end

    def to_s
        str = '['
        node = @head
        unless node.nil?
            loop do
                node = node.next
                str += node.to_s
                break if node == @head
                str += ','
            end
        end
        str += ']'
        str
    end
end

This code can also be found here. I also did a port of this code to Go that can be found here.

PS: Liked this article? Please share it on Facebook, Twitter or LinkedIn.

TQ
dev.com