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::Node
Public Class methods
new()
# 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
[](v)
# File lib/more/facets/linkedlist.rb, line 94
        def [](v)
                @lookup[v].value
        end
[]=(k,v)
# 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
delete(k)
# File lib/more/facets/linkedlist.rb, line 114
        def delete(k)
                n = @lookup.delete(k)
                v = n ? node_purge(n) : nil
                v
        end
each() {|n.key,n.value| ...}
# 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
empty?()
# File lib/more/facets/linkedlist.rb, line 110
        def empty?
                @lookup.empty?
        end
first()
# File lib/more/facets/linkedlist.rb, line 120
        def first
                @head.next_node.value
        end
last()
# File lib/more/facets/linkedlist.rb, line 124
        def last
                @tail.prev_node.value
        end
length()
# File lib/more/facets/linkedlist.rb, line 188
        def length
                @lookup.length
        end
pop()
# 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
push(v)
# 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
queue()
# 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
shift()
# 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
to_a()
# 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
unshift(v)
# 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