¿Cómo implementar una lista doblemente enlazada en PHP?

Question

Recibí una pregunta de entrevista el viernes y creo que la suspendí. La pregunta era:

Escriba una clase que procese una lista de doble enlace en PHP.

entiendo el concepto, y aquí está el código que di:

class element { 
private $current; 
public function __construct($e) { 
    $this->current = $e; 
} 
// method 
// etc.. 
} 

class doublelist 
{ 
    private $prev; 
    private $next; 
    private $current; 
    private $list; 
    public function add(element $e) { 
    if($this->current == NULL) { 
    $this->prev = $this->current; 
    } 
    $this->current = $e; 
    } 
} 

$list = new doublelist(); 
$list->add(new element('a')); 
$list->add(new element('b')); 

Esto funciona al principio, pero si agrego un segundo elemento que "perder" el primero, y yo no entiendo por qué.

Answer 1

Debe realizar un seguimiento de $prev y $next en el element s, no en la lista. Si desea que sea transparente, puede ajustar cada element en un bean que tenga punteros a los siguientes y anteriores, o simplemente haga que element los tenga por definición.

La forma en que lo está haciendo ahora, la lista solo sabrá cuál es la actual element, y cuál vino antes. Pero lo que realmente debería estar haciendo es averiguarlo desde el element (o frijol) cuál será el siguiente o el anterior.

Editar

Dado que esta cuestión ha estado recibiendo la vista de vez en cuando, pensé que me gustaría añadir un poco de código para ayudar a explicar esto mejor.

class DoublyLinkedList { 
    private $start = null; 
    private $end = null; 

    public function add(Element $element) { 
     //if this is the first element we've added, we need to set the start 
     //and end to this one element 
     if($this->start === null) { 
      $this->start = $element); 
      $this->end = $element; 
      return; 
     } 

     //there were elements already, so we need to point the end of our list 
     //to this new element and make the new one the end 
     $this->end->setNext($element); 
     $element->setPrevious($this->end); 
     $this->end = $element; 
    } 

    public function getStart() { 
     return $this->start; 
    } 

    public function getEnd() { 
     return $this->end; 
    } 
} 

class Element { 
    private $prev; 
    private $next; 
    private $data; 

    public __construct($data) { 
     $this->data = $data; 
    } 

    public function setPrevious(Element $element) { 
     $this->prev = $element; 
    } 

    public function setNext(Element $element) { 
     $this->next = $element; 
    } 

    public function setData($data) { 
     $this->data = $data; 
    } 
} 

Existen, por supuesto, otros métodos que podría agregar; y si alguien está interesado en ellos, puedo agregarlos también.

Answer 2

La respuesta correcta es: Disculpe, no. Ya se ha hecho y está incluido en la biblioteca estándar de PHP. http://php.net/manual/en/class.spldoublylinkedlist.php

---

Además, su función de complemento no debe tener un elemento. Simplemente debería ser $list->add('a');. Expone demasiado su implementación.