如何在PHP中实现双向链表？

Question

I got an interview question on Friday and I think I flunked it. The question was:

Write a class that process a double linked list in PHP.

I understand the concept, and here's the code I gave:

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'));

This works initially, but if I add a second element I "lose" the first one, and I don't understand why.

Answer 1

You need to be keeping track of $prev and $next on the elements, not the list. If you want to make it transparent, you can wrap each element in a bean that has pointers to the next and previous ones, or just make element have those by definition.

The way you're doing it right now, the list will only know which one is the current element, and which one came before that. But what you should really be doing is figuring it out from the element (or bean) which one will be the next or previous.

Edit

Since this question has been getting the occasional view, I thought I'd add a little code to help explain this better.

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 function __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;
    }
}

There are, of course, other methods you could add; and if anyone is interested in those I can add them as well.