class Hashery::LinkedList
LinkedList
implements a simple doubly linked list with efficient hash-like element access.
This is a simple linked-list implementation with efficient random access of data elements. It was inspired by George Moscovitis’ LRUCache implementation found in Facets 1.7.30, but unlike the linked-list in that cache, this one does not require the use of a mixin on any class to be stored. The linked-list provides the push, pop, shift, unshift, first, last, delete and length methods which work just like their namesakes in the Array class, but it also supports setting and retrieving values by key, just like a hash.
LinkedList
was ported from the original in Kirk Hanes IOWA web framework.
Acknowledgements¶ ↑
LinkedList
is based on the LinkedList
library by Kirk Haines.
Copyright © 2006 Kirk Haines <khaines@enigo.com>.
Public Class Methods
Initialize new LinkedList
instance.
# File lib/hashery/linked_list.rb, line 46 def initialize @head = Node.new @tail = Node.new @lookup = Hash.new node_join(@head,@tail) end
Public Instance Methods
Lookup entry by key.
# File lib/hashery/linked_list.rb, line 57 def [](key) @lookup[key].value end
Add node to linked list.
# File lib/hashery/linked_list.rb, line 64 def []=(k,v) if @lookup.has_key?(k) @lookup[k].value = v else n = Node.new(k,v,@head,@head.next_node) node_join(n,@head.next_node) node_join(@head,n) @lookup[k] = n end v end
Remove node idenified by key.
# File lib/hashery/linked_list.rb, line 86 def delete(key) n = @lookup.delete(key) v = n ? node_purge(n) : nil v end
Iterate over nodes, starting with the head node and ending with the tail node.
# File lib/hashery/linked_list.rb, line 203 def each n = @head while (n = n.next_node) and n != @tail yield(n.key,n.value) end end
Is linked list empty?
# File lib/hashery/linked_list.rb, line 79 def empty? @lookup.empty? end
Get value of first node.
# File lib/hashery/linked_list.rb, line 95 def first @head.next_node.value end
Get value of last node.
# File lib/hashery/linked_list.rb, line 102 def last @tail.prev_node.value end
Number of nodes.
# File lib/hashery/linked_list.rb, line 193 def length @lookup.length end
# File lib/hashery/linked_list.rb, line 136 def pop k = @tail.prev_node.key n = @lookup.delete(k) node_delete(n) if n end
# File lib/hashery/linked_list.rb, line 145 def push(v) if @lookup.has_key?(v) n = @lookup[v] node_delete(n) node_join(@tail.prev_node,n) node_join(n,@tail) else n = Node.new(v,v,@tail.prev_node,@tail) node_join(@tail.prev_node,n) node_join(n,@tail) @lookup[v] = n end v end
Produces an Array of key values.
Returns [Array].
# File lib/hashery/linked_list.rb, line 167 def queue r = [] n = @head while (n = n.next_node) and n != @tail r << n.key end r end
# File lib/hashery/linked_list.rb, line 109 def shift k = @head.next_node.key n = @lookup.delete(k) node_delete(n) if n end
Converts to an Array of node values.
Returns [Array].
# File lib/hashery/linked_list.rb, line 181 def to_a r = [] n = @head while (n = n.next_node) and n != @tail r << n.value end r end
# File lib/hashery/linked_list.rb, line 118 def unshift(v) if @lookup.has_key?(v) n = @lookup[v] node_delete(n) node_join(n,@head.next_node) node_join(@head,n) else n = Node.new(v,v,@head,@head.next_node) node_join(n,@head.next_node) node_join(@head,n) @lookup[v] = n end v end
Private Instance Methods
Delete a node.
n - A node.
# File lib/hashery/linked_list.rb, line 217 def node_delete(n) node_join(n.prev_node,n.next_node) v = n.value end
Join two nodes.
a - A node. b - A node.
# File lib/hashery/linked_list.rb, line 242 def node_join(a,b) a.next_node = b b.prev_node = a end
Purge a node.
n - A node.
# File lib/hashery/linked_list.rb, line 227 def node_purge(n) node_join(n.prev_node,n.next_node) v = n.value n.value = nil n.key = nil n.next_node = nil n.prev_node = nil v end