class 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.
Public Class Methods
new()
click to toggle source
# File lib/more/facets/linkedlist.rb, line 60 def initialize @head = Node.new @tail = Node.new @lookup = Hash.new node_join(@head,@tail) end
Public Instance Methods
[](v)
click to toggle source
# File lib/more/facets/linkedlist.rb, line 67 def [](v) @lookup[v].value end
[]=(k,v)
click to toggle source
# File lib/more/facets/linkedlist.rb, line 71 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
delete(k)
click to toggle source
# File lib/more/facets/linkedlist.rb, line 87 def delete(k) n = @lookup.delete(k) v = n ? node_purge(n) : nil v end
each() { |key,value| ... }
click to toggle source
# File lib/more/facets/linkedlist.rb, line 165 def each n = @head while (n = n.next_node) and n != @tail yield(n.key,n.value) end end
empty?()
click to toggle source
# File lib/more/facets/linkedlist.rb, line 83 def empty? @lookup.empty? end
first()
click to toggle source
# File lib/more/facets/linkedlist.rb, line 93 def first @head.next_node.value end
last()
click to toggle source
# File lib/more/facets/linkedlist.rb, line 97 def last @tail.prev_node.value end
length()
click to toggle source
# File lib/more/facets/linkedlist.rb, line 161 def length @lookup.length end
pop()
click to toggle source
# File lib/more/facets/linkedlist.rb, line 122 def pop k = @tail.prev_node.key n = @lookup.delete(k) node_delete(n) if n end
push(v)
click to toggle source
# File lib/more/facets/linkedlist.rb, line 128 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
queue()
click to toggle source
# File lib/more/facets/linkedlist.rb, line 143 def queue r = [] n = @head while (n = n.next_node) and n != @tail r << n.key end r end
shift()
click to toggle source
# File lib/more/facets/linkedlist.rb, line 101 def shift k = @head.next_node.key n = @lookup.delete(k) node_delete(n) if n end
to_a()
click to toggle source
# File lib/more/facets/linkedlist.rb, line 152 def to_a r = [] n = @head while (n = n.next_node) and n != @tail r << n.value end r end
unshift(v)
click to toggle source
# File lib/more/facets/linkedlist.rb, line 107 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
node_delete(n)
click to toggle source
# File lib/more/facets/linkedlist.rb, line 174 def node_delete(n) node_join(n.prev_node,n.next_node) v = n.value end
node_join(a,b)
click to toggle source
# File lib/more/facets/linkedlist.rb, line 189 def node_join(a,b) a.next_node = b b.prev_node = a end
node_purge(n)
click to toggle source
# File lib/more/facets/linkedlist.rb, line 179 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