Làm cách nào để triển khai danh sách được liên kết kép trong PHP?

Question

Tôi đã nhận được câu hỏi phỏng vấn vào thứ Sáu và tôi nghĩ rằng tôi đã bỏ qua nó. Câu hỏi là:

Viết một lớp xử lý danh sách liên kết kép trong PHP.

Tôi hiểu các khái niệm, và đây là đoạn code tôi đã:

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

này hoạt động ban đầu, nhưng nếu tôi thêm một yếu tố thứ hai tôi "mất" cái đầu tiên, và tôi không hiểu tại sao.

Answer 1

Bạn cần theo dõi $prev và $next trên element s, không phải danh sách. Nếu bạn muốn làm cho nó trong suốt, bạn có thể bọc mỗi element trong một hạt có con trỏ đến những cái tiếp theo và trước đó, hoặc chỉ làm cho element có những định nghĩa đó.

Cách bạn đang thực hiện ngay bây giờ, danh sách sẽ chỉ biết cái nào là element hiện tại và cái nào đến trước đó. Nhưng những gì bạn thực sự nên làm là tìm ra từ element (hoặc đậu) cái nào sẽ là cái tiếp theo hoặc trước đó.

Sửa

Kể từ khi câu hỏi này đã được nhận quan điểm thường xuyên, tôi nghĩ rằng tôi muốn thêm một mã nhỏ để giúp giải thích tốt hơn này.

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

Có tất nhiên, các phương pháp khác bạn có thể thêm; và nếu có ai quan tâm đến những người tôi có thể thêm chúng.

Answer 2

Câu trả lời đúng là: Xin lỗi, không. Nó đã được thực hiện và được bao gồm trong thư viện chuẩn PHP. http://php.net/manual/en/class.spldoublylinkedlist.php

---

Ngoài ra, chức năng bổ sung của bạn không được lấy yếu tố. Nó chỉ là $list->add('a'); Bạn đang phơi bày quá trình triển khai của mình quá nhiều.