DoublyLinkedlist

A Ruby implementation of the famous Doubly Linkedlist data structure with support to the Enumerable methods such as each, to_a, map, etc. following ruby idioms. Supports Queue operations as well as Stack operations. A Linkedlist is efficient in many specific cases than other data structures such as Array.

Add this line to your application's Gemfile:

gem 'doubly_linkedlist'

And then execute:

$ bundle install

Or install it yourself as:

$ gem install doubly_linkedlist

There are different ways to initialize a linkedlist including the one which converting an array into a list by calling to_list method on the array object.

You can find the examples below.

# You can pass an array as argument whose elements will be the created list's node values.
list = DoublyLinkedlist::List.new([obj1, obj2, ...])

# Argument is optional. If not given, a empty list with no nodes is created.
empty_list = DoublyLinkedlist::List.new

# You can also use `to_list` method on an array object to create a new list object.
another_list = [obj1, obj2, ...].to_list

another_list.class # => DoublyLinkedlist::List

Returns the number of nodes in the list.

Examples are shown below,

empty_list = DoublyLinkedlist::List.new

empty_list.count # => 0

another_list = [10, 20, 40, 30].to_list

another_list.count # => 4

Returns the value at the head of the list if present, nil otherwise.

list = [10, 20, 40, 50].to_list

list.head # => 10
list.first # => 10

empty_list = DoublyLinkedlist::List.new

empty_list.head # => nil

Returns the value at the tail of the list if present, nil otherwise.

list = [10, 20, 40, 50].to_list

list.tail # => 50
list.last # => 50

empty_list = DoublyLinkedlist::List.new

empty_list.tail # => nil

Returns the node object at the given index if present, nil otherwise.

list = DoublyLinkedlist::List.new [1, "Some object", 40, 100]

list.find_at(1) # => "Some object"
list.find_at(4) # => nil

Returns the leftmost(#index)/rightmost(#rindex) index of the value present in the list, nil if not present.

list = DoublyLinkedlist::List.new [1, "Some object", 40, 100, 40]

list.index(40) # => 2
list.rindex(40) # => 4

list.index(200) # => nil

Deletes the node at a given index and returns the value present in the deleted node. Returns nil if the given index is out of range.

list = DoublyLinkedlist::List.new [1, "Some object", 40, 100, 40]
list.count # => 5

list.delete_at(1) # => "Some object"
list # => <DoublyLinkedlist::List: [1, 40, 100, 40]>
list.count # => 4

list.delete_at(6) # => nil
list.count # => 4

Converts the list object into an array object with all the node values.

list = DoublyLinkedlist::List.new [1, "Some object", 40, 100, 40]

Supports the methods available in the Enumerable module such as to_a, each, each_with_object, any?, etc. For more information on available methods refer documentation for Ruby Enumerable Module.

Some examples below,

list = DoublyLinkedlist::List.new [1, "Some object", 40, 100, 40]

list.each { |obj| puts obj }
# 1
# Some object
# 40
# 100
# 40
# => nil

arr = list.to_a
arr.class # => Array
arr # => [1, "Some object", 40, 100, 40]

Inserts a node with the given value into the head of the list, increments and returns the count of nodes.

list = DoublyLinkedlist::List.new [1, "Some object", 40, 100, 40]

list.push(25) # => 6
list # => <DoublyLinkedlist::List: [25, 1, "Some object", 40, 100, 40]>

Deletes and returns the node value at the head of the list.

list = DoublyLinkedlist::List.new [1, "Some object", 40, 100, 40]

list.pop # => 1
list.count # => 4
list # => <DoublyLinkedlist::List: ["Some object", 40, 100, 40]>

Appends a node with the given value into tail of the list, increments and returns the count of nodes.

list = DoublyLinkedlist::List.new [1, "Some object", 40, 100, 40]

list.enqueue(25) # => 6
list # => <DoublyLinkedlist::List: [1, "Some object", 40, 100, 40, 25]>

Deletes and returns the node value at the head of the list. (Same as #pop)

list = DoublyLinkedlist::List.new [1, "Some object", 40, 100, 40]

list.deque # => 1
list.count # => 4
list # => <DoublyLinkedlist::List: ["Some object", 40, 100, 40]>

Refer documentation for more information.

After checking out the repo, run bin/setup to install dependencies. Then, run rake spec to run the tests.

To install this gem onto your local machine, run bundle exec rake install. To release a new version, update the version number in version.rb, and then run bundle exec rake release, which will create a git tag for the version, push git commits and tags, and push the .gem file to rubygems.org.

Bug reports and pull requests are welcome on GitHub at https://github.com/anshabmk/doubly_linkedlist. This project is intended to be a safe, welcoming space for collaboration, and contributors are expected to adhere to the code of conduct.

The gem is available as open source under the terms of the MIT License.

Everyone interacting in the DoublyLinkedlist project's codebases, issue trackers, chat rooms and mailing lists is expected to follow the code of conduct.