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;
}
}
}
}
?>