怎么在PHP中定义一个双向链表

这期内容当中小编将会给大家带来有关怎么在PHP中定义一个双向链表，文章内容丰富且以专业的角度为大家分析和叙述，阅读完这篇文章希望大家可以有所收获。

<?php
/**
***双向链表
*@authorzhiyuan12@
*/
/**
*链表元素结点类
*/
classNode_Element{
public$pre=NULL;//前驱
public$next=NULL;//后继
public$key=NULL;//元素键值
public$data=NULL;//结点值
function__Construct($key,$data){
$this->key=$key;
$this->data=$data;
}
}
/**
*双向链表类
*/
classDoubleLinkedList{
private$head;//头指针
private$tail;//尾指针
private$current;//当前指针
private$len;//链表长度
function__Construct(){
$this->head=self::_getNode(null,null);
$this->curelement=$this->head;
$this->tail=$this->head;
$len=0;
}
/**
*@desc:读取链表全部结点
*/
publicfunctionreadAll(){
$tmp=$this->head;
while($tmp->next!==null){
$tmp=$tmp->next;
var_dump($tmp->key,$tmp->data);
}
}
publicfunctionmove($pos1,$pos2){
$pos1Node=$this->findPosition($pos1);
$pos2Node=$this->findPosition($pos2);
if($pos1Node!==null&&$pos2Node!==null){
$tmpKey=$pos1Node->key;
$tmpData=$pos1Node->data;
$pos1Node->key=$pos2Node->key;
$pos1Node->data=$pos2Node->data;
$pos2Node->key=$tmpKey;
$pos2Node->data=$tmpData;
returntrue;
}
returnfalse;
}
/**
*@desc:在指定关键词删除结点
*
*@param:$key
*指定位置的链表元素key
*/
publicfunctiondelete($key){
$pos=$this->find($key);
if($pos!==null){
$tmp=$pos;
$last=null;
$first=true;
while($tmp->next!==null&&$tmp->next->key===$key){
$tmp=$tmp->next;
if(!$first){
$this->delNode($last);
}else{
$first=false;
}
$last=$tmp;
}
if($tmp->next!==null){
$pos->pre->next=$tmp->next;
$tmp->next->pre=$pos->pre;
}else{
$pos->pre->next=null;
}
$this->delNode($pos);
$this->delNode($tmp);
}
}
/**
*@desc:在指定位置删除结点
*
*@param:$key
*指定位置的链表元素key
*/
publicfunctiondeletePosition($pos){
$tmp=$this->findPosition($pos);
if($tmp===null){
returntrue;
}
if($tmp===$this->getTail()){
$tmp->pre->next=null;
$this->delNode($tmp);
returntrue;
}
$tmp->pre->next=$tmp->next;
$tmp->next->pre=$tmp->pre;
$this->delNode($tmp);
}
/**
*@desc:在指定键值之前插入结点
*
*@param:$key
*//指定位置的链表元素key
*@param:$data
*//要插入的链表元素数据
*@param:$flag
*//是否顺序查找位置进行插入
*/
publicfunctioninsert($key,$data,$flag=true){
$newNode=self::_getNode($key,$data);
$tmp=$this->find($key,$flag);
if($tmp!==null){
$newNode->pre=$tmp->pre;
$newNode->next=$tmp;
$tmp->pre=$newNode;
$newNode->pre->next=$newNode;
}else{
$newNode->pre=$this->tail;
$this->tail->next=$newNode;
$this->tail=$newNode;
}
$this->len++;
}
/**
*@desc:在指定位置之前插入结点
*
*@param:$pos
*指定插入链表的位置
*@param:$key
*指定位置的链表元素key
*@param:$data
*要插入的链表元素数据
*/
publicfunctioninsertPosition($pos,$key,$data){
$newNode=self::_getNode($key,$data);
$tmp=$this->findPosition($pos);
if($tmp!==null){
$newNode->pre=$tmp->pre;
$newNode->next=$tmp;
$tmp->pre=$newNode;
$newNode->pre->next=$newNode;
}else{
$newNode->pre=$this->tail;
$this->tail->next=$newNode;
$this->tail=$newNode;
}
$this->len++;
returntrue;
}
/**
*@desc:根据key值查询指定位置数据
*
*@param:$key
*//指定位置的链表元素key
*@param:$flag
*//是否顺序查找
*/
publicfunctionfind($key,$flag=true){
if($flag){
$tmp=$this->head;
while($tmp->next!==null){
$tmp=$tmp->next;
if($tmp->key===$key){
return$tmp;
}
}
}else{
$tmp=$this->getTail();
while($tmp->pre!==null){
if($tmp->key===$key){
return$tmp;
}
$tmp=$tmp->pre;
}
}
returnnull;
}
/**
*@desc:根据位置查询指定位置数据
*
*@param:$pos
*//指定位置的链表元素key
*/
publicfunctionfindPosition($pos){
if($pos<=0||$pos>$this->len)
returnnull;
if($pos<($this->len/2+1)){
$tmp=$this->head;
$count=0;
while($tmp->next!==null){
$tmp=$tmp->next;
$count++;
if($count===$pos){
return$tmp;
}
}
}else{
$tmp=$this->tail;
$pos=$this->len-$pos+1;
$count=1;
while($tmp->pre!==null){
if($count===$pos){
return$tmp;
}
$tmp=$tmp->pre;
$count++;
}
}
returnnull;
}
/**
*@desc:返回链表头节点
*/
publicfunctiongetHead(){
return$this->head->next;
}
/**
*@desc:返回链表尾节点
*/
publicfunctiongetTail(){
return$this->tail;
}
/**
*@desc:查询链表节点个数
*/
publicfunctiongetLength(){
return$this->len;
}
privatestaticfunction_getNode($key,$data){
$newNode=newNode_Element($key,$data);
if($newNode===null){
echo"newnodefail!";
}
return$newNode;
}
privatefunctiondelNode($node){
unset($node);
$this->len--;
}
}
$myList=newDoubleLinkedList();
$myList->insert(1,"test1");
$myList->insert(2,"test2");
$myList->insert("2b","test2-b");
$myList->insert(2,"test2-c");
$myList->insert(3,"test3");
$myList->insertPosition(5,"t","testt");
$myList->readAll();
echo"+++";
$myList->deletePosition(0);
$myList->readAll();
echo"...".$myList->getLength();
var_dump($myList->findPosition(3)->data);
?>

运行结果：

int(1)
string(5)"test1"
int(2)
string(7)"test2-c"
int(2)
string(5)"test2"
string(2)"2b"
string(7)"test2-b"
string(1)"t"
string(5)"testt"
int(3)
string(5)"test3"
+++int(1)
string(5)"test1"
int(2)
string(7)"test2-c"
int(2)
string(5)"test2"
string(2)"2b"
string(7)"test2-b"
string(1)"t"
string(5)"testt"
int(3)
string(5)"test3"
...6string(5)"test2"

上述就是小编为大家分享的怎么在PHP中定义一个双向链表了，如果刚好有类似的疑惑，不妨参照上述分析进行理解。如果想知道更多相关知识，欢迎关注恰卡编程网行业资讯频道。