1. 首页
  2. PHP
  3. 链表

链表

码农天地 -
链表
链表简介

数组：对于索引有语义的情况，利用索引获取值，快速查询。

随机访问的能力

链表：不适合用于索引有语义的情况

真正的动态，不需要处理固定容量的问题构建构建节点类

<?php
declare(strict_types=1);
​
class Node
{
// 该节点的元素值
public $e;
// 下一个节点的指针
public $next;
​
public function __construct($e = null, $next = null)
{
$this->e = $e;
$this->next = $next;
}
​
// 将该节点对象的元素值用字符串输出
public function __toString(): string
{
return (string)$this->e;
}
}

构建链表实现类定义属性与构造函数

<?php
declare(strict_types=1);
​
require_once 'Node.php';
​
class LinkedList
{
// 链表头指针
private $head;
​
// 链表中元素数量
private int $size;
​
public function __construct()
{
$this->head = null;
$this->size = 0;
}
}

获取链表有效元素数量

// 获取链表有效元素数量
public function getSize(): int
{
return $this->size;
}

判断链表是否为空

// 链表是否为空
public function isEmpty(): bool
{
return $this->size === 0;
}

在链表头插入一个元素

// 在链表头插入一个元素
public function addFrist($e): void
{
// $nodeObj = new Node($e);
// $nodeObj->next = $this->head;
// $this->head = $nodeObj;
$this->head = new Node($e, $this->head);
$this->size++;
}

在第index位插入元素$e

// 往index位添加一个新元素e
// 辅助理解与练习用，假定链表也又索引
public function add(int $index, $e): void
{
if ($index < 0 || $index > $this->size) {
throw new RuntimeException('index值有误');
}
if ($index === 0) {
$this->addFrist($e);
} else {
$prev = $this->head;
for ($i = 0; $i < $index - 1; $i++) {
$prev = $prev->next;
}
$prev->next = new Node($e, $prev->next);
$this->size++;
}
}

在链表末尾插入元素$e

// 在立案表末尾插入元素$e
public function addLast($e): void
{
$this->add($this->size, $e);
}

引入虚拟头结点，使不管往链表中的哪个节点插入元素都逻辑相同

<?php
declare(strict_types=1);
​
require_once 'Node.php';
​
class LinkedList
{
// 链表头指针
// private $head;
​
// 虚拟头结点
private $dummyHead;
​
// 链表中元素数量
private int $size;
​
public function __construct()
{
// $this->head = null;
$this->dummyHead = new Node(null, null);
$this->size = 0;
}
​
// 在链表头插入一个元素
// public function addFrist($e): void
// {
//     // $nodeObj = new Node($e);
//     // $nodeObj->next = $this->head;
//     // $this->head = $nodeObj;
//     $this->head = new Node($e, $this->head);
//     $this->size++;
// }
​
// 往index位添加一个新元素e
// 辅助理解与练习用，假定链表也有索引
// public function add(int $index, $e): void
// {
//     if ($index < 0 || $index > $this->size) {
//         throw new RuntimeException('index值有误');
//     }
//     if ($index === 0) {
//         $this->addFrist($e);
//     } else {
//         $prev = $this->head;
//         for ($i = 0; $i < $index - 1; $i++) {
//             $prev = $prev->next;
//         }
//         $prev->next = new Node($e, $prev->next);
//         $this->size++;
//     }
// }
​
// 往index位添加一个新元素e
public function add(int $index, $e): void
{
if ($index < 0 || $index > $this->size) {
throw new RuntimeException('index值有误');
}
​
$prev = $this->dummyHead;
for ($i = 0; $i < $index; $i++) {
$prev = $prev->next;
}
​
$prev->next = new Node($e, $prev->next);
​
$this->size++;
}
​
// 在立案表末尾插入元素$e
public function addLast($e): void
{
$this->add($this->size, $e);
}
​
// 在链表头插入一个元素
public function addFrist($e): void
{
$this->add(0, $e);
}
}

设置第index位的值为e

// 设置第index位的元素值
// 辅助理解与练习用，假定链表也有索引
public function set(int $index, $e): void
{
if ($index < 0 || $index >= $this->size) {
throw new RuntimeException('index值有误');
}
// 使用虚拟头结点的下一个元素作为起始位
$cur = $this->dummyHead->next;
for ($i = 0; $i < $index; $i++) {
$cur = $cur->next;
}
$cur->e = $e;
}

