如何在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上的element s，而不是列表。如果你想使它透明，你可以将每个element包装在一个指向下一个和前一个指针的bean中，或者只是让element具有这些定义。

你现在这样做的方式，列表只会知道哪一个是当前的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 __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/en/class.spldoublylinkedlist.php

---

此外，你的add函数不应该带一个元素。它应该只是$list->add('a');你正在暴露你的实现太多。