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

Question

我在周五收到一道面试题，我想我没及格。问题是:

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

我理解这个概念，这是我给出的代码:

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

这最初有效，但如果我添加第二个元素，我会“丢失”第一个元素，我不明白为什么。

Answer 1

您需要跟踪元素 上的$prev 和$next，而不是列表。如果你想让它透明，你可以将每个 element 包装在一个 bean 中，该 bean 具有指向下一个和上一个的指针，或者只是让 element 具有定义的那些。

按照您现在的做法，列表将只知道当前的元素，以及之前的元素。但您真正应该做的是从 element(或 bean)中找出下一个或上一个。

编辑

由于这个问题偶尔会出现，我想我应该添加一些代码来帮助更好地解释这个问题。

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

当然，您还可以添加其他方法；如果有人对这些感兴趣，我也可以添加。