Continuing my data structures thoughts from previous posts, I’ve created a linked list example.

/*
 * Node - a basic link node.
 */
class Node {
	var $id;
	var $next;
	/*
	 *
	 */
	function __construct($id)
	{
		$this->id = $id;
	}
}
$a = new Node("mark");
var_dump($a);
$b = $a->next = new Node("wes");
var_dump($b);
$c = $a->next->next = new Node("mj");
var_dump($c);
$d = $a->next->next->next = new Node("bruce");
var_dump($d);
$d->next = $b;
var_dump($d);

echo " //loop through the list and see what's there...";
$current = $a;
$max = 5;
while($current && $max)
{
	var_dump($current);
	$max--;
	$current = $current->next;
}

echo "// implement Floyd's circular loop as seen at http://ostermiller.org/find_loop_singly_linked_list.html ";
function is_looping($start_node)
{
	$current = $fast_node1 = $fast_node2 = $start_node;
	while($current && $fast_node1 = $fast_node2->next && $fast_node2 = $fast_node1->next)
	{
		var_dump($current);
		if($current == $fast_node1 || $current == $fast_node2)
			return TRUE;

		$current = $current->next;
 	}
	return 0;
}

if(is_looping($a)) echo "LOOP FOUND!";
else echo "NO LOOP!";

if(is_looping(new Node('dud'))) echo "LOOP FOUND!";
else echo "NO LOOP!";

Try it out at: http://www.randymelder.com/test/linkedlist1.php

Thoughts?