Ruby implementations of common data structures.
Install Ruby Structures:
gem install ruby_structures
Or add it to your Gemfile:
gem 'ruby_structures'
Require Ruby Structures in your file:
require 'ruby_structures'
- Stack
- Queue
- Linked List
- Binary Tree
- LRU Cache
- Heap
- Priority Queue
- Graph
- Weighted Graph
More to come...
A Stack is a LIFO (last in, first out) container.
#to_a#==#empty?#push(el)#<<(el)#pop#peek#length#include?(el)
A Queue is a FIFO (first in, first out) container.
#to_a#==#empty?#enqueue(el)#<<(el)#dequeue#peek#length#include?(el)
A Linked List is an ordered collection of items, or nodes, where the ordering is determined by links between the nodes. The Ruby Structures implementation of a Linked List is doubly linked, meaning that each node has a link to the node after it as well as the node preceding it.
#to_a#empty?#length#first#last#append(key, val)#prepend(key, val)#add_after_key(ref_key, key, val)#add_before_key(ref_key, key, val)#find_by_key(key)#find_by_val(val)#include_key?(key)#include_val?(val)#remove(key)#update(key, new_val)#each(&prc)
A Binary Tree is a tree in which each Node may have a maximum of two children.
::from_array(array)#depth_first_search#breadth_first_search
An LRU Cache is an ordered container that combines a Hash and a Linked List to provide insertion, deletion and inclusion methods in constant time.
#to_a#empty?#length#first#last#append(key, val)#prepend(key, val)#add_after_key(ref_key, key, val)#add_before_key(ref_key, key, val)#remove(key)#find(key)#include?(key)
A Heap is a tree-based data structure that adheres to the Heap principle. Ruby Structures implements a Min Heap, which means that each parent element in the heap is of lesser value than each of its child elements. A Min Heap always has access to its minimum element.
::from_array(array)#to_a#empty?#length#peek#insert(el)#insert_multiple(array)#extract#find(el)#include?(el)#merge(other_heap)
A Priority Queue is a specialized queue where each element has a 'priority' attribute. A Priority Queue always has access to its highest priority element.
::from_array(array)::from_hash(hash)#to_a#empty?#length#peek#insert(data, priority)#extract#find(data)#include?(data)#merge(other_queue)
A Graph is a set of vertices and a set vertex pairs, or edges, that connect vertices to one another. Ruby Structures implements both an Undirected Graph (unordered edge pairs) and a Directed Graph (ordered edge pairs).
#add_vertex(id)#delete_vertex(id)#create_edge(id1, id2)#delete_edge(id1, id2)#adjacent?(id1, id2)#adjacent_vertices(id)#depth_first_search(target_id, start_id, &prc)#breadth_first_search(target_id, start_id, &prc)
A Weighted Graph is a Graph in which each edge is assigned a weight. Ruby Structures implements both the undirected and directed varieties of a Weighted Graph.
#add_vertex(id)#delete_vertex(id)#create_edge(id1, id2, weight)#delete_edge(id1, id2, weight)#adjacent?(id1, id2)#adjacent_vertices(id)#highest_weight_adjacent(id)#lowest_weight_adjacent(id)