<?php

/**

 * php实现链表

 * Date: 2018/5/18

 * Time: 下午5:59

 */

class Node

{

    public $nodeId = 0;

    public $left = 0;

    public $right = 0;

    public function __construct($nodeId, $left, $right)

    {

        $this->nodeId = $nodeId;

        $this->left = $left;

        $this->right = $right;

    }

}

class ListArr

{

    private $list = null;

    public function construct()

    {

    }

    //创造一个n长度链表

    public function createList($n)

    {

        if ($n <= 0) {

            return false;

        }

        for ($i = 0; $i < $n; $i++) {

            if ($i == 0) {

                $node = new Node(0, $n - 1, 1);

            } elseif ($i == $n - 1) {

                $node = new Node($n - 1, $n - 2, 0);

            } else {

                $node = new Node($i, $i - 1, $i + 1);

            }

            $this->list[$i] = $node;

        }

    }

    //遍历链表

    public function iteratorList()

    {

        $total = count($this->list);  //链表长度

        $strRet = '';

        for ($i = 0; $i < $total; $i++) {

            $node = $this->list[$i];

            echo  "current node : {$node->left}->{$node->nodeId}->{$node->right}\n";

        }

        echo $strRet;

    }

    //查找某一节点

    public function findNode($n)

    {

        if ($n < 0 ) {

            return false;

        }

        $total = count($this->list);

        if ($n > $total) {

            $n = $n % $total;

            $node = $this->list[$n - 1];

        } else {

            $node = $this->list[$n - 1];

        }

        echo "current Node is {$node->nodeId}  left is {$node->left} right is {$node->right}\n";

    }

}

$list = new ListArr();

$list->createList(5);

$list->findNode(3);

$list->findNode(6);

$list->iteratorList();