linked-list's Introduction

LinkedList

Ruby implementation of Doubly Linked List, following some Ruby idioms.

Installation

Add this line to your application's Gemfile:

gem 'linked-list'

And then execute:

$ bundle

Or install it yourself as:

$ gem install linked-list

Usage

object = Object.new # could be anything
list = LinkedList::List.new

list.push(object)
list << object # same as `push`

list.unshift(object)

list.pop
list.shift

list.insert(object, before: object)
list.insert(object, before: ->(n) { n == 'foo' })

list.insert(object, after: object)
list.insert(object, after: ->(n) { n == 'foo' })

list.insert_before(object, node)
list.insert_after(object, node)

list.reverse
list.reverse!

list.delete(object)
list.delete { |n| n == 'foo' }

list.delete_all(object)
list.delete_all { |n| n == 'foo' }

list.each  # Enumerator object
list.each { |e| puts e }

list.reverse_each # Enumerator object
list.reverse_each { |e| puts e }

list.reverse_each_node # Enumerator object
list.reverse_each_node { |node| puts node.data }

list.first # head of the list
list.last # tail of the list

list.length
list.size # same as `length`

list.to_a

Another way to instantiate List or Node is to use conversion functions. First, include LinkedList::Conversions module to your class

class Foo
  include LinkedList::Conversions
end

Now anywhere in your class you can use the following methods

Node(object)           # will return new `Node` object
List(object)           # will return new `List` object with one `Node` object
List([object, object]) # will return new `List` object with two `Node` objects

Please see LinkedList::List, LinkedList::Node, and LinkedList::Conversions for details.

Tests

Run test with

$ rake

Contributing

Fork it
Create your feature branch (git checkout -b my-new-feature)
Commit your changes (git commit -am 'Add some feature')
Push to the branch (git push origin my-new-feature)
Create new Pull Request

linked-list's People

Contributors

Stargazers

Watchers

linked-list's Issues

Make List#__unlink_node public

There's currently no way to remove a value from a list in O(1) time, even if you have its Node. Exposing List#__unlink_node publicly, or alternately giving List#delete a special case if it's passed a Node, would solve this.

Recommend Projects