PHP数据结构之——链表

链表是一种在逻辑上连续、有序的数据存储结构（在物理存储单元上非连续非有序）。在我大学的时候，学习C++的数据结构课程时，最先接触的就是链表（大学是学渣别喷...）

那么链表是怎样的一种结构呢？

用“形象的”文字来描述就是：

node_1->node_2->node_3->node_4->...->node_n ， 每一个node包含一些存储的数据

引用百度百科的图片：

链表就是这么个东西。那么链表有几种类型呢？基本型链表大致可以分成以下几种：

1，单向链表

2，双向链表

3，单向循环链表

4，双向循环链表

5，十字链表（也可以划分为有向图）

那么链表在php是如何实现的呢？话不多说，直接上代码（一个双向循环链表的样例，代码low勿喷）

LinkedList.php

<?php

class Node {
    public $id;
    public $left;
    public $right;

    public function __construct($id) {
        $this->id = $id;
    }

    //创建节点的左右节点关系
    public function linkedNode($left_id, $right_id) {
        $this->left = $left_id;
        $this->right = $right_id;
        return true;
    }
}

class LinkedList {
    public $id;
    public $_list;

    public function __construct($id) {
        $this->id = $id;
    }

    //建立n个节点的双向链表
    public function createList($n) {
        if($n == 0) {
            return false;
        } else {
            for($i = 0; $i < $n; $i ++) {
                $node[$i] = new Node($i);
                if($i == 0) {
                    $node[$i]->linkedNode($n-1, 1);
                } elseif($i == $n-1) {
                    $node[$i]->linkedNode($i-1, 0);
                } else {
                    $node[$i]->linkedNode($i-1, $i+1);
                }
            }
        }
        $this->_list = $node;
        return $this->_list; 
    }

    //从任一节点开始遍历整条链（可以选择方向）
    public function iterateList($id = 0) {
        $list = $this->_list;
        $count = 0 ;
        $total = count($list);
        while($count < $total) {
            if($id >= $total) {
                echo $list[$id-$total]->id,"->";
            } else {
                echo $list[$id]->id,"->";
            }
            $id ++;
            $count ++;
        }

        echo "<br/>";
    }

    //获取链表中某一节点的信息
    public function getOneNode($id) {
        $list = $this->_list;
        if(is_null($list[$id])) {
            echo "Node not exist.<br/>";
        } else {
            echo "Node Info : <br/>id : ", $list[$id]->id, "<br/>left : ", $list[$id]->left, "<br/>right : ",$list[$id]->right;
            echo "<br/>";
        }
    }
}

$linkedList = new LinkedList(1);//创建id为1的链表
$linkedList->createList(10);//为id为1的链表创建10个节点
//获取一个不存在的节点信息
$linkedList->getOneNode(20);
//获取一个存在的节点信息
$linkedList->getOneNode(2);
//从一个节点的位置开始遍历整个链表
$linkedList->iterateList(2);