An example code for implementing a doubly linked list in PHP-PHP Tutorial-php.cn

An example code for implementing a doubly linked list in PHP

WBOY

Release： 2016-07-25 08:57:40

Original

1257 people have browsed it

/**
* **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 );
?>

Copy code

Php8, I'm coming too

Learn website layout in 30 minutes

Shangguan Oracle Beginner to Proficient Video Tutorial

Your first line of UNI-APP code

Flutter from scratch to app launch

Brother Lian New Linux Video Tutorial

AXURE 9 Video Tutorial (Suitable for Product Manager Interactive Product Design UI)

Zero Basic Proficiency PS Video Tutorial

16 day UI video tutorial to get you started

PS Techniques and Slicing Techniques Video Tutorial

Alibaba Cloud Environment Construction and Project Launch Video Tutorial

Overview of Computer Networks - Basic Knowledge that Programmers Must Master

Essential Tutorial for Programmers - HTTP Protocol Explanation

Websocket Video Tutorial

An example code for implementing a doubly linked list in PHP