札记之PHP实现单向链表

Posted on | In

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

单向链表的类型声明

1
2
3
4
5
6
7
8
9
class ListNode
{
    private $data = NULL;
    private $next = NULL;
    public function __construct(string $data = NULL)
    {
        $this->data = $data;
    }
}

链表的遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class LinkedList 
{
	private $headNode = NULL;
	private $length = 0;

	function display() 
	{
		$currentNode = $this->headNode;
		while ($currentNode != NULL) {
			print $currentNode->data. "\n\r";
			$currentNode = $currentNode->next;
		}
	}
}

链表的插入

表开头插入结点

表头插入结点，只需要修改新结点的next指针

  • 更新新结点的next指针，使其指向当前结点的表头结点；
  • 更新表头指针的值，使其指向新结点；
    札记之PHP实现单向链表
表结尾插入结点

尾部插入新结点，需要修改两个next指针，一个为最后结点的next指针和新结点的next指针

  • 新结点的next指针指向NULL；
  • 最后一个结点的next指针指向新结点；
    札记之PHP实现单向链表
表中间插入结点
  • 找到位置结点，再将新结点的next指向位置结点的下一个结点；
  • 位置结点的next指针指向新结点；
    札记之PHP实现单向链表

链表的删除

删除链表的表头
  • 创建一个临时结点，它指向表头指针所指向的结点。
  • 修改表头指针的值，使其指向下一个结点，并移除临时结点。
    札记之PHP实现单向链表
删除链表的表尾
  • 遍历链表，在遍历时保存前驱结点的地址，当遍历到链表的表尾时，将有两个指针，分别是表尾结点的指针和指向表尾结点的前驱结点的指针;
  • 将表尾的前驱结点的next指针更新为NULL;
  • 移除表尾结点;
    札记之PHP实现单向链表
删除链表中间的结点
  • 遍历链表，在遍历时保存前驱结点的地址，找到被删除的结点，将前驱结点的next指针的值更新为被删除的结点的next指针的值
  • 移除需删除的当前结点
    札记之PHP实现单向链表

完整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
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
class ListNode
{
    private $data;
    private $next;
    public function __construct(string $data = NULL)
    {
        $this->data = $data;
    }
    public function __get($var)
    {
        return $this->$var;
    }
    public function __set($var, $val)
    {
        return $this->$var = $val;
    }
}


class LinkedList
{
    private $head = NULL;
    private $length = 0;
    private $currentNode;

    /**
     * 插入一个结点
     * @param string|NULL $data
     * @return bool
     * complexity O(n)
     */
    public function insert(string $data = NULL)
    {
        $newNode = new ListNode($data);
        if ($this->head === NULL) {
            $this->head = &$newNode;
        } else {
            $currentNode = $this->head;
            while ($currentNode->next !== NULL) {
                $currentNode = $currentNode->next;
            }
            $currentNode->next = $newNode;
        }
        $this->length++;
        return true;
    }

    /**
     * 在最前方插入结点
     * @param string $data
     * complexity O(1)
     */
    public function insertAtFirst($data) 
    {
        $newNode = new ListNode($data);
        if ($this->headNode == NULL) {
            $this->headNode = &$newNode;
        } else {
            $currentFirstNode  = $this->headNode;
            $newNode->next = $currentFirstNode;
            $this->headNode = $newNode;
        }

        $this->length++;
    }

    /**
     * 在特定结点后插入
     * @param string|NULL $data
     * @param string|NULL $query
     * complexity O(n)
     */
    public function insertAfter(string $data = NULL, string $query = NULL)
    {
        $newNode = new ListNode($data);

        if ($this->head !== NULL) {
            $currentNode = $this->head;
            while ($currentNode !== NULL) {
                if ($currentNode->data === $query) {
                    $newNode->next = $currentNode->next;
                    $currentNode->next = $newNode;
                    $this->length++;
                    break;
                }
                $currentNode = $currentNode->next;
            }
        }
    }

    /**
     * 在特定结点前插入
     * @param string $data
     * @param string $query
     * complexity O(n)
     */
    public function insertBefore(string $data = NULL, string $query = NULL)
    {   
        $newNode = new ListNode($data);
        //只有一个结点的情况
        if ($this->head && $this->head->data == $query) {
            $newNode->next = $this->head;
            $this->head = $newNode;
        }

        if ($this->head !== NULL) {       
            $previous = NULL;
            $currentNode = $this->head;
            while ($currentNode !== NULL) {
                if ($currentNode->data === $query) {
                    $previous->next = $newNode;
                    $newNode->next = $currentNode;
                    $this->length++;
                    break;
                }
                $previous = $currentNode;
                $currentNode = $currentNode->next;
            }
        }
    }

    public function display()
    {
        echo 'LinkList length: ' . $this->length . PHP_EOL;
        $currentNode = $this->head;
        while ($currentNode !== NULL) {
            echo $currentNode->data . PHP_EOL;
            $currentNode = $currentNode->next;
        }
    }

