Object
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.
LinkedList is based on the LinkedList library by Kirk Haines.
Copyright (C) 2006 Kirk Haines <khaines@enigo.com>.
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
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
Generated with the Darkfish Rdoc Generator 2.