php实现单链表(静态链表)_PHP_编程开发_程序员俱乐部

<?php
    /*
     * 单链表的PHP实现
     *
     * @author zhaojiangwei
     * @since 2011/10/20
     */

    //结点类
    class Node{
        private $next = NULL; //下一个结点指针
        private $data = NULL; //数据
   
        public function Node($data, $next = NULL){
            $this->data = $data;
            $next && $this->next = $next;
        }
        public function getData(){
            return $this->data;
        }
        public function setData($data){
            $this->data = $data;
        }
        public function getNext(){
            return $this->next;
        }
        public function setNext($next){
            $this->next = $next;
        }
    }

    //单链表类
    class LinkList{
        private $data_list = NULL; //结点集          

        public function LinkList($data = false){
            $this->data_list = array();
            $title = new Node(NULL);
            $this->data_list[] = $title;
          
            if($data){
                if(is_array($data)){
                    $this->addMoreData($data);
                }else{
                    $this->addData($data);
                }
            }
        }
        //返回第N个结点的值
        public function getNodeByNumber($number){
            return $this->data_list[$this->findKeyByNumber($number)]->getData();
        }
        //添加一组结点
        public function addMoreData($datas){
            foreach($datas as $value){
                $this->addData($value);
            }
        }
        //添加结点统一入口,供外面调用
        //$number 添加在第几个结点的后面
        public function addData($data, $number = false){
            $node = new Node($data);
            if($number === FALSE || $number == count($this->data_list)){
                $this->insertLastNode($node);
            }elseif($number > count($this->data_list)){
                return false;
            }else{
                $this->insertNode($node, $number);
            }
        }
        //插入一个结点到最后
        private function insertLastNode($node){
                $node->setNext(NULL);             
                $lastKey = $this->findLastNode();
                $insert_key = $this->insertNodeIntoArray($node);
                $this->data_list[$lastKey]->setNext($insert_key);
        }    
        //插入一个结点
        private function insertNode($node, $number){
            $insert_number = $this->findKeyByNumber($number);    
            $node->setNext($this->data_list[$insert_number]->getNext());
            $insert_key = $this->insertNodeIntoArray($node);
            $this->data_list[$insert_number]->setNext($insert_key);
        }
        //查找第N个结点对应的数组key
        private function findKeyByNumber($number){
            $i = $key = 0;

            while($i < $number){
                $key = $this->data_list[$key]->getNext();
                $i ++;
            }
         
            return $key;
        }
        //将结点加入数组
        private function insertNodeIntoArray($node){
            $this->data_list[] = $node;     
            return $this->getLastKey();
        }
        //删除结点
        public function deleteNode($number){
            if($number == 0 || $number > count($this->data_list)){
                return false;
            }

            $pre_key = $this->findKeyByNumber($number - 1);
            $key = $this->data_list[$pre_key]->getNext();

          $this->data_list[$pre_key]->setNext($this->data_list[$key]->getNext());
            unset($this->data_list[$key]);
        }

        //查找某结点的前一个结点
        private function getPreNodeKey($key){
            foreach($this->data_list as $k=>$v){
                if($v->getNext() == $key){
                    return $k;  
                }
            }
            return false;
        }

        //打印链表
        public function getData_list(){
            return $this->data_list;
        }

        //返回数组的最后一个键
        private function getLastKey(){
            end($this->data_list);
            return key($this->data_list);
        }

        //判断某个键值是否存在
        private function ifExistKey($key){
            if(array_key_exists($key, $this->data_list)){
                return true;
            }          
            return false;
        }
        //查找尾结点
        public function findLastNode(){
            foreach($this->data_list as $key=>$value){
                if($value->getNext() === NULL){
                    return $key;
                }
            }
        }
    }
?>