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.
[](v)
click to toggle source
67: def [](v)
68: @lookup[v].value
69: end
[]=(k,v)
click to toggle source
71: def []=(k,v)
72: if @lookup.has_key?(k)
73: @lookup[k].value = v
74: else
75: n = Node.new(k,v,@head,@head.next_node)
76: node_join(n,@head.next_node)
77: node_join(@head,n)
78: @lookup[k] = n
79: end
80: v
81: end
delete(k)
click to toggle source
87: def delete(k)
88: n = @lookup.delete(k)
89: v = n ? node_purge(n) : nil
90: v
91: end
each()
click to toggle source
165: def each
166: n = @head
167: while (n = n.next_node) and n != @tail
168: yield(n.key,n.value)
169: end
170: end
empty?()
click to toggle source
83: def empty?
84: @lookup.empty?
85: end
first()
click to toggle source
93: def first
94: @head.next_node.value
95: end
last()
click to toggle source
97: def last
98: @tail.prev_node.value
99: end
length()
click to toggle source
161: def length
162: @lookup.length
163: end
pop()
click to toggle source
122: def pop
123: k = @tail.prev_node.key
124: n = @lookup.delete(k)
125: node_delete(n) if n
126: end
push(v)
click to toggle source
128: def push(v)
129: if @lookup.has_key?(v)
130: n = @lookup[v]
131: node_delete(n)
132: node_join(@tail.prev_node,n)
133: node_join(n,@tail)
134: else
135: n = Node.new(v,v,@tail.prev_node,@tail)
136: node_join(@tail.prev_node,n)
137: node_join(n,@tail)
138: @lookup[v] = n
139: end
140: v
141: end
queue()
click to toggle source
143: def queue
144: r = []
145: n = @head
146: while (n = n.next_node) and n != @tail
147: r << n.key
148: end
149: r
150: end
shift()
click to toggle source
101: def shift
102: k = @head.next_node.key
103: n = @lookup.delete(k)
104: node_delete(n) if n
105: end
to_a()
click to toggle source
152: def to_a
153: r = []
154: n = @head
155: while (n = n.next_node) and n != @tail
156: r << n.value
157: end
158: r
159: end
unshift(v)
click to toggle source
107: def unshift(v)
108: if @lookup.has_key?(v)
109: n = @lookup[v]
110: node_delete(n)
111: node_join(n,@head.next_node)
112: node_join(@head,n)
113: else
114: n = Node.new(v,v,@head,@head.next_node)
115: node_join(n,@head.next_node)
116: node_join(@head,n)
117: @lookup[v] = n
118: end
119: v
120: end
![[+]](./images/find.png "show/hide quicksearch")