From: Dave Cantrell <ruby-talk@...>
Date: 2006-02-15T14:33:00+09:00
Subject: Re: tree structures

> How would you represent a linked list in Ruby?

Like David said, probably not at all, using Array.

BUT... just for grins (and to actually, honest to god, learn about one 
of those nifty data structures I always had abstracted out for me in 
other languages) when I first picked up Ruby a few weeks back I decided 
to implement a non-Array-based linked list.

Looking back over it, it's ugly as hell and I'd probably do quite a bit 
of it differently now. But as a learning exercise in Ruby it taught me a 
fair bit. Especially when I pulled the node traversal out into a 
separate method to pass blocks into.

(Speaking of ugly, it appears in my haste I made a node traversal nested 
inside a node traversal, for absolutely no good reason. Ick.)

So, purely for BS fun, here's my crappy non-Array linked list, in all 
it's ugly glory.

-dave

=====linkedlist.rb
#########################################################
class Node
	attr_reader :name
	attr_accessor :next
	
	def initialize(name)
		@name = name
	end

	def to_s
		@name
	end
	
end


#########################################################
class LinkedList

	attr_reader :length

	def initialize()
		@headNode = nil
		@tailNode = nil
		@length   = 0
	end

	# Returns the first node in the list.
	def head
		@headNode
	end

	# Returns the last node in the list.
	def tail
		@tailNode
	end
	
	# Adds a new node to the list.
	# If no nodes exist, sets the root node and last
	#		node to the new node.
	# If nodes exist, appends to the last node and
	#   resets the last node to the new node.
	def add(aNode)
		if !@headNode
			@headNode = aNode
			@tailNode = @headNode
		else
			@tailNode.next = aNode
			@tailNode = @tailNode.next
		end
		@length += 1
	end

	# Deletes the node from the list that matches
	#		the node passed in, and return it.
	# Match is based on object.id equality.
	def delete(aNode)
		prev, curr = nil
		traverse do |node|
			prev, curr = curr, node
			if node === aNode
				# need to rewire the prev/next if they exist
				if prev and curr.next
					prev.next = curr.next
				else
					prev = nil  # deleting head node
				end
				# reset head and tail nodes
				# TODO: This is SLOPPY and should be re-written
				# TEST: Run this way with 1m nodes, then re-write
				#       and re-run test, checking performance gain
				#       from not re-iterating over all nodes with
				#       each delete
				traverse do |node|
					
				end
				@length -= 1
				return curr
			end
		end
	end

	# Iterates over all nodes starting at root
	# 	and yields each node encountered.
	def traverse
		currNode = @headNode
		yield(currNode)  # have to yeild the first node first
		if !(@headNode === @tailNode)
			while currNode.next
				currNode = currNode.next
				yield(currNode)
			end
		end
	end

	def shownodes
		traverse { |node| print node, (node.next ? " -> " : "\n") }
	end
	
end # LinkedList



########################################################


list = LinkedList.new

n1 = Node.new("node1")
n2 = Node.new("node2")
n3 = Node.new("node3")
n4 = Node.new("node4")

puts "adding nodes"
p list.length
list.add n1
list.add n2
list.add n3
list.add n4
p list.length

list.shownodes


puts "deleting nodes"
puts list.delete(n3)
puts list.delete(n1)
puts list.delete(n2)
puts list.delete(n4)

list.shownodes