php循环链表实现

Question

我写了这个类来实现链表:

class Node{
    public $data;
    public $link;

    function __construct($data, $next = NULL){
        $this->data = $data;
        $this->link = $next;
    }    
}

class CircularLinkedList{
    private $first;
    private $current;
    private $count;

    function __construct(){
        $this->count = 0;
        $this->first = null;
        $this->current = null;
    }

    function isEmpty(){
        return ($this->first == NULL);
    }

    function push($data){
        //line 30
        $p = new Node($data, $this->first);
        if($this->isEmpty()){
            $this->first = $p;
            $this->current = $this->first;
        }
        else{           
            $q = $this->first;
            //line 38
            while($q->link != $this->first)
                $q = $q->link;
            $q->link = $p;    
        }
        $this->count++;       
    }

    function find($value){
        $q = $this->first;
        while($q->link != null){
            if($q->data == $value)
                $this->current = $q;
            $q = $q->link;    
        }
        return false;      
    }

    function getNext(){
        $result = $this->current->data;
        $this->current = $this->current->link;
        return $result;        
    }
}  

但是当我尝试插入一些值(value)时，

$ll = new CircularLinkedList();

$ll->push(5);
$ll->push(6);
$ll->push(7);
$ll->push(8);
$ll->push(9);
$ll->push(10);

//$ll->find(7);

for($j=0;$j<=30;$j++){
    $result = $ll->getNext();
    echo $result."<br />";
}

脚本在第二次推送时挂起并给出 max_execution_time 错误。

如上所示，如果我将 calss 的第 30 和 38 两行更改为普通的 LinkedList，则效果很好。 (通过删除最后一个节点链接到第一个节点)。

那么问题是什么，如何解决呢？

更新:通过将 push() 函数更改为此，它可以作为线性链表正常工作:

function push($data){
    $p = new Node($data);
    if($this->isEmpty()){
        $this->first = $p;
        $this->current = $this->first;
    }
    else{
        $q = $this->first;
        while($q->link != null)
            $q = $q->link;
        $q->link = $p;    
    }
    $this->count++;       
}

Answer 1

对于线性链表 - 更改以下内容:

      function push($data){

       if($this->isEmpty()){
         $this->first   = new Node($data);
         $this->current = $this->first;
         $this->count++;
       }
       else{

        $this->current->link = new Node($data);
        $this->current = $this->current->link;
        $this->count++;

      }

    }

这个结构产生:

    CircularLinkedList Object
    (
      [first:CircularLinkedList:private] => Node Object
      (
        [data] => 2
        [link] => Node Object
            (
                [data] => 10
                [link] => Node Object
                    (
                        [data] => 3
                        [link] => Node Object
                            (
                                [data] => 9
                                [link] => 
                            )

                    )

            )

    )

    [current:CircularLinkedList:private] => Node Object
    (
        [data] => 9
        [link] => 
    )

    [count:CircularLinkedList:private] => 4
 )

对于通告 - 更改为:

     function push($data){

       if($this->isEmpty()){
         $this->first   = new Node($data);
         $this->current = $this->first;
         $this->count++;
       }
       else{

        $this->current->link = new Node($data, $this->first);
        $this->current = $this->current->link;
        $this->count++;

      }

    }

这个结构产生:

    CircularLinkedList Object
    (
      [first:CircularLinkedList:private] => Node Object
      (
        [data] => 2
        [link] => Node Object
            (
                [data] => 10
                [link] => Node Object
                    (
                        [data] => 3
                        [link] => Node Object
                            (
                                [data] => 9
                                [link] => Node Object
       *RECURSION*
                            )

                    )

            )

       )

    [current:CircularLinkedList:private] => Node Object
    (
        [data] => 9
        [link] => Node Object
            (
                [data] => 2
                [link] => Node Object
                    (
                        [data] => 10
                        [link] => Node Object
                            (
                                [data] => 3
                                [link] => Node Object
         *RECURSION*
                            )

                    )

            )

     )

    [count:CircularLinkedList:private] => 4
   )