Class: LinkedList

Inherits:
Object show all
Includes:
Enumerable
Defined in:
lib/more/facets/linkedlist.rb

Overview

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.

Defined Under Namespace

Classes: Node

Instance Method Summary collapse

Methods included from Enumerable

#**, #accumulate, cart, cartesian_product, #cartesian_product, #cluster_by, #collect_if, #collect_with_index, combinations, #combos, #commonality, #compact_collect, #count, #divide, #each_by, #each_combination, #each_combo, #each_pair, #each_permutation, #eachn, #elementwise, #entropy, #every, #every!, #filter_collect, #frequency, #group_by, #ideal_entropy, #inject!, #injecting, #map_send, #mash, #mode, #modulate, #none?, #nonuniq, #occur, #one?, #permutation, #permutation_number, #probability, #split, #sum, #threaded_map, #threaded_map_send, #to_elem, #to_h, #to_hash, #uniq_by

Constructor Details

#initialize ⇒ LinkedList 



79
80
81
82
83
84
 
# File 'lib/more/facets/linkedlist.rb', line 79

def initialize
        @head = Node.new
        @tail = Node.new
        @lookup = Hash.new
        node_join(@head,@tail)
end

Instance Method Details

#[](v) ⇒ Object 



86
87
88
 
# File 'lib/more/facets/linkedlist.rb', line 86

def [](v)
        @lookup[v].value
end

#[]=(k, v) ⇒ Object 



90
91
92
93
94
95
96
97
98
99
100
 
# File 'lib/more/facets/linkedlist.rb', line 90

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) ⇒ Object 



106
107
108
109
110
 
# File 'lib/more/facets/linkedlist.rb', line 106

def delete(k)
        n = @lookup.delete(k)
        v = n ? node_purge(n) : nil
        v
end

#each ⇒ Object 



184
185
186
187
188
189
 
# File 'lib/more/facets/linkedlist.rb', line 184

def each
        n = @head
        while (n = n.next_node) and n != @tail
                yield(n.key,n.value)
        end
end

#empty? ⇒ Boolean 



102
103
104
 
# File 'lib/more/facets/linkedlist.rb', line 102

def empty?
        @lookup.empty?
end

#first ⇒ Object 



112
113
114
 
# File 'lib/more/facets/linkedlist.rb', line 112

def first
        @head.next_node.value
end

#last ⇒ Object 



116
117
118
 
# File 'lib/more/facets/linkedlist.rb', line 116

def last
        @tail.prev_node.value
end

#length ⇒ Object 



180
181
182
 
# File 'lib/more/facets/linkedlist.rb', line 180

def length
        @lookup.length
end

#pop ⇒ Object 



141
142
143
144
145
 
# File 'lib/more/facets/linkedlist.rb', line 141

def pop
        k = @tail.prev_node.key
        n = @lookup.delete(k)
        node_delete(n) if n
end

#push(v) ⇒ Object 



147
148
149
150
151
152
153
154
155
156
157
158
159
160
 
# File 'lib/more/facets/linkedlist.rb', line 147

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 ⇒ Object 



162
163
164
165
166
167
168
169
 
# File 'lib/more/facets/linkedlist.rb', line 162

def queue
        r = []
        n = @head
        while (n = n.next_node) and n != @tail
                r << n.key
        end
        r
end

#shift ⇒ Object 



120
121
122
123
124
 
# File 'lib/more/facets/linkedlist.rb', line 120

def shift
        k = @head.next_node.key
        n = @lookup.delete(k)
        node_delete(n) if n
end

#to_a ⇒ Object 



171
172
173
174
175
176
177
178
 
# File 'lib/more/facets/linkedlist.rb', line 171

def to_a
        r = []
        n = @head
        while (n = n.next_node) and n != @tail
                r << n.value
        end
        r
end

#unshift(v) ⇒ Object 



126
127
128
129
130
131
132
133
134
135
136
137
138
139
 
# File 'lib/more/facets/linkedlist.rb', line 126

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