A brief discussion on how to implement and process linked lists in PHP

This article will introduce to you how to implement and process linked lists in PHP. It has certain reference value. Friends in need can refer to it. I hope it will be helpful to everyone.

[Recommended learning: "PHP Video Tutorial"]

Linked List

A linked list is a non-continuous and non-sequential storage structure on a physical storage unit. The logical order of data elements is realized through the link order of pointers in the linked list. A linked list consists of a series of nodes (each element in the linked list is called a node), and nodes can be dynamically generated at runtime.

Forms: single linked list, double linked list, skip list (the redis collection data structure is realized by skip list, time complexity O (log N))

Learn about skip list: https://lotabout .me/2018/skip-list/

php implements the add, delete, modify and query operations on the linked list

Define node class:

val = $val; $this->next = $next; } }

Linked list class:

head = new Node(); $this->size = 0; } //头插法 public function addFirst( $value ){ // $node = new Node($value); // $node->next = $this->head; // $this->head = $node; //简化 // $this->head = new Node( $value, $this->head ); // $this->size++; $this->add(0,$value); } /**指定索引位置插入 * @param $index * @param $value * @throws Exception */ public function add( $index, $value ){ if( $index > $this->size ) throw new Exception('超过链表范围'); // if( $index==0 ){ // $this->addFirst($value); // }else{ $prev = $this->head; for($i=0;$inext; } // $node = new Node($value); // $node->next = $prev->next; // $prev->next = $node; $prev->next = new Node($value,$prev->next); // } $this->size++; } /**尾插法 * @param $value */ public function addLast( $value ){ $this->add($this->size,$value); } /*** * 编辑 * @param $index * @param $value * @throws Exception */ public function edit( $index, $value ){ if( $index > $this->size-1 ) throw new Exception('超过链表范围'); $prev = $this->head->next; for($i=0;$ival = $value; $prev = $prev->next; } } /** * 查询 * @param $index * @return null * @throws Exception */ public function select($index){ if( $index > $this->size-1 ) throw new Exception('超过链表范围'); $prev = $this->head->next; for($i=0;$inext; } } /**删除 * @param $index * @throws Exceptionr */ public function delete( $index ){ if( $index > $this->size-1 ) throw new Exception('超过链表范围'); $prev = $this->head; for($i=0;$inext = $prev->next->next; $prev = $prev->next; } $this->size--; } /**检索值是否存在 * @param $value * @return bool */ public function iscontain( $value ){ $prev = $this->head->next; while( $prev ){ if( $prev->val==$value ){ return true; } $prev = $prev->next; } return false; } /**转换为字符串 * @return string */ public function tostring(){ $prev = $this->head->next; $r = []; while( $prev ){ $r[] = $prev->val; $prev = $prev->next; } return implode('->',$r); } /** * 删除指定的节点值 * @param $value */ public function removeFileds( $value ){ $prev = $this->head; while( $prev->next ){ if( $prev->val == $value ){ $prev->val = $prev->next->val; $prev->next = $prev->next->next; }else{ $prev = $prev->next; } } } /** * 通过递归方式删除指定的节点值 * @param $value */ public function removeFiledsByRecursion( $value ){ $this->head = $this->removeByRecursion( $this->head ,$value); return $this->head; } public function removeByRecursion( $node , $value, $level=0 ){ if( $node->next == null ){ $this->showDeeep($level,$node->val); return $node->val == $value ? $node->next:$node; } $this->showDeeep($level,$node->val); $node->next = $this->removeByRecursion( $node->next,$value,++$level ); $this->showDeeep($level,$node->val); return $node->val == $value ? $node->next:$node; } /** * 显示深度 * 帮助理解递归执行过程，回调函数执行层序遵循系统栈 * @param int $level 深度层级 * @param $val * @return bool */ public function showDeeep( $level=1,$val ){ if( $level
The calling operation is as follows: 
addFirst(1); $node->add(1,7); $node->add(2,10); $node->edit(1,8); var_dump($node->select(1)) ; $node->delete(1); $node->addLast(99); var_dump($node->iscontain(2)); var_export($node); var_export($node->tostring());
      
Analyze the time complexity of the linked list operation:
      
增： O(n) 只对链表头操作：O(1) 删： O(n) 只对链表头操作：O(1) 改：O(n) 查：O(n) 只对链表头操作：O(1)
      
Use the linked list to implement the stack
      
addFirst($value); } /** * @return mixed */ public function pop(){ $r = $this->head->next->val; $this->delete(0); return $r; } }
      
push(1); $stack->push(3); $stack->push(6); $stack->push(9); print_r($stack->pop()); print_r($stack->head);
      
Linked list implementation queue
      

      
head->val==null ){ $this->tail = new Node( $value ); $this->head = $this->tail; }else{ $this->tail->next = new Node( $value ); $this->tail = $this->tail->next; } $this->size++; } /** * pop * @return null * @throws \Exception */ public function pop(){ if( $this->sizehead->val; $this->head = $this->head->next; $this->size--; return $val; } /** * 查看队首 */ public function checkHead(){ return $this->head->val; } /** * 查看队尾 */ public function checkEnd(){ return $this->tail->val; } /** * toString */ public function toString(){ $r = []; while( $this->head ){ $r[] = $this->head->val; $this->head = $this->head->next; } return implode('->',$r); } }
      
Test
      
push(1); $stack->push(3); $stack->push(6); $stack->push(9); print_r($stack->pop()); print_r($stack->head); print_r($stack->checkHead()); print_r($stack->checkEnd()); print_r($stack->toString()); /** 1 app\models\Node Object ( [val] => 3 [next] => app\models\Node Object ( [val] => 6 [next] => app\models\Node Object ( [val] => 9 [next] => ) ) ) 3 9 3->6->9 **/
      
For more programming-related knowledge, please visit:Programming Video! !
      
The above is the detailed content of A brief discussion on how to implement and process linked lists in PHP. For more information, please follow other related articles on the PHP Chinese website!