关于链表:链表

34次阅读

共计 6807 个字符,预计需要花费 18 分钟才能阅读完成。

链表

简介

  • 数组:对于索引有语义的状况,利用索引获取值,疾速查问。

    • 随机拜访的能力
  • 链表:不适宜用于索引有语义的状况

    • 真正的动静,不须要解决固定容量的问题

构建

构建节点类

<?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)
正文完
 0