[thelist] PHP, MySQL and Linked List

[Burhan Khalid]

Hershel Robinson wrote:
> I have a linked list structure which I am storing in a MySQL database. The
> site code is in PHP. A few tasks which the code must do:
> 
> 1 Display the nodes of the list in order (i.e. traversing the links).
> 2 Delete and Insert nodes.
> 3 Move nodes up or down one notch in the list.
> 
> I found no brilliant built-in tools to assist with this in PHP (server runs
> PHP 4.3) nor MySQL, so I wrote some simple code to handle these issues. Each
> row of the table has an ID and a NextID field. The NextID simply points to
> the ID of the next node.
> 
> The only algorithm about which I am not thrilled is the first one above, to
> display the entire list in order. The method I am using is to load the
> entire table, putting each node (and all of its relevant data) into a node
> object, an instance of a class I defined. Once the entire table is loaded,
> the code can then loop through the nodes, beginning with ID 1 (the root),
> following the links, until we come to ID 0 which means done.

I think a recursive function here would help.  I was recently working on 
a similar issue, and found that recursion solves the problem of avoiding 
to load the entire tree to do the traversing.

I had two functions, one to find the reverse path from a node (ie, all 
parents), and one to build a drop down menu with the tree.  Both used 
recursion.

Here is the findReversePath() function.  You pass it the node id that 
you want the tree for, and a reference to an array that you want the 
information returned to.

It is for a table that contains id, title, and parent (the parent id) of 
generic nodes (I made it as generic as possible).  The top level nodes 
have a parent of -1 (the root node, which doesn't exist).

function findReversePath($node,&$return)
{
   // -- First, lets find the parent for our node

   $query  = "SELECT id,title,parent FROM nodes WHERE id = ".$id.";
   $query .= "ORDER BY parent DESC";

   $result = mysql_query($query);
   if (!$result) { die($query."<br />".mysql_error()); }
   	
   $info = mysql_fetch_assoc($result);
   	
   if ($info['cat_parent'] == -1)
   {
   	//We have reached the top level category
   	$return[] = $info;
   	return $return;
   } else {
	// Find the other parents -- recursively
   	$return[] = $info;
   	findReversePath($info['parent'],$return);
   }
}

Here is a sample call :

$trail = array();
findReversePath($catid,$trail);
echo '<pre>'; print_r($trail); echo '</pre>';

I'm sure you can modify the above for your situation.

Hope this helps,
Burhan