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

목록이 아닌 element에 $prev 및 $next을 추적해야합니다. 그것을 투명하게 만들고 싶다면 각각의 element을 다음 또는 이전 포인터를 가진 빈에 랩핑하거나 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');이어야합니다. 구현을 너무 많이 노출시키고 있습니다.