An example code for implementing a doubly linked list in PHP

/**
 * **Double linked list
 * @author zhiyuan12@
 * @modified 2012-10-25
 * @site: bbs.it-home.org
*/
/**
 * Linked list element node class
*/
class Node_Element {
 public $pre = NULL; // Precursor
 public $next = NULL; // Successor
 public $key = NULL; // Element key value
 public $data = NULL; // Node value
 function __Construct($key, $data) {
 $this->key = $key;
 $this ->data = $data;
 }
}
/**
 * Doubly linked list class
*/
class DoubleLinkedList {
 private $head; // Head pointer
 private $tail; // Tail pointer
 private $current; // Current pointer
 private $len; // Linked list length
 function __Construct() {
 $this->head = self::_getNode ( null, null );
 $this->curelement = $this->head;
 $this->tail = $this->head;
 $len = 0;
 }
 /**
 * @ desc: Read all nodes of the linked list
*/
 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: Delete the node at the specified keyword
 *
 * @param: $key
 * The linked list element key at the specified position
*/
 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: Delete the node at the specified position
 *
 * @param: $key
 * The key of the linked list element at the specified position
*/
 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: Insert the node before the specified key value
 *
 * @param : $key
 * //The linked list element key at the specified position
 * @param : $data
 * //The linked list element data to be inserted
 * @param: $flag
 * //Whether to search for positions sequentially for insertion
 */
 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: Insert the node before the specified position
 *
 * @param : $pos
 * Specify the position to insert into the linked list
 * @param : $key
 * The key of the linked list element at the specified position
 * @param : $data
 * Linked list element data to be inserted
*/
    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: Query the specified position data based on the key value
 *
 * @param : $key
 * //The linked list element key at the specified position
 * @param : $flag
 * //Whether to search in order
*/
    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: Query the specified location data based on the location
 *
 * @param: $pos
 * //The linked list element key at the specified location
*/
    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: Return the head node of the linked list
*/
    public function getHead() {
        return $this->head->next;
    }
    /**
 * @desc: Return the tail node of the linked list
*/
    public function getTail() {
        return $this->tail;
    }
    /**
 * @ desc: Query the number of nodes in the linked list
*/
    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 );
?>