PHP 实现链表

设计链表，链表的每个节点都是一个对象，每个节点都应具备一个val和一个next引用。

//链表节点
class Node{
    public $val;
    public $next;

    function __construct($val = NULL,$next = NULL){
        $this->val = $val;
        $this->next = $next;
    }
}
//链表
class MyLinkedList {
    public $head; //存储头部
    public $size; //存储大小
    /**
     * 初始化链表
     */
    function __construct() {
        $this->head = new Node(); //初始化链表的时候头部应为一个节点
        $this->size = 0; //初始化默认的大小为0
    }

    /**
     * 获取链表的一个节点，如果不存在或者大于链表长度则返回-1
     * @param Integer $index
     * @return Integer
     */
    function get($index) {
        if($index > $this->size - 1) return -1;
        $prev = $this->head->next;
        for($i=0;$i<=$index;$i++){
            if($i == $index){
                return $prev->val;
            }
            $prev = $prev->next; //循环链表
        }
        return -1;
    }

    /**
     * 设置链表的头部节点
     * @param Integer $val
     * @return NULL
     */
    function addAtHead($val) {
        $prev = $this->head;
        $prev->next = new Node($val,$prev->next);
        $this->size++;
    }

    /**
     * 设置链表的尾部 循环整个链表的大小后后添加
     * @param Integer $val
     * @return NULL
     */
    function addAtTail($val) {
        $size = $this->size;$prev = $this->head;
        for($i = 0;$i < $size;$i++){
            $prev = $prev->next;
        }
        $prev->next = new Node($val,$prev->next);
        $this->size++;
    }

    /**
     * 在指定的节点后面添加新的节点，循环到指定节点后直接添加节点引用
     * @param Integer $index
     * @param Integer $val
     * @return NULL
     */
    function addAtIndex($index, $val) {
        if($index > $this->size) return -1;
        $prev = $this->head;
        for($i=0;$i<$index;$i++){
            $prev = $prev->next;
        }
        $prev->next = new Node($val,$prev->next);
        $this->size++;
    }

    /**
     * 删除节点，将此节点的next引用越过要删除的节点即可
     * @param Integer $index
     * @return NULL
     */
    function deleteAtIndex($index) {
        if($index > $this->size - 1) return -1;
        $prev = $this->head;
        for($i = 0;$i<=$index;$i++){
            if($i == $index){
                $prev->next = $prev->next->next;
            }
            $prev = $prev->next;
        }
        $this->size--;
    }
}