Hace un tiempo comencé a desarrollar un sitio que requería de una estructura de árbol para recorrer las categorías.

Después de buscar un tiempo, no pude encontrar ninguna API que tenga un buen desempeño y sea relativamente amigable.

Es por eso, que decidí escribirla por mi mismo. Dado mi trasfondo de Java (y el idílico romance con sus colecciones) tomé como decisión de diseño asemejarlo lo más posible a dichas estructuras.

Hoy cuelgo la primera oficialmente libre de bugs (eso espero). Como el nombre del post indica, es una Linked List (Lista Enlazada) totalmente implementada en PHP y con la misma interfaz que la símil de Java. Por lo tanto tenemos los mismos métodos para accederla, resultando los mismos resultados.

Espero dentro de poco poder subir el árbol, y si sigue en pié el proyecto, algunos grafos dirigidos.

Por último, le pido a cualquier usuario que si reconocen algun problema o bug me lo comuniquen así sigo mejorándola.

<?php

/**
 * LinkedList
 * @author Santiago Basulto
 * @copyright Xingular.net
 * @version 2009
 * @access public
 */

class LinkedList extends ArrayObject {
	private $_array;

	public function __construct()
	{
  		if(is_array(func_get_arg(0)))
		{
			$this->_array = func_get_arg(0);
		}
  		else{
			$this->_array = func_get_args();
		}
		parent::__construct($this->_array);
	}

	public function each($callback)
	{
		$iterator = $this->getIterator();
		while($iterator->valid())
		{
			$callback($iterator->current());
			$iterator->next();
		}
	}

	public function add()
	{
		$parametros =func_get_args();
		if(func_num_args()==2)
		{
			$this->addPosition($parametros[0],$parametros[1]);
		}
		else{
			if(func_num_args()==1)
            {
				$this->addFirst($parametros[0]);
            }
		}
	}
	public function addFirst($object)
	{
		if(isset($object))
		{
   			array_unshift($this->_array,$object);
   			parent::__construct($this->_array);
		}
	}
	public function addLast($object)
	{
		$this->_array[] = $object;
  		parent::__construct($this->_array);
	}

	public function addPosition($index,$object)
	{
		if(count($this->_array)>=$index)
		{
			$aux = array();
			for($i=0;$i<$index;$i++)
			{
				$aux[] = array_shift($this->_array);
			}
			$aux[]=$object;
			$this->_array=array_merge($aux,$this->_array);
			unset($aux);
			parent::__construct($this->_array);
		}
	}
	public function remove($index)
	{
		if($index<$this->size())
		{
                 array_splice($this->_array,$index,1);
                 parent::__construct($this->_array);
		}
	}

	public function removeObject($object)
	{
		$index = array_search($object,$this->_array);
		if($index!=false)
		{
			array_splice($this->_array,$index,1);
                        parent::__construct($this->_array);
                        return true;
		}
		return false;
	}

	public function clear()
	{
		$nuevo = array();
		$this->_array = $nuevo;
		parent::__construct($this->_array);
	}
	// Clone es una palabra reservada del lenguaje.
	//agregue el siguiente método por si alguien no lo sabe
	public function copy()
	{
		$copia = clone $this;
		return $copia;
	}

	public function without()
	{
		$args = func_get_args();
		return array_values(array_diff($this->_array,$args));
	}

	public function element()
	{
		return $this->_array[0];
	}

	public function indexOf($value)
	{
		return array_search($value,$this->_array);
	}

	public function contains($value)
	{
		return ($this->indexOf($value)!=FALSE);
	}

	public function inspect()
	{
		echo "<pre>".print_r($this->_array, true)."</pre>";
	}

	public function last()
	{
		return $this->_array[count($this->_array)-1];
	}

	public function reverse($applyToSelf=false)
	{
		if (!$applyToSelf)
			return array_reverse($this->_array);
		else
		{
			$_array = array_reverse($this->_array);
			$this->_array = $_array;
			parent::__construct($this->_array);
			return $this->_array;
		}
	}

	// En php se devuelve una copia, no una referencia. Para devolver una referencia (malisima practica) es necesario
	// usar el operador Referencia ( & )
	public function toArray()
	{
		return $this->_array;
	}

	public function shift()
	{
		$_element = array_shift($this->_array);
		parent::__construct($this->_array);
		return $_element;
	}
	public function removeFirst()
	{
		return $this->shift();
	}

	public function pull()
	{
		return $this->shift();
	}

	public function pullFirst()
	{
		return $this->shift();
	}

	public function pullLast()
	{
		return $this->pop();
	}

	public function pop()
	{
		$_element = array_pop($this->_array);
		parent::__construct($this->_array);
		return $_element;
	}

	public function size()
	{
		return count($this->_array);
	}

	public function set($index,$value)
	{
		if($index<$this->size())
		{
                        $this->_array[$index]=$value;
 			parent::__construct($this->_array);
		}
		return false;
	}

	public function get($index)
	{
		if($index<$this->size() && is_int($index))
		{
			return $this->_array[$index];
		}
	}

	public function getFirst()
	{
		return $this->_array[0];
	}

	public function peek()
	{
		return $this->getFirst();
	}

	public function peekFirst()
	{
		return $this->getFirst();
	}

	public function peekLast()
	{
		return $this->getLast();
	}

	public function getLast()
	{
		return $this->_array[$this->size()-1];
	}

}

?>

Para descargar:
proyecto en google-code