如何在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');你正在暴露你的實現太多。