PHP双向链表定义与用法示例

本文实例讲述了PHP双向链表定义与用法。分享给大家供大家参考，具体如下：由于需要对一

本文实例讲述了PHP双向链表定义与用法。分享给大家供大家参考，具体如下：

由于需要对一组数据多次进行移动操作，所以写个双向链表。但对php实在不熟悉，虽然测试各个方法没啥问题，就是不知道php语言深层的这些指针和unset有什么注意的地方，贴出来让大家教育吧。效率没测试....求谅解～

<?php
/**
 * **双向链表
 * @author zhiyuan12@
 */
/**
 * 链表元素结点类
 */
class Node_Element {
 public $pre = NULL; // 前驱
 public $next = NULL; // 后继
 public $key = NULL; // 元素键值
 public $data = NULL; // 结点值
 function __Construct($key, $data) {
 $this->key = $key;
 $this->data = $data;
 }
}
/**
 * 双向链表类
 */
class DoubleLinkedList {
 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: 读取链表全部结点
 */
 public function readAll() {
 $tmp = $this->head;
 while ( $tmp->next !== null ) {
 $tmp = $tmp->next;
 var_dump ( $tmp->key, $tmp->data );
 }
 }
 public function move($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;
 return true;
 }
 return false;
 }
 /**
 * @ desc: 在指定关键词删除结点
 *
 * @param : $key
 * 指定位置的链表元素key
 */
 public function delete($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
 */
 public function deletePosition($pos) {
 $tmp = $this->findPosition ( $pos );
 if ($tmp === null) {
 return true;
 }
 if ($tmp === $this->getTail ()) {
 $tmp->pre->next = null;
 $this->delNode ( $tmp );
 return true;
 }
 $tmp->pre->next = $tmp->next;
 $tmp->next->pre = $tmp->pre;
 $this->delNode ( $tmp );
 }
 /**
 * @ desc: 在指定键值之前插入结点
 *
 * @param : $key
 * //指定位置的链表元素key
 * @param : $data
 * //要插入的链表元素数据
 * @param : $flag
 * //是否顺序查找位置进行插入
 */
 public function insert($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
 * 要插入的链表元素数据
 */
 public function insertPosition($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 ++;
 return true;
 }
 /**
 * @ desc: 根据key值查询指定位置数据
 *
 * @param : $key
 * //指定位置的链表元素key
 * @param : $flag
 * //是否顺序查找
 */
 public function find($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;
 }
 }
 return null;
 }
 /**
 * @ desc: 根据位置查询指定位置数据
 *
 * @param : $pos
 * //指定位置的链表元素key
 */
 public function findPosition($pos) {
 if ($pos <= 0 || $pos > $this->len)
 return null;
 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 ++;
 }
 }
 return null;
 }
 /**
 * @ desc: 返回链表头节点
 */
 public function getHead() {
 return $this->head->next;
 }
 /**
 * @ desc: 返回链表尾节点
 */
 public function getTail() {
 return $this->tail;
 }
 /**
 * @ desc: 查询链表节点个数
 */
 public function getLength() {
 return $this->len;
 }
 private static function _getNode($key, $data) {
 $newNode = new Node_Element ( $key, $data );
 if ($newNode === null) {
 echo "new node fail!";
 }
 return $newNode;
 }
 private function delNode($node) {
 unset ( $node );
 $this->len --;
 }
}
$myList = new DoubleLinkedList ();
$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"