이 글에서는 PHP에서 연결 리스트를 구현하는 방법을 소개합니다. 도움이 필요한 친구들이 모두 참고할 수 있기를 바랍니다.
추천 학습: "PHP 비디오 튜토리얼"
링크드 리스트는 물리적 저장 장치의 비연속, 비순차적 저장 구조입니다. 데이터 요소의 논리적 순서는 포인터 링크를 통해 구현됩니다. 연결리스트에서 순서를 정하세요. 연결된 목록은 일련의 노드(연결된 목록의 각 요소를 노드라고 함)로 구성되며 노드는 런타임에 동적으로 생성될 수 있습니다.
양식: 단일 연결 목록, 이중 연결 목록, 건너뛰기 목록(redis 컬렉션 데이터 구조는 건너뛰기 목록, 시간 복잡도 O(log N)으로 구현됨)
건너뛰기 목록 자세히 알아보기: https://lotabout.me/2018/ Skip-list /
노드 클래스 정의:
<?php class Node
{
public $val;
public $next;
public function __construct( $val = null, $next = null )
{
$this->val = $val;
$this->next = $next;
}
}연결된 목록 클래스:
<?php /**链表
* Class Linklist
* @package app\models
*/
class Linklist
{
public $head; //头节点(默认一个虚拟头节点)
public $size; //长度
public function __construct()
{
$this->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<p>호출 작업은 다음과 같습니다. </p><pre class="brush:php;toolbar:false"><?php $node = new Linklist();
$node->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 연결된 목록 작업의 시간 복잡도:
增： O(n) 只对链表头操作：O(1) 删： O(n) 只对链表头操作：O(1) 改：O(n) 查：O(n) 只对链表头操作：O(1)
<?php /**
* 链表实现栈
* Class LinklistStack
* @package app\models
*/
class LinklistStack extends Linklist
{
/**
* @param $value
*/
public function push( $value ){
$this->addFirst($value);
}
/**
* @return mixed
*/
public function pop(){
$r = $this->head->next->val;
$this->delete(0);
return $r;
}
}<?php $stack = new LinklistStack();
$stack->push(1);
$stack->push(3);
$stack->push(6);
$stack->push(9);
print_r($stack->pop());
print_r($stack->head);
<?php /**
* 链表实现队列
* Class LinkListQueue
* @package app\models
*/
class LinkListQueue extends Linklist
{
public $tail; //尾节点
/**
* push
* @param $value
*/
public function push( $value ){
if( $this->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
<?php $stack = new LinkListQueue();
$stack->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
**/위 내용은 PHP에서 연결리스트를 구현하는 방법에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
