Author | Manuela Ruiz (mruiz@lcc.uma.es) |
This class represents a linked list
other_list | another LinearLinkedList object |
returns | true if this list is identical to the specified list |
# File lib/data-structures.rb, line 262 262: def ==(other_list) 263: result = false 264: if !other_list 265: other_list = LinearLinkedList.new 266: end 267: if other_list.kind_of? LinearLinkedList 268: result = (@size == other_list.size) 269: current = @first 270: other_current = other_list.first 271: while (result && current && other_current) 272: result = ((current.key == other_current.key) && (current.list == other_current.list)) 273: current = current._next 274: other_current = other_current._next 275: end 276: end 277: return result 278: end
returns | a new LinearLinkedList, identical to this one |
# File lib/data-structures.rb, line 248 248: def clone() 249: new_lllist = LinearLinkedList.new 250: current = @first 251: while current 252: new_node = current.clone 253: new_lllist.insert_node(new_node) 254: current = current._next 255: end 256: return new_lllist 257: end
key | key of the node to remove |
returns | true iff the node has been deleted, false otherwise. |
Deletes the specified node
# File lib/data-structures.rb, line 176 176: def delete_node(key) 177: previous = nil 178: current = @first 179: exists = false 180: while (current && !exists) 181: if (key == current.key) 182: exists = true 183: else 184: previous = current 185: current = current._next 186: end 187: end 188: 189: if exists 190: if !previous #Is the first node 191: @first = @first._next 192: if (@size == 1) 193: @last = nil 194: end 195: else #General case 196: if !current._next 197: @last = previous 198: end 199: previous._next = current._next 200: end 201: @size -= 1 202: result = true 203: else 204: result = false 205: end 206: return result 207: end
returns | true iff the list is empty |
# File lib/data-structures.rb, line 243 243: def empty?() 244: return !@first 245: end
returns | returns, in each invocation, the next node, in order, in the list |
# File lib/data-structures.rb, line 225 225: def get_next() 226: if @current_node == Constants::START 227: @current_node = @first 228: elsif @current_node 229: @current_node = @current_node._next 230: else 231: self.reset_iterator 232: end 233: result = @current_node 234: return result 235: end
key::key of the node we want to recover
returns | the node with the specified key. In case it does not exists, returns nil. |
# File lib/data-structures.rb, line 157 157: def get_node(key) 158: result = nil 159: current = @first 160: found = false 161: while (current && !found) 162: if (current.key == key) 163: found = true 164: result = current 165: else 166: current = current._next 167: end 168: end 169: return result 170: end
i::index ofthe node to be retrieved
returns | the node in the position i, or nil if i >= size of the list |
# File lib/data-structures.rb, line 212 212: def get_node_i(i) 213: if (i < @size) 214: j = 0 215: result = @first 216: while (j < i) 217: result = result._next 218: j += 1 219: end 220: end 221: return result 222: end
returns | the hash code for this list |
# File lib/data-structures.rb, line 281 281: def hash 282: array = self.to_array 283: hash_array = Array.new 284: array.each { |node| 285: hash_array.push node.hash 286: } 287: return hash_array.hash 288: end
n | LinearLinkedListNode to add |
returns | the inserted node or the previously existing node in case the key already exist in the list |
Inserts the node, maintaining the order of the list
# File lib/data-structures.rb, line 102 102: def insert_node(n) 103: previous = nil 104: current = @first 105: position_found = false 106: exists = false 107: while (current && !position_found && !exists) 108: if (n.key < current.key) 109: position_found = true 110: elsif (n.key == current.key) 111: exists = true 112: else 113: previous = current 114: current = current._next 115: end 116: end 117: 118: if !exists #If the node does'n exist 119: if !previous #Is the first node 120: n._next = @first 121: @first = n 122: @current_node = Constants::START 123: if (@size == 0) 124: @last = n 125: end 126: else # General case (or last to be added if !position_found) 127: if !position_found 128: @last = n 129: end 130: previous._next = n 131: n._next = current 132: end 133: 134: @size += 1 135: result = n 136: else 137: result = current 138: end 139: return result 140: end
resets the iterator used by get_next()
# File lib/data-structures.rb, line 238 238: def reset_iterator() 239: @current_node = Constants::START 240: end
returns | the nodes of the list in the form of an array |
# File lib/data-structures.rb, line 143 143: def to_array 144: result = Array.new 145: current = @first 146: while current 147: result.push current 148: current = current._next 149: end 150: 151: return result 152: end
Disabled; run with --debug to generate this.
Generated with the Darkfish Rdoc Generator 1.1.6.