DoubleLinkedList

The missing Ruby Linked list

Installation

Add this line to your application's Gemfile:

gem 'double_linked_list'

And then execute:

$ bundle

Or install it yourself as:

$ gem install double_linked_list

Usage

navigation:

• next
• previous or prev

llist = DoubleLinkedList.from_a(1, 2, 3)
llist.datum #=> 1
llist.next.datum #=> 2
llist.next.next.datum #=> 3
llist.next.next.next #=> nil
llist.next.next.prev.datum #=> 2

Elements in the list delegate methods to datum

class DatumExample
  def hello
    true
  end
end
dll = DoubleLinkedList.from_a(DatumExample.new, DatumExample.new, DatumExample.new, DatumExample.new)
dll.head.hello # => true
dll.next.prev.hello # => true
dll.last.hello # => true
dll.last.next.hello # => NoMethodError: undefined method `hello' for nil:NilClass

last:

llist = DoubleLinkedList.from_a(1, 2, 3)
llist.last.datum #=> 3

find:

llist = DoubleLinkedList.from_a(1, 2, 3)
two = llist.find(2)
two.datum #=> 2
two.next.datum #=> 3
llist.find(3).datum #=> 3
llist.find(9) #=> nil

find_by:

User = Struct.new(:id)
users = [
  User.new(1),
  User.new(2),
  User.new(3)
]
llist = DoubleLinkedList.from_a(users)
llist.find_by{ |elem| elem.id == 1 }.id #=> 1

append:

llist = DoubleLinkedList.from_a(1, 2, 3)
llist.append(4)
llist.last.datum #=> 4
llist.last.next #=> be_nil
llist.last.previous.datum #=> 3

Enumerable

• map
• each
• reverse_each

each:

DoubleLinkedList.from_a(1, 2, 3).each { |e| puts e.datum }
# 1
# 2
# 3

map:

DoubleLinkedList.from_a(1, 2, 3).map { |e| e.datum + 1}
#=> [2, 3, 4]

reverse_each:

DoubleLinkedList.from_a(1, 2, 3).reverse_each { |e| puts e.datum }
# 3
# 2
# 1

chunk_by:

It will split the Double linked list in multiple linked list if the block returns truly. The first element of the splitted array are the elememts that return true in the block.

llist = DoubleLinkedList.from_a(1, 2, 3, 4)
chunked = llist.chunk_by do |e, current_llist|
            e.datum == 3 && current_llist.head.datum == 1
          end
chunked.first.is_a? DoubleLinkedList #=> true
chunked.first.head.datum #=> 1
chunked.first.last.datum #=> 2
chunked.map{|ll| ll.to_a } #=> [[1, 2], [3, 4]]

A custom dll can be provided to enhance dll outputs

class CustomDLL < DoubleLinkedList; end

llist = DoubleLinkedList.from_a(1, 2, 3, 4)
chunked = llist.chunk_by(CustomDLL) do |e, current_llist|
            e.datum == 3 && current_llist.head.datum == 1
          end
chunked.first.is_a?(CustomDLL) #=> true

select_by:

For selecting fractions of the linked list avoiding the elements not returned in between the selected head and last sequences. In the block must be returned a DoubleLinkedList::Sequence instance and head and last in the DoubleLinkedList::Sequence must be a DoubleLinkedList::Element (the element is passed to the block)

llist = DoubleLinkedList.from_a(1, 2, 3, 4)
select = llist.select_by do |e|
           if e.datum == 2 && e.next.datum == 3
             DoubleLinkedList::Sequence.new(head: e, last: e.next)
           end
         end
select.is_a? Array #=> true
select.first.is_a? DoubleLinkedList #=> true
select.map{|ll| ll.to_a } #=> [[2, 3]]

Development

After checking out the repo, run bin/setup to install dependencies. Then, run bundle exec rspec to run the tests. You can also run bin/console for an interactive prompt that will allow you to experiment.

To install this gem onto your local machine, run bundle exec rake install. rubygems.org.

Contributing

Bug reports and pull requests are welcome on GitHub at https://github.com/arturictus/double_linked_list.