Class LinkedList
In: lib/more/facets/linkedlist.rb
Parent: Object

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

Enumerable

Classes and Modules

Class LinkedList::Node

Public Class methods

[Source]

# 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

[Source]

# File lib/more/facets/linkedlist.rb, line 94
        def [](v)
                @lookup[v].value
        end

[Source]

# 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

[Source]

# File lib/more/facets/linkedlist.rb, line 114
        def delete(k)
                n = @lookup.delete(k)
                v = n ? node_purge(n) : nil
                v
        end

[Source]

# 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

[Source]

# File lib/more/facets/linkedlist.rb, line 110
        def empty?
                @lookup.empty?
        end

[Source]

# File lib/more/facets/linkedlist.rb, line 120
        def first
                @head.next_node.value
        end

[Source]

# File lib/more/facets/linkedlist.rb, line 124
        def last
                @tail.prev_node.value
        end

[Source]

# File lib/more/facets/linkedlist.rb, line 188
        def length
                @lookup.length
        end

[Source]

# 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

[Source]

# 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

[Source]

# 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

[Source]

# 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

[Source]

# 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

[Source]

# 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

[Validate]