Home  >  Article  >  Backend Development  >  An example code for implementing a doubly linked list in PHP

An example code for implementing a doubly linked list in PHP

WBOY
WBOYOriginal
2016-07-25 08:57:401262browse
  1. /**
  2. * **Double linked list
  3. * @author zhiyuan12@
  4. * @modified 2012-10-25
  5. * @site: bbs.it-home.org
  6. */
  7. /**
  8. * Linked list element node class
  9. */
  10. class Node_Element {
  11. public $pre = NULL; // Precursor
  12. public $next = NULL; // Successor
  13. public $key = NULL; // Element key value
  14. public $data = NULL; // Node value
  15. function __Construct($key, $data) {
  16. $this->key = $key;
  17. $this ->data = $data;
  18. }
  19. }
  20. /**
  21. * Doubly linked list class
  22. */
  23. class DoubleLinkedList {
  24. private $head; // Head pointer
  25. private $tail; // Tail pointer
  26. private $current; // Current pointer
  27. private $len; // Linked list length
  28. function __Construct() {
  29. $this->head = self::_getNode ( null, null );
  30. $this->curelement = $this->head;
  31. $this->tail = $this->head;
  32. $len = 0;
  33. }
  34. /**
  35. * @ desc: Read all nodes of the linked list
  36. */
  37. public function readAll() {
  38. $tmp = $this->head;
  39. while ( $tmp->next !== null ) {
  40. $tmp = $tmp->next;
  41. var_dump ( $tmp->key, $tmp->data );
  42. }
  43. }
  44. public function move($pos1, $pos2) {
  45. $pos1Node = $this->findPosition ( $pos1 );
  46. $pos2Node = $this->findPosition ( $pos2 );
  47. if ($pos1Node !== null && $pos2Node !== null) {
  48. $tmpKey = $pos1Node->key;
  49. $tmpData = $pos1Node->data;
  50. $pos1Node->key = $pos2Node->key;
  51. $pos1Node-> ;data = $pos2Node->data;
  52. $pos2Node->key = $tmpKey;
  53. $pos2Node->data = $tmpData;
  54. return true;
  55. }
  56. return false;
  57. }
  58. /**
  59. * @ desc: Delete the node at the specified keyword
  60. *
  61. * @param: $key
  62. * The linked list element key at the specified position
  63. */
  64. public function delete($key) {
  65. $pos = $this->find ( $key );
  66. if ($pos !== null) {
  67. $tmp = $pos;
  68. $last = null ;
  69. $first = true;
  70. while ( $tmp->next !== null && $tmp->next->key === $key ) {
  71. $tmp = $tmp->next;
  72. if (! $first) {
  73. $this->delNode ( $last );
  74. } else {
  75. $first = false;
  76. }
  77. $last = $tmp;
  78. }
  79. if ($tmp->next ! == null) {
  80. $pos->pre->next = $tmp->next;
  81. $tmp->next->pre = $pos->pre;
  82. } else {
  83. $pos ->pre->next = null;
  84. }
  85. $this->delNode ( $pos );
  86. $this->delNode ( $tmp );
  87. }
  88. }
  89. /**
  90. * @ desc: Delete the node at the specified position
  91. *
  92. * @param: $key
  93. * The key of the linked list element at the specified position
  94. */
  95. public function deletePosition($pos) {
  96. $tmp = $this->findPosition ( $pos );
  97. if ($tmp === null) {
  98. return true;
  99. }
  100. if ($tmp === $ this->getTail ()) {
  101. $tmp->pre->next = null;
  102. $this->delNode ( $tmp );
  103. return true;
  104. }
  105. $tmp->pre-> ;next = $tmp->next;
  106. $tmp->next->pre = $tmp->pre;
  107. $this->delNode ( $tmp );
  108. }
  109. /**
  110. * @ desc: Insert the node before the specified key value
  111. *
  112. * @param : $key
  113. * //The linked list element key at the specified position
  114. * @param : $data
  115. * //The linked list element data to be inserted
  116. * @param: $flag
  117. * //Whether to search for positions sequentially for insertion
  118. */
  119. public function insert($key, $data, $flag = true) {
  120. $newNode = self::_getNode ( $key, $data );
  121. $tmp = $this->find ( $key, $ flag );
  122. if ($tmp !== null) {
  123. $newNode->pre = $tmp->pre;
  124. $newNode->next = $tmp;
  125. $tmp->pre = $newNode ;
  126. $newNode->pre->next = $newNode;
  127. }else {
  128. $newNode->pre = $this->tail;
  129. $this->tail->next = $newNode;
  130. $this->tail = $newNode;
  131. }
  132. $this->len ++;
  133. }
  134. /**
  135. * @ desc: Insert the node before the specified position
  136. *
  137. * @param : $pos
  138. * Specify the position to insert into the linked list
  139. * @param : $key
  140. * The key of the linked list element at the specified position
  141. * @param : $data
  142. * Linked list element data to be inserted
  143. */
  144. public function insertPosition($pos, $key, $data) {
  145. $newNode = self::_getNode ( $key, $data );
  146. $tmp = $this->findPosition ( $pos );
  147. if ($tmp !== null) {
  148. $newNode->pre = $tmp->pre;
  149. $newNode->next = $tmp;
  150. $tmp->pre = $newNode;
  151. $newNode->pre->next = $newNode;
  152. } else {
  153. $newNode->pre = $this->tail;
  154. $this->tail->next = $newNode;
  155. $this->tail = $newNode;
  156. }
  157. $this->len ++;
  158. return true;
  159. }
  160. /**
  161. * @desc: Query the specified position data based on the key value
  162. *
  163. * @param : $key
  164. * //The linked list element key at the specified position
  165. * @param : $flag
  166. * //Whether to search in order
  167. */
  168. public function find($key, $flag = true) {
  169. if ($flag) {
  170. $tmp = $this->head;
  171. while ( $tmp->next !== null ) {
  172. $tmp = $tmp->next;
  173. if ($tmp->key === $key) {
  174. return $tmp;
  175. }
  176. }
  177. } else {
  178. $tmp = $this->getTail ();
  179. while ( $tmp->pre !== null ) {
  180. if ($tmp->key === $key) {
  181. return $tmp;
  182. }
  183. $tmp = $tmp->pre;
  184. }
  185. }
  186. return null;
  187. }
  188. /**
  189. * @ desc: Query the specified location data based on the location
  190. *
  191. * @param: $pos
  192. * //The linked list element key at the specified location
  193. */
  194. public function findPosition($pos) {
  195. if ($pos <= 0 || $pos > $this->len)
  196. return null;
  197. if ($pos < ($this->len / 2 + 1)) {
  198. $tmp = $this->head;
  199. $count = 0;
  200. while ( $tmp->next !== null ) {
  201. $tmp = $tmp->next;
  202. $count ++;
  203. if ($count === $pos) {
  204. return $tmp;
  205. }
  206. }
  207. } else {
  208. $tmp = $this->tail;
  209. $pos = $this->len - $pos + 1;
  210. $count = 1;
  211. while ( $tmp->pre !== null ) {
  212. if ($count === $pos) {
  213. return $tmp;
  214. }
  215. $tmp = $tmp->pre;
  216. $count ++;
  217. }
  218. }
  219. return null;
  220. }
  221. /**
  222. * @desc: Return the head node of the linked list
  223. */
  224. public function getHead() {
  225. return $this->head->next;
  226. }
  227. /**
  228. * @desc: Return the tail node of the linked list
  229. */
  230. public function getTail() {
  231. return $this->tail;
  232. }
  233. /**
  234. * @ desc: Query the number of nodes in the linked list
  235. */
  236. public function getLength() {
  237. return $this->len;
  238. }
  239. private static function _getNode($key, $data) {
  240. $newNode = new Node_Element ( $key, $data );
  241. if ($newNode === null) {
  242. echo "new node fail!";
  243. }
  244. return $newNode;
  245. }
  246. private function delNode($node) {
  247. unset ( $node );
  248. $this->len --;
  249. }
  250. }
  251. // $myList = new DoubleLinkedList ();
  252. // $myList->insert ( 1, "test1" );
  253. // $myList->insert ( 2, "test2" );
  254. // $myList->insert ( "2b", "test2-b" );
  255. // $myList->insert ( 2, "test2-c" );
  256. // $myList->insert ( 3, "test3" );
  257. // $myList->insertPosition ( 5, "t", "testt" );
  258. // $myList->readAll ();
  259. // echo "+++";
  260. // $myList->deletePosition(0);
  261. // $myList->readAll ();
  262. // echo "..." . $myList->getLength ();
  263. // var_dump ( $myList->findPosition ( 3 )->data );
  264. ?>
Copy code


Statement:
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn