Home > Article > Backend Development > Implementation of linked list in PHP
Implementation of linked list in PHP
- 不言Original
- 2018-04-24 10:38:353730browse
The content of this article is about the implementation of linked lists in PHP. It has certain reference value. Now I share it with everyone. Friends in need can refer to it
Start learning about data structures
I changed the font when writing code today. I used to use console which looks great. Today I found a style that I like betterSource Code Pro
Last two The picture is quite beautiful! ! ! 
Let’s get to the point and talk about the operation of the linked list
Node
First there must be a node class for storing data
<?phpnamespace LinkedList;class Node{
/**
* @var $data integer
*/
public $data; /**
* 节点指向的下一个元素
*
* @var $next Node
*/
public $next; public function __construct(int $data = -1)
{
public function __construct(int $data = null)
{
// 初始化赋值 data，也可通过 $node->data = X; 赋值
$this->data = $data;
}
}Linked list management class (for operating node data)
Because the code of the operation class is too long, we will analyze it in parts
Header insertion (because it is relatively simple, so I will talk about this first)
Listen Name, you know that a node is inserted from the head
When the linked list is empty, the current node is initialized
When the linked list is not empty, Insert the new node as the head node
public function insertHead(int $data) : bool{
///////////////////////////////////////////////////////////////////////////
// +-----------+ +--------+ +--------+
// | | | | | |
// | head node | +> | node | +> | node | +>
// | | | | | | | | |
// | | | | | | | | |
// | next | | | next | | | next | |
// +------+----+ | +----+---+ | +----+---+ |
// | | | | | |
// +------+ +-----+ +-----+
///////////////////////////////////////////////////////////////
// +-----------+ +--------+ +--------+
// | | | | | |
// +---> | head node | +> | node | +> | node | +>
// | | | | | | | | | |
// | | | | | | | | | |
// | | next | | | next | | | next | |
// | +------+----+ | +----+---+ | +----+---+ |
// | | | | | | |
// +--------+ | +------+ +-----+ +-----+
// | | |
// |new node| |
// | | |
// | | |
// | next | |
// +----+---+ |
// | |
// +-----+
//
// 1. 实例化一个数据节点
// 2. 使当前节点的下一个等于现在的头结点
// 即使当前头结点是 null，也可成立
// 3. 使当前节点成为头结点
// 即可完成头结点的插入
$newNode = new Node($data); $newNode->next = $this->head; $this->head = $newNode; return true;
}(index=0 is the head node, go down in sequence, and return false if the position is exceeded)
public function insert(int $index = 0, int $data) : bool{
// 头结点的插入, 当头部不存在，或者索引为0
if (is_null($this->head) || $index === 0) { return $this->insertHead($data);
} // 正常节点的插入, 索引从 0 开始计算
// 跳过了头结点，从 1 开始计算
$currNode = $this->head; $startIndex = 1; // 遍历整个链表，如果当前节点是 null，则代表到了尾部的下一个，退出循环
for ($currIndex = $startIndex; ! is_null($currNode); ++ $currIndex) { ////////////////////////////////////////////////////////////////////////////
///
// +--------+ +--------+ +-------------+ +--------+
// | | | | | | | |
// | node | +> |currNode| +> |currNode next| +> | node | +>
// | | | | | | | | | | | |
// | | | | | | | | | | | |
// | next | | | next | | | next | | | next | |
// +----+---+ | +----+---+ | +------+------+ | +----+---+ |
// | | | | | | | |
// +-----+ +-----+ +--------+ +-----+
////////////////////////////////////////////////////////////////////////////
// +--------+ +--------+ +-------------+ +--------+
// | | | | | | | |
// | node | +> |currNode| +> |currNode next| +> | node | +>
// | | | | | | | | | | | |
// | | | | | | | | | | | |
// | next | | | next | | | next | | | next | |
// +----+---+ | +--------+ | +------+------+ | +----+---+ |
// | | +--------+ | | | | |
// +-----+ | | | +--------+ +-----+
// |new node| |
// | | |
// | | |
// | next | |
// +----+---+ |
// | |
// +-----+
////////////////////////////////////////////////////////////////////////////
//
// +--------+ +--------+ +-------------+ +--------+
// | | | | | | | |
// | node | +> |currNode| +> |currNode next| +> | node | +>
// | | | | | | | | | | | |
// | | | | | | | | | | | |
// | next | | | next | | | next | | | next | |
// +----+---+ | +----+---+ | +------+------+ | +----+---+ |
// | | | +--------+ | | | | |
// +-----+ | | | | +--------+ +-----+
// +----> |new node| |
// | | |
// | | |
// | next | |
// +----+---+ |
// | |
// +-----+
//
// 1. 当前索引等于传入参数的索引
// 2. 实例化新数据节点
// 3. 新节点的下一个指向当前节点的下一个节点
// 4. 当前节点的下一个节点指向新节点
if ($currIndex === $index) { $newNode = new Node($data); $newNode->next = $currNode->next; $currNode->next = $newNode; return true;
} // 移动到下一个节点
$currNode = $currNode->next;
} return false;
}and above Two This is the basic operation of inserting. Take a look at the example code.
<?php // 自动加载的代码就不贴了，直接在 githubrequire __DIR__.'/../vendor/bootstrap.php'; // 实例化一个链表管理对象$manager = new \LinkedList\Manager(); // 8$manager->insertHead(8); // 5 8$manager->insertHead(5); // 1 5 8$manager->insertHead(1); // 1 2 5 8$manager->insert(1, 2); // false 节点元素不足 6 个$manager->insert(5, 4); // 1 2 5 8 9$manager->insertEnd(9); // 3$manager->find(8); // 1 2 8 9$manager->delete(2);
Find
Finding the value of the linked list is also very simple, just traverse it
/**
* 查找链表的值中的索引
* 成功返回索引值，找不到返回 -1
*
* @param int $data
* @return int
*/public function find(int $data) : int{
$currNode = $this->head; // 查找还是很简单的，只要遍历一次链表，然后再判断值是否相等就可以了
for ($i = 0; ! is_null($currNode); ++ $i) { if ($currNode->data === $data) { return $i;
} $currNode = $currNode->next;
} return -1;
}You only need to traverse the linked list once, find equal values, and return the index value if found. If not found, return -1
Delete
/**
* 删除链表的节点
*
* @param int $index
* @return bool
*/public function delete(int $index) : bool{
// 没有任何节点，直接跳过
if (is_null($this->head)) { return false;
} elseif ($index === 0) { // 头结点的删除
$this->head = $this->head->next;
} // 这里的开始的索引是 1
// 但当前节点指向的确实 头结点
// 因为删除的时候必须标记删除的前一个节点
// for 的判断是判断下一个节点是否为 null
// $currNode 是操作的节点
// $currNode->next 是要删除的节点
$startIndex = 1; $currNode = $this->head; for ($i = $startIndex; ! is_null($currNode->next); ++ $i) { if ($index === $i) { // 使当前节点等于要删除节点的下一个
// 即可完成删除
$currNode->next = $currNode->next->next; break;
} $currNode = $currNode->next;
} return true;
}End
The code has been hosted on github
There will be time to continue learning data structures, doubly linked lists, trees and the like! ! !
Related recommendations:
php implements the reverse order of a linked list
Use PHP to implement a singly linked list
How does PHP implement a doubly linked list and sort it
The above is the detailed content of Implementation of linked list in PHP. For more information, please follow other related articles on the PHP Chinese website!