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

Question

我周五收到了一个面试问题,我认为我不及格了.问题是:

编写一个在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对elementS,不在名单.如果你想让它变得透明,你可以将每个包装element在一个指向下一个和前一个指针的bean中,或者element根据定义制作它们.

你现在这样做的方式,列表只会知道哪一个是当前的element,哪一个是在此之前.但你应该做的是从element(或豆)中找出它将是下一个或前一个.

编辑

由于这个问题偶尔会得到,我想我会添加一些代码来帮助解释这个问题.

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

当然,还有其他方法可以添加; 如果有人对那些我感兴趣,我也可以添加它们.

Answer 2

在编写任何代码之前，告诉他们 已经完成并且已包含在PHP标准库中。 http://php.net/manual/zh/class.spldoublylinkedlist.php

另外，您的add函数不应包含任何元素。应该只是$list->add('a'); 您正在过多地暴露您的实现。