Basic Linked List Example

by randy melder @ gmail.com

Find documentation for this example at: http://www.randymelder.com/2009/12/06/php-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))
	{
		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!";

$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);
if(is_looping($a)) echo "
LOOP FOUND!";
else echo "
NO LOOP!";


// Let's see a trivial implementation output...
object(Node)#1 (2) {
  ["id"]=>
  string(4) "mark"
  ["next"]=>
  NULL
}
object(Node)#2 (2) {
  ["id"]=>
  string(3) "wes"
  ["next"]=>
  NULL
}
object(Node)#3 (2) {
  ["id"]=>
  string(2) "mj"
  ["next"]=>
  NULL
}
object(Node)#4 (2) {
  ["id"]=>
  string(5) "bruce"
  ["next"]=>
  NULL
}
object(Node)#4 (2) {
  ["id"]=>
  string(5) "bruce"
  ["next"]=>
  object(Node)#2 (2) {
    ["id"]=>
    string(3) "wes"
    ["next"]=>
    object(Node)#3 (2) {
      ["id"]=>
      string(2) "mj"
      ["next"]=>
      *RECURSION*
    }
  }
}

 //loop through the list and see what's there...object(Node)#1 (2) {
  ["id"]=>
  string(4) "mark"
  ["next"]=>
  object(Node)#2 (2) {
    ["id"]=>
    string(3) "wes"
    ["next"]=>
    object(Node)#3 (2) {
      ["id"]=>
      string(2) "mj"
      ["next"]=>
      object(Node)#4 (2) {
        ["id"]=>
        string(5) "bruce"
        ["next"]=>
        *RECURSION*
      }
    }
  }
}
object(Node)#2 (2) {
  ["id"]=>
  string(3) "wes"
  ["next"]=>
  object(Node)#3 (2) {
    ["id"]=>
    string(2) "mj"
    ["next"]=>
    object(Node)#4 (2) {
      ["id"]=>
      string(5) "bruce"
      ["next"]=>
      *RECURSION*
    }
  }
}
object(Node)#3 (2) {
  ["id"]=>
  string(2) "mj"
  ["next"]=>
  object(Node)#4 (2) {
    ["id"]=>
    string(5) "bruce"
    ["next"]=>
    object(Node)#2 (2) {
      ["id"]=>
      string(3) "wes"
      ["next"]=>
      *RECURSION*
    }
  }
}
object(Node)#4 (2) {
  ["id"]=>
  string(5) "bruce"
  ["next"]=>
  object(Node)#2 (2) {
    ["id"]=>
    string(3) "wes"
    ["next"]=>
    object(Node)#3 (2) {
      ["id"]=>
      string(2) "mj"
      ["next"]=>
      *RECURSION*
    }
  }
}
object(Node)#2 (2) {
  ["id"]=>
  string(3) "wes"
  ["next"]=>
  object(Node)#3 (2) {
    ["id"]=>
    string(2) "mj"
    ["next"]=>
    object(Node)#4 (2) {
      ["id"]=>
      string(5) "bruce"
      ["next"]=>
      *RECURSION*
    }
  }
}

// implement Floyd's circular loop as seen at http://ostermiller.org/find_loop_singly_linked_list.html 
LOOP FOUND!
NO LOOP!object(Node)#5 (2) {
  ["id"]=>
  string(4) "mark"
  ["next"]=>
  NULL
}
object(Node)#1 (2) {
  ["id"]=>
  string(3) "wes"
  ["next"]=>
  NULL
}
object(Node)#6 (2) {
  ["id"]=>
  string(2) "mj"
  ["next"]=>
  NULL
}
object(Node)#7 (2) {
  ["id"]=>
  string(5) "bruce"
  ["next"]=>
  NULL
}

NO LOOP!