    /**
     * 获取最后一个结点
     * @return bool
     */
    public function getAfterNode()
    {
        $currentNode = $this->head;
        while ($currentNode !== NULL) {
            $currentNode = $currentNode->next;
            if ($currentNode->next == NULL) {
                return $currentNode;
            }
        }
    }

    /**
     * 搜索一个结点
     * @param string $data
     * @return bool|ListNode
     * complexity O(n)
     */
    public function search(string $data)
    {
        if ($this->length > 0) {
            $currentNode = $this->head;
            while ($currentNode !== NULL) {
                if ($currentNode->data === $data) {
                    return $currentNode;
                }
                $currentNode = $currentNode->next;
            }
        }
        return false;
    }

    /**
     * 删除最前面的结点
     * @return bool
     * complexity O(1)
     */
    public function deleteFirst()
    {
        if ($this->head !== NULL) {
            if ($this->head->next !== NULL) {
                $this->head = $this->head->next;
            } else {
                $this->head = NULL;
            }
            $this->length--;
            return true;
        }
        return false;
    }

    /**
     * 删除最后面的结点
     * @return bool
     * complexity O(1)
     */
    public function deleteLast()
    {
        if ($this->head !== NULL) {
            $currentNode = $this->head;
            if ($currentNode->next !== NULL) {
                $previousNode = NULL;
                while ($currentNode->next !== NULL) {
                    $previousNode = $currentNode;
                    $currentNode = $currentNode->next;
                }
                $previousNode->next = NULL;
            } else {
                $this->head = NULL;
            }
            $this->length--;
            return true;
        }
        return false;
    }

    public function delLinkedList()
    {
        if ($this->head !== NULL) {
            $this->head = NULL;
        }
    }

    public function getLinkLength() 
    { 
        $i = 0; 
        $currentNode = $this->head; 
        while ($currentNode->next !== NULL) { 
            $i ++; 
            $currentNode = $currentNode->next; 
        }
        return $i;
    }

    /**
     * 删除特定结点
     * @param string $query
     * @return bool
     * complexity O(n)
     */
    public function delete(string $query)
    {
        if ($this->head !== NULL) {
            $currentNode = $this->head;
            $previous = NULL;
            while ($currentNode !== NULL) {
                if ($currentNode->data === $query) {
                    if ($currentNode->next === NULL) {
                        $previous->next = NULL;
                    } else {
                        $previous->next = $currentNode->next;
                    }
                    $this->length--;
                    return true;
                }
                $previous = $currentNode;
                $currentNode = $currentNode->next;
            }
        }
        return false;
    }

    /**
     * 返回特定位置的结点
     * @param int $n
     * @return NULL
     * complexity O(n)
     */
    public function getNthNode(int $n = 0)
    {
        $count = 0;
        if ($this->head !== NULL && $n <= $this->length) {
            $currentNode = $this->head;
            while ($currentNode !== NULL) {
                if ($count === $n) {
                    return $currentNode;
                }
                $count++;
                $currentNode = $currentNode->next;
            }
        }
    }

    /**
     *反转链表
     * complexity O(n)
     */
    public function reverse()
    {
        if ($this->head !== NULL) {
            if ($this->head->next !== NULL) {
                $reveredList = NULL;
                $next = NULL;
                $currentNode = $this->head;
                while ($currentNode !== NULL) {
                    $next = $currentNode->next;
                    $currentNode->next = $reveredList;
                    $reveredList = $currentNode;
                    $currentNode = $next;
                }
                $this->head = $reveredList;
            }
        }
    }
}


$linkedObj = new LinkedList();

print("============插入===========\n\r");
printf("插入结点1,2,3,4,5,6\n\r");
$linkedObj->insert(1);
$linkedObj->insert(2);
$linkedObj->insert(3);
$linkedObj->insert(4);
$linkedObj->insert(5);
$linkedObj->insert(6);
printf("在结点2后面插入:%d\n\r", 22);
$linkedObj->insertAfter(22, 2);
printf("在结点4前面插入:%d\n\r", 33);
$linkedObj->insertBefore(33, 4);
printf("插入后数据:\n\r");
$linkedObj->display();

print("============删除===========\n\r");
printf("删除头部结点1\n\r");
$linkedObj->deleteFirst();
printf("删除尾部结点6\n\r");
$linkedObj->deleteLast();
printf("删除结点5\n\r");
$linkedObj->delete(5);
printf("删除后的数据:\n\r");
$linkedObj->display();

print("============反转===========\n\r");
$linkedObj->reverse();
printf("反转后的数据:\n\r");
$linkedObj->display();

运行结果

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
============插入===========
插入节点1,2,3,4,5,6
在节点2后面插入:22
在节点4前面插入:33
插入后数据:
LinkList length: 8
1
2
22
3
33
4
5
6
============删除===========
删除头部节点1
删除尾部节点6
删除节点5
删除后的数据:
LinkList length: 5
2
22
3
33
4
============反转===========
反转后的数据:
LinkList length: 5
4
33
3
22
2
参考资料：
数据结构与算法之美
-------------本文结束感谢您的阅读-------------
坚持原创技术分享，您的支持将鼓励我继续创作！