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.
Methods
[]
[]=
delete
each
empty?
first
last
length
new
pop
push
queue
shift
to_a
unshift
Included Modules
Classes and Modules
Class LinkedList::NodePublic Class methods
[ + ]
# File lib/more/facets/linkedlist.rb, line 87 def initialize @head = Node.new @tail = Node.new @lookup = Hash.new node_join(@head,@tail) end
Public Instance methods
[ + ]
# File lib/more/facets/linkedlist.rb, line 94 def [](v) @lookup[v].value end
[ + ]
# File lib/more/facets/linkedlist.rb, line 98 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
[ + ]
# File lib/more/facets/linkedlist.rb, line 114 def delete(k) n = @lookup.delete(k) v = n ? node_purge(n) : nil v end
[ + ]
# File lib/more/facets/linkedlist.rb, line 192 def each n = @head while (n = n.next_node) and n != @tail yield(n.key,n.value) end end
[ + ]
# File lib/more/facets/linkedlist.rb, line 110 def empty? @lookup.empty? end
[ + ]
# File lib/more/facets/linkedlist.rb, line 120 def first @head.next_node.value end
[ + ]
# File lib/more/facets/linkedlist.rb, line 124 def last @tail.prev_node.value end
[ + ]
# File lib/more/facets/linkedlist.rb, line 188 def length @lookup.length end
[ + ]
# File lib/more/facets/linkedlist.rb, line 149 def pop k = @tail.prev_node.key n = @lookup.delete(k) node_delete(n) if n end
[ + ]
# File lib/more/facets/linkedlist.rb, line 155 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
[ + ]
# File lib/more/facets/linkedlist.rb, line 170 def queue r = [] n = @head while (n = n.next_node) and n != @tail r << n.key end r end
[ + ]
# File lib/more/facets/linkedlist.rb, line 128 def shift k = @head.next_node.key n = @lookup.delete(k) node_delete(n) if n end
[ + ]
# File lib/more/facets/linkedlist.rb, line 179 def to_a r = [] n = @head while (n = n.next_node) and n != @tail r << n.value end r end
[ + ]
# File lib/more/facets/linkedlist.rb, line 134 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