PHP实现双向链表的一例代码

<?php 
/**
 * **双向链表
 * @author zhiyuan12@
 * @modified 2012-10-25
 * @site: www.jb200.com
 */ 
/**
 * 链表元素结点类
 */ 
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 ); 
?>