查找元素是否存在

// 查找链表中是否有元素$e
public function contains($e): bool
{
// 使用虚拟头结点的下一个元素作为起始位
$cur = $this->dummyHead->next;
while ($cur !== null) {
if ($cur->e === $e) {
return true;
}
$cur = $cur->next;
}
return false;
}

删除元素

// 删除第index位的元素值，并返回删除的元素值
// 辅助理解与练习用，假定链表也有索引
public function remove(int $index)
{
if ($index < 0 || $index >= $this->size) {
throw new RuntimeException('index值有误');
}
$prev = $this->dummyHead;
for ($i = 0; $i < $index; $i++) {
$prev = $prev->next;
}
$retNode = $prev->next;
$prev->next = $retNode->next;
$retNode->next = null;
$this->size--;
​
return $retNode->e;
}
​
// 删除第一个元素
public function removeFrist()
{
return $this->remove(0);
}
​
// 删除最后一个元素
public function removeLast()
{
return $this->remove($this->size - 1);
}

对象转字符串魔术方法

public function __toString(): string
{
$string = '';
$cur = $this->dummyHead->next;
while ($cur !== null) {
$string .= ($cur . '->');
$cur = $cur->next;
}
$string .= 'NULL
';
return $string;
}

完整代码

<?php
declare(strict_types=1);
​
require_once 'Node.php';
​
class LinkedList
{
// 链表头指针
// private $head;
​
// 虚拟头结点
private $dummyHead;
​
// 链表中元素数量
private int $size;
​
public function __construct()
{
//       $this->head = null;
$this->dummyHead = new Node(null, null);
$this->size = 0;
}
​
// 获取链表有效元素数量
public function getSize(): int
{
return $this->size;
}
​
// 链表是否为空
public function isEmpty(): bool
{
return $this->size === 0;
}
​
// 在链表头插入一个元素
// public function addFrist($e): void
// {
//     // $nodeObj = new Node($e);
//     // $nodeObj->next = $this->head;
//     // $this->head = $nodeObj;
//     $this->head = new Node($e, $this->head);
//     $this->size++;
// }
​
// 往index位添加一个新元素e
// 辅助理解与练习用，假定链表也有索引
// public function add(int $index, $e): void
// {
//     if ($index < 0 || $index > $this->size) {
//         throw new RuntimeException('index值有误');
//     }
//     if ($index === 0) {
//         $this->addFrist($e);
//     } else {
//         $prev = $this->head;
//         for ($i = 0; $i < $index - 1; $i++) {
//             $prev = $prev->next;
//         }
//         $prev->next = new Node($e, $prev->next);
//         $this->size++;
//     }
// }
​
// 往index位添加一个新元素e
public function add(int $index, $e): void
{
if ($index < 0 || $index > $this->size) {
throw new RuntimeException('index值有误');
}
​
$prev = $this->dummyHead;
for ($i = 0; $i < $index; $i++) {
$prev = $prev->next;
}
​
$prev->next = new Node($e, $prev->next);
​
$this->size++;
}
​
// 在立案表末尾插入元素$e
public function addLast($e): void
{
$this->add($this->size, $e);
}
​
// 在链表头插入一个元素
public function addFrist($e): void
{
$this->add(0, $e);
}
​
// 获取第index位的元素值
// 辅助理解与练习用，假定链表也有索引
public function get(int $index)
{
if ($index < 0 || $index >= $this->size) {
throw new RuntimeException('index值有误');
}
​
// 使用虚拟头结点的下一个元素作为起始位
$cur = $this->dummyHead->next;
​
for ($i = 0; $i < $index; $i++) {
$cur = $cur->next;
}
return $cur->e;
}
​
// 获取链表的第一个元素
public function getFrist()
{
return $this->get(0);
}
​
// 获取链表的最后一个元素
public function getLast()
{
return $this->get($this->size - 1);
}
​
// 设置第index位的元素值
// 辅助理解与练习用，假定链表也有索引
public function set(int $index, $e): void
{
if ($index < 0 || $index >= $this->size) {
throw new RuntimeException('index值有误');
}
// 使用虚拟头结点的下一个元素作为起始位
$cur = $this->dummyHead->next;
for ($i = 0; $i < $index; $i++) {
$cur = $cur->next;
}
$cur->e = $e;
}
​
// 查找链表中是否有元素$e
public function contains($e): bool
{
// 使用虚拟头结点的下一个元素作为起始位
$cur = $this->dummyHead->next;
​
while ($cur !== null) {
if ($cur->e === $e) {
return true;
}
$cur = $cur->next;
}
return false;
}
​
// 删除第index位的元素值，并返回删除的元素值
// 辅助理解与练习用，假定链表也有索引
public function remove(int $index)
{
if ($index < 0 || $index >= $this->size) {
throw new RuntimeException('index值有误');
}
$prev = $this->dummyHead;
for ($i = 0; $i < $index; $i++) {
$prev = $prev->next;
}
$retNode = $prev->next;
$prev->next = $retNode->next;
$retNode->next = null;
$this->size--;
​
return $retNode->e;
}
​
// 删除第一个元素
public function removeFrist()
{
return $this->remove(0);
}
​
// 删除最后一个元素
public function removeLast()
{
return $this->remove($this->size - 1);
}
​
public function __toString(): string
{
$string = '';
$cur = $this->dummyHead->next;
while ($cur !== null) {
$string .= ($cur . '->');
$cur = $cur->next;
}
$string .= 'NULL
';
return $string;
}
}

测试

require DIR . '/LinkedList/LinkedList.php';
$linkedListObj = new LinkedList();
for ($i = 0; $i < 5; $i++) {
$linkedListObj->addFrist($i);
echo $linkedListObj;
}
$linkedListObj->add(2,'abc');
echo $linkedListObj;
​
$linkedListObj->removeLast();
echo $linkedListObj;
$linkedListObj->removeFrist();
echo $linkedListObj;
$linkedListObj->remove(2);
echo $linkedListObj;

时间复杂度

添加操作

addLast()为O(n)addFirst()为O(1)add()为O(n/2)~O(n)

删除操作

removeLast()为O(n)removeFirst()为O(1)remove()为O(n/2)~O(n)

修改操作

set()为O(n)

查找操作

get()为O(n)contains()为O(n)增：O(n)删：O(n)改：未知索引O(n)查：未知索引O(n)如果只是对链表头增删改查的话就是都是O(1)
特别申明：本文内容来源网络，版权归原作者所有，如有侵权请立即与我们联系（cy198701067573@163.com），我们将及时处理。

php介绍

PHP即“超文本预处理器”，是一种通用开源脚本语言。PHP是在服务器端执行的脚本语言，与C语言类似，是常用的网站编程语言。PHP独特的语法混合了C、Java、Perl以及 PHP 自创的语法。利于学习，使用广泛，主要适用于Web开发领域。
更多关于php的阅读
上一篇： laravel8更新之速率限制改进
下一篇： Java详细学习路线及路线图(2020最新版) | Java工程师成神之路 | Java最全学习路线

Tags 标签

链表php数据结构

扩展阅读

隐藏apache版本信息
2018-09-30 10:56:15 []
CentOS 6.5安装php5.6
2018-09-30 11:36:53 []
PHP版ZIP压缩解压类库
2018-12-22 13:11:00 []
CentOS7.2安装 PHP7.3.4 操作详细教程
2020-06-28 19:09:43 []
PHP 设置脚本超时时间、PHP脚本内存限制设置
2020-06-28 19:09:43 []
PHP 函数filesize获取文件大小错误，一直不变
2020-06-28 19:09:43 []
Linux php: command not found
2020-02-05 01:30:13 []
php 缓冲区 buffer 原理
2020-06-28 19:09:43 []
PHP中三种设置脚本最大执行时间的方法
2020-06-28 19:17:34 []

加个好友，技术交流

1628738909466805.jpg

码农天地

首页 HTML/CSS WEB服务器 PHP Linux 数据库 异常报错 插件工具 美文欣赏 站长直荐
友情链接：码农天地爱厂家深圳钻石回收麦思会议

Copyright © 2019-2024| 沪ICP备19030844号-2 | SiteMap