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