PHP 实现单向链表

Posted on

数据结构是每一个好的程序员的必修课程,这回乘着闭关修炼的这段时间,好好整理下关于数据结构的相关只是.本次就以链表开始说起.

什么的链表

链表与数组不一样,在 C, java 中 数组的初始化是需要声明长度,以及每个元素的大小的.虽然在书写伤可以简写,但最终编译器在初始化时,也会隐式完成声明.每个数组在声明完成后,其占用内存地址是连续的,占用内存大小不可改变.

链表是一种数据结构,一个基础的链表是由多个单节点连接在一起组成的,在内存地址中非连续的线性表.每个节点至少包含值字段,以及指向下一个节点内存地址的指针坐标.

链表的优点相对于数组来说,链表更加灵活.数组需要知道元素的大小,而链表不需要,并且链表的每个节点都可以是不同类型,空间利用更加灵活.

但由于链表是根据存放在节点中的指针地址寻找下一个节点的,所以无法完成像数组的随机读取功能,并且每个节点多存放了指针地址,内存开销相应比数组稍大.

连接结构剖析

在上一节介绍中描述中我们知道,链表是由节点构成的.每一个节点至少包含值与指针地址,下面我们应用 wiki 百科中的图片作为描述:

avatar

上图中每组都包含值与指针地址,指针地址指向下一个节点的内存地址,这样程序在查询到节点时,就知道下一个节点在那个地方,整个结构犹如链条一般.因此得名链表

当然链表也不仅仅只有一种,还有双向链表,循环链表,十字链表等等.wiki 中有相关描述 链接地址.本文由于篇幅限制,不做过多叙述.更多结构会在今后的文章中看到

在 php 中完成链表的实现

大多数 php 开发者都很少有使用到数据结构,基本都是使用 PHP 的数组结构,虽说 php 数组是由 Hash table与list 组成的特殊结构. 但大多数 php 程序员都不太清楚.

另外 php 的官方的标准库 Spl 中也有各种写好的结构.类似 SplQueue SplHeap SplStack SplDoublyLinkedList,各种结构数不胜数,这些后续在讲解,这里先做一个简单的 PHP 实现

那么首先链表是由节点组成的,所以我们需要定义一个节点结构.为了方便,我们就简单的实现一个单链表:

1
2
3
4
5
6
7
8
9
10
11
12
13
// 单链表节点
class ListNode
{
    // 节点值
    public $data = null;
    // 下一个节点
    public $next = null;

    public function __construct($data)
    {
        $this->data = $data;
    }
}

然后写一个简单的链表操作类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
class ListTest
{
    public $next = null;

    // 添加节点
    public function attach($data)
    {
        // 如果为 null 则添加链表头
        if ( is_null($this->next) ) {
            $this->next = new ListNode($data);
            return $this;
        }

        // 如果非空,则循环至最后一个节点
        $nextNode = $this->next;
       
        while ($nextNode->next) {
            $nextNode = $nextNode->next;
        }

        // 设置下一个节点
        $nextNode->next = new ListNode($data);
        return $this;
    }

    // 移除节点
    public function detach($data)
    {
        $node = $this->find($data);
    }

    public function findPrev($data)
    {
        if ( is_null($this->next) ) {
            return false;
        }

        // 如果第一个节点就是,则返回自身
        if ($this->next->data === $data) {
            return $this;
        }
        
        $current = $this->next;
        $nextNode = $current->next;
   
        while ( $nextNode->data !== $data ){
            $current = $nextNode;
            // 若存在下一个节点,则指向下一个节点,否则跳出
            if ($nextNode->next){
                $nextNode = $nextNode->next;
            }else{
                break;
            }
        }

        if ($nextNode->data === $data) {
            return $current;
        }else{
            return false;
        }
    }

    // 查询是否存在
    public function find($data)
    {
        $nodePrev = $this->findPrev($data);

        if ($nodePrev) {
            return $nodePrev->next;
        }else{
            return false;
        }
    }
}

此处只实现了几个操作作为演示,并非完整链表.其他操作方法各位也可以自己实现

接下来就是测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
$l = new ListTest();
// 新增节点
$l->attach("hello");
$l->attach("world");
$l->attach("test");

echo "------------------ attach node -----------------" . PHP_EOL;

$callable = function ($value) use ($l)
{
    return $l->find($value) ? "yes" . PHP_EOL : "no" . PHP_EOL;
};
// 查询节点
print_r($callable("hello")); 
print_r($callable("world")); 
print_r($callable("test")); 
print_r($callable("haha"));

下面是输出结果:

1
2
3
4
5
6
➜  List php exmple.php
------------------ attach node -----------------
yes
yes
yes
no

感想

虽然在 php 的开发中,数据结构很少使用,基本上使用 php 的数组结构就可以完成大多数工作. 大多数 php 程序员基本没学过数据结构,也能有一份好的工作和丰厚的工资.但是我认为我们还是不能满足于此,工作中还是需要多多学习,以免到时候书到用时方恨少.碰到的问题明明有解决方案,但自己不知道.这才是最尴尬的了!