Example of recursive deletion of linked list elements by PHP
- 2021-09-04 23:10:17
- OfStack
Preface
This article introduces recursion. The essence of recursion is the process of transforming the original problem into a smaller problem and solving these smaller problems. Here are two examples of recursion to help you learn about recursion.
1. Recursive array summation
For example, an array $arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; Need to require sum, and help learn the understanding of recursion by realizing the summation of arrays by recursive functions.
1.1 Output file output_recursion. php
<?php
require 'ArrayRecursion.php';
/**
* Recursive realization of array summation
*/
$arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
echo ArrayRecursion::recursionSum($arr);1.2 Class ArrayRecursion
This is an array of recursive summation code, where recursionSum () is a recursive function, equivalent to the summation process into smaller summation, and finally achieve the desired results:
<?php
/**
* Summing Arrays Using Recursion Facilitate the understanding of recursion
* Class ArrayRecursion
*/
class ArrayRecursion
{
public static function sum(array $arr) {
return self::recursionSum($arr);
}
public static function recursionSum(array $arr, $i = 0) {
if (count($arr) == $i) {
return 0;
}
return $arr[$i] + self::recursionSum($arr, $i + 1);
}
}Tips: This summation process only helps to learn the idea of recursion. The actual summation can directly traverse the array.
2. Recursively delete an element of a linked list
For example, a linked list 10- > 9- > 8- > 99- > 7- > 99- > 6- > 5- > 99- > 4- > 3- > 2- > 1- > null needs to delete an element whose value is equal to 99, and the effect of deleting a specified element can be obtained by implementing recursion.
2.1 Output file output_recursion. php
<?php
require 'LinkedList.php';
require 'LinkedListRecursion.php';
/**
* First instantiate 1 Linked lists, add to the linked list 50 Elements
*/
$linkedList = new LinkedList();
for ($i = 0; $i < 50; $i++) {
if ($i % 7 == 0) {
$linkedList->addFirst(99);
} else {
$linkedList->addFirst($i);
}
}
echo $linkedList->toString();
/** Print elements in linked list
* 99->48->47->46->45->44->43->99->41->40->39->
* 38->37->36->99->34->33->32->31->30->29->99->27->
* 26->25->24->23->22->99->20->19->18->17->16->15->
* 99->13->12->11->10->9->8->99->6->5->4->3->2->1->99->null
*/
// Pass linked list objects into 1 Methods that can delete a specified element, such as 99
echo LinkedListRecursion::deleteElement($linkedList, 99)->toString();
/** Print
* 48->47->46->45->44->43->41->40->
* 39->38->37->36->34->33->32->31->
* 30->29->27->26->25->24->23->22->
* 20->19->18->17->16->15->13->12->
* 11->10->9->8->6->5->4->3->2->1->null
*/2.2 LinkedList & Node linked list class
This is a linked list class, you can use addFirst () method to add elements to the head of the linked list, you can use getHead () to obtain the node object information of the linked list head, you can use setHead () to change head, and another linked list node class Node is defined below:
<?php
/**
* Realization of linked list
* Class LinkedList
*/
class LinkedList
{
private $dummyHead;
private $size;
/**
* Initialize linked list null->null
* LinkedList constructor.
*/
public function __construct() {
$this->dummyHead = new Node(null, null);
$this->size = 0;
}
/**
* Get the linked list size
* @return int
*/
public function getSize(): int {
return $this->size;
}
/**
* Determine whether the linked list is empty
* @return bool
*/
public function isEmpty(): bool {
return $this->size == 0;
}
/**
* At the end of the linked list index Position add element
* @param int $index
* @param $e
*/
public function add(int $index, $e): void {
if ($index < 0 || $index > $this->size) {
echo " Index range error ";
exit;
}
$prve = $this->dummyHead;
for ($i = 0; $i < $index; $i++) {
$prve = $prve->next;
}
// Insert the top of the position 1 Of a position next Node points to the inserted node, and the next Node information points to the next Node
$prve->next = new Node($e, $prve->next);
$this->size++;
}
/**
* Add an element to the beginning of a linked list
* @param $e
*/
public function addFirst($e): void {
$this->add(0, $e);
}
/**
* Add an element to the end of a linked list
* @param $e
*/
public function addLast($e): void {
$this->add($this->size, $e);
}
/**
* Get the number of the linked list index Position element
* @param $index
*/
public function get($index) {
if ($index < 0 || $index > $this->size) {
echo " Index range error ";
exit;
}
$node = $this->dummyHead;
for ($i = 0; $i < $index + 1; $i++) {
$node = $node->next;
}
return $node->e;
}
/**
* Get the number of the linked list 1 Elements
* @return mixed
*/
public function getFirst() {
return $this->get(0);
}
/**
* Get the last of the linked list 1 Elements
* @return mixed
*/
public function getLast() {
return $this->get($this->size - 1);
}
/**
* Modify the column in the linked list index Position element value
* @param $index
* @param $e
*/
public function update($index, $e) {
if ($index < 0 || $index > $this->size) {
echo " Index range error ";
exit;
}
$node = $this->dummyHead;
for ($i = 0; $i < $index + 1; $i++) {
$node = $node->next;
}
$node->e = $e;
}
/**
* Determine whether there is an element in the linked list
* @param $e
* @return bool
*/
public function contains($e): bool {
for ($node = $this->dummyHead->next; $node != null; $node = $node->next) {
if ($node->e == $e) {
return true;
}
}
return true;
}
/**
* Delete the entries in the linked list index Position element
* @param $index
*/
public function remove($index) {
if ($index < 0 || $index > $this->size) {
echo " Index range error ";
exit;
}
if ($this->size == 0) {
echo " The linked list is already empty ";
exit;
}
$prve = $this->dummyHead;
for ($i = 0; $i < $index; $i++) {
$prve = $prve->next;
}
$node = $prve->next;
$prve->next = $node->next;
$this->size--;
return $node->e;
}
/**
* Delete linked list header element
*/
public function removeFirst() {
return $this->remove(0);
}
/**
* Delete the last element of linked list
*/
public function removeLast() {
return $this->remove($this->size - 1);
}
/**
* Get header node information
* @return mixed
*/
public function getHead() {
return $this->dummyHead->next;
}
/**
* Set head
* @param Node $head
*/
public function setHead(Node $head) {
$this->dummyHead->next = $head;
}
/**
* Linked list elements are converted to string display
* @return string
*/
public function toString(): string {
$str = "";
for ($node = $this->dummyHead->next; $node != null; $node = $node->next) {
$str .= $node->e . "->";
}
return $str . "null";
}
}
class Node
{
public $e;// Node element
public $next; // Next node information
/**
* Constructor Setting Node Information
* Node constructor.
* @param $e
* @param $next
*/
public function __construct($e, $next) {
$this->e = $e;
$this->next = $next;
}
}2.3 LinkedListRecursion Class
This class defines an deleteElement (LinkedList $linkedList, $val) method that deletes nodes with specified element values in the passed linked list class (actually, the node's next repoints), and the recursionDelete ($head, $val) method is a recursive function that recursively deletes nodes with specified element values equal to $val in head:
<?php
/**
* Recursively delete the specified element of linked list
* Class LinkedListRecursion
*/
class LinkedListRecursion
{
public static function deleteElement(LinkedList $linkedList, $val) {
$linkedList->setHead(self::recursionDelete($linkedList->getHead(), $val));
return $linkedList;
}
/**
* Recursive function Recursively delete linked list elements
* @param $head
* @param $val
* @return null
*/
private static function recursionDelete($head, $val) {
if ($head == null) {
return null;
} else {
if ($head->e == $val) {
return self::recursionDelete($head->next, $val);
} else {
$head->next = self::recursionDelete($head->next, $val);
return $head;
}
}
}
}Code repository: https://gitee.com/love-for-po...
Summarize