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

new() click to toggle source

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

<<(v)
Alias for: push
[](key) click to toggle source

Lookup entry by key.

# File lib/hashery/linked_list.rb, line 57
def [](key)
  @lookup[key].value
end
[]=(k,v) click to toggle source

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
delete(key) click to toggle source

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
each() { |key,value| ... } click to toggle source

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
empty?() click to toggle source

Is linked list empty?

# File lib/hashery/linked_list.rb, line 79
def empty?
  @lookup.empty?
end
first() click to toggle source

Get value of first node.

# File lib/hashery/linked_list.rb, line 95
def first
  @head.next_node.value
end
last() click to toggle source

Get value of last node.

# File lib/hashery/linked_list.rb, line 102
def last
  @tail.prev_node.value
end
length() click to toggle source

Number of nodes.

# File lib/hashery/linked_list.rb, line 193
def length
  @lookup.length
end
Also aliased as: size
pop() click to toggle source
# 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
push(v) click to toggle source
# 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
Also aliased as: <<
queue() click to toggle source

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
shift() click to toggle source
# 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
size()
Alias for: length
to_a() click to toggle source

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
unshift(v) click to toggle source
# 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

node_delete(n) click to toggle source

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
node_join(a,b) click to toggle source

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
node_purge(n) click to toggle source

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