紫锦木 | 足迹👣
2019-05-25 | PHP | UNLOCK

PHP单项链表的实现

说明：单向链表（单链表）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始；链表是使用指针进行构造的列表；又称为结点列表，因为链表是由一个个结点组装起来的；其中每个结点都有指针成员变量指向列表中的下一个结点；
列表是由结点构成，head 指针指向第一个成为表头结点，而终止于最后一个指向 NULL 的指针。

示意图说明

代码说明

SingleLink.php
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
<?php

class Node
{
    public $id    = null;
    public $value = null;
    public $next  = null;

    public function __construct($id, $value)
    {
        $this->id    = $id;
        $this->value = $value;
    }
}

class SingleLink
{
    private $node;

    public function __construct($id = null, $value = null)
    {
        $this->node = new Node($id, $value);
    }

    /**
     * 往链表中添加节点
     *
     * @param Node $node
     */
    public function addLink(Node $node)
    {
        $currentNode = $this->node;
        while ($currentNode->next !== null) {
            // 相当于插入链表
            if ($currentNode->next->id > $node->id) {
                break;
            }
            // 取到链表的最后一个节点
            $currentNode = $currentNode->next;
        }
        // 下面两行代码实现插入替换next
        $node->next        = $currentNode->next;
        $currentNode->next = $node;
        $currentNode->next = $node;
    }

    /**
     * 获取整个链表内容
     *
     * @return array
     */
    public function getLinkList()
    {
        $result      = [];
        $currentNode = $this->node;
        // 链表为空的
        if ($currentNode === null) {
            return $result;
        }

        while ($currentNode->next !== null) {
            array_push($result, [
                'id'    => $currentNode->next->id,
                'value' => $currentNode->next->value,
            ]);
            if ($currentNode->next->next === null) {
                break;
            }
            $currentNode = $currentNode->next;
        }

        return $result;
    }

    /**
     * 往链表中删除指定节点
     * @param $id
     * @return bool
     */
    public function delLink($id)
    {
        $currentNode = $this->node;
        while ($currentNode->next !== null) {
            if ($currentNode->next->id === $id) {
                $currentNode->next = $currentNode->next->next;

                return true;
            }

            $currentNode = $currentNode->next;
        }

        return false;
    }

    /**
     * 获取链表的长度
     *
     * @return int
     */
    public function getLinkLength()
    {
        $count       = 0;
        $currentNode = $this->node;
        while ($currentNode->next !== null) {
            $count++;
            $currentNode = $currentNode->next;
        }

        return $count;
    }

    /**
     * 更新链表
     *
     * @param $id
     * @param $value
     */
    public function updateLink($id, $value)
    {
        $currentNode = $this->node;
        while ($currentNode->next !== null) {
            if ($currentNode->next->id === $id) {
                $currentNode->next->value = $value;
                break;
            }

            $currentNode = $currentNode->next;
        }
    }

    /**
     * 根据链表ID获取链表的值
     *
     * @param $id
     * @return mixed|null
     */
    public function getLinkValueById($id)
    {
        $linkList = $this->getLinkList();
        foreach ($linkList as $item) {
            if ($id === $item['id']) {
                return $item['value'];
            }
        }

        return null;
    }

    /**
     * 清空链表
     */
    public function clear()
    {
        $this->node = new Node(null, null);
    }

    /**
     * 判断链表是否为空
     *
     * @return bool
     */
    public function isEmpty()
    {
        return $this->node->next !== null;
    }
}
test.php
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
<?php
require 'SingleLink.php';

$singleLink = new SingleLink;
$singleLink->add(1, 'aaaa');
$singleLink->add(3, 'cccc');
$singleLink->add(2, 'bbbb');

echo $singleLink->getLinkLength(); // 打印链表长度

var_dump($singleLink->getLink()); // 获取链表的内容

$singleLink->delLink(2); // 删除id为2的节点

// TODO：其他的自行实践
单项链表

评论加载中