札记之PHP实现双向链表

Posted on | In
  • 双向链表的优点：对于链表中一个给定的结点，可以从两个方向进行操作;
  • 双向链表的缺点：每个结点需要一个额外的指针，因此需要更多的开销，插入和删除时更费时;

双向链表的类型声明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class ListNode
{
    public $data = NULL;
    public $next = NULL;
    public $prev = NULL;
    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;
    }
}

双向链表的插入

在链表的开头前插入一个新结点

  • 将新结点的后继指针更新为指向当前的表头结点，将前驱指针赋值为NULL
  • 将表头结点的前驱指针更新为指向新结点，然后将新结点作为表头
    札记之PHP实现双向链表

在链表的末尾后插入一个新结点

  • 遍历到链表的最后，然后插入新结点
  • 将新结点的后继指针赋值为NULL，前驱指针指向表尾结点
  • 将表尾结点的后继指针更新为指向新结点
    札记之PHP实现双向链表

在链表的中间插入一个新结点

  • 将新结点的后继指针赋值为位置结点的后继结点，前驱指针指向位置结点
  • 将位置结点的后继结点的前驱指针赋值为新结点，将位置结点的后继指针赋值为新结点
    札记之PHP实现双向链表

双向链表的删除

删除双向链表的第一个结点

  • 创建一个临时结点，它与表头指向同一个结点
  • 修改表头指针，使其指向下一个结点，将表头指针的前驱指针赋值为NULL，然后移除临时结点
    札记之PHP实现双向链表

删除双向链表的最后一个

  • 找到表尾结点的前驱结点
  • 遍历链表，同时保存前驱结点的地址。当遍历到表尾时，有两个指针分别是指向表尾结点的指针和指向表尾结点的前驱结点的指针
  • 更新表尾结点的前驱结点的后继指针的值为NULL
  • 移除表尾结点
    札记之PHP实现双向链表

删除双向链表中间的一个结点

  • 遍历链表时保存前驱结点,一旦找到要删除的结点，更改前驱结点的后继指针使其指向被删除结点的后继结点，更改被删除结点的后继结点的前驱指针指向被删除结点的前驱结点
  • 移除被删除的当前结点
    札记之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

class ListNode
{
    public $data = NULL;
    public $next = NULL;
    public $prev = NULL;
    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 DoubleLinkedList
{
    private $head = null;
    private $last = null;
    private $length = 0;

    public function insert(string $data = null)
    {
        $newNode = new ListNode($data);
        if ($this->head) {
            $currentNode = $this->head;
            while ($currentNode) {
                if ($currentNode->next === null) {
                    $currentNode->next = $newNode;
                    $newNode->prev = $currentNode;
                    $this->last = $newNode;
                    $this->length++;
                    return true;
                }
                $currentNode = $currentNode->next;
            }
        } else {
            $this->head = &$newNode;
            $this->last = $newNode;
            $this->length++;
            return true;
        }
    }

    /**
     * @param string|null $data
     * @return bool
     */
    public function insertAtFirst(string $data = null)
    {
        $newNode = new ListNode($data);
        if ($this->head === null) {
            $this->head = &$newNode;
            $this->last = $newNode;
        } else {
            $currentFirstNode = $this->head;
            $currentFirstNode->prev = $newNode;
            $newNode->next = $currentFirstNode;
            $this->head = &$newNode;
        }
        $this->length++;
        return true;
    }

        /**
     * @param string|null $data
     * @return bool
     */
    public function insertAtLast(string $data = null)
    {
        $newNode = new ListNode($data);
        if ($this->head !== null) {
            $currentNode = $this->last;
            $this->last = $newNode;
            $currentNode->next = $newNode;
            $newNode->prev = $currentNode;
        } else {
            $this->head = &$newNode;
            $this->last = $newNode;
        }
        $this->length++;
        return true;
    }

    /**
     * @param string|null $data
     * @param string|null $query
     */
    public function insertBefore(string $data = null, string $query = null)
    {
        $newNode = new ListNode($data);
        if ($this->head) {
            $currentNode = $this->head;
            $prevNode = $this->head->prev;
            while ($currentNode !== null) {
                if ($currentNode->data === $query) {
                    if ($prevNode) {
                        $currentNode->prev = $newNode;
                        $newNode->next = $currentNode;
                        $newNode->prev = $prevNode;
                    } else {
                        $currentNode->prev = $newNode;
                        $newNode->next = $currentNode;
                        $this->head = $newNode;
                    }
                    $this->length++;
                    break;
                }
                $prevNode = $currentNode->prev;
                $currentNode = $currentNode->next;
            }
        }
    }

    /**
     * @param string|null $data
     * @param string|null $query
     */
    public function insertAfter(string $data = null, string $query = null)
    {
        $newNode = new ListNode($data);
        if ($this->head) {
            $currentNode = $this->head;
            while ($currentNode) {
                if ($currentNode->data === $query) {
                    if ($nextNode = $currentNode->next) {
                        $currentNode->next = $newNode;
                        $newNode->prev = $currentNode;
                        $nextNode->prev = $newNode;
                        $newNode->next = $nextNode;
                    } else {
                        $currentNode->next = $newNode;
                        $newNode->prev = $currentNode;
                        $this->last = $newNode;
                    }
                    $this->length++;
                    break;
                }
                $currentNode = $currentNode->next;
            }
        }
    }

    /**
     * @return bool
     */
    public function deleteFirst()
    {
        if ($this->head) {
            $currentNode = $this->head;
            $nextNode = $currentNode->next;
            if ($nextNode) {
                $nextNode->prev = null;
                $this->head = $nextNode;
            } else {
                $this->head = null;
            }
            unset($currentNode);
            $this->length--;
            return true;
        }
        return false;
    }

    /**
     * @return bool
     */
    public function deleteLast()
    {
        if ($this->last) {
            $currentNode = $this->last;
            if ($prevNode = $currentNode->prev) {
                $prevNode->next = null;
                $this->last = $prevNode;
            } else {
                $this->last = null;
                $this->head = null;
            }
            $this->length--;
            return true;
        }
        return false;
    }

    /**
     * @param string|null $query
     * @return bool
     */
    public function delete(string $query = null)
    {
        if ($this->head) {
            $currentNode = $this->head;
            $prevNode = null;
            while ($currentNode) {
                if ($currentNode->data === $query) {
                    if ($nextNode = $currentNode->next) {
                        if ($prevNode) {
                            $prevNode->next = $nextNode;
                            $nextNode->prev = $prevNode;
                        } else {
                            $this->head = $nextNode;
                            $nextNode->prev = null;
                        }
                        unset($currentNode);
                    } else {
                        if ($prevNode) {
                            $this->last = $prevNode;
                            $prevNode->next = null;
                            unset($currentNode);
                        } else {
                            $this->head = null;
                            $this->last = null;
                        }
                    }
                    $this->length--;
                    return true;
                }
                $prevNode = $currentNode;
                $currentNode = $currentNode->next;
            }
        }
        return false;
    }

    /**
     * 反转双链表
     */
    public function reverse()
    {
        if ($this->head !== null) {
            if ($this->head->next !== null) {
                $reversedList = null;
                $currentNode = $this->head;
                while ($currentNode !== null) {
                    $next = $currentNode->next;
                    $currentNode->next = $reversedList;
                    $currentNode->prev = $next;
                    $reversedList = $currentNode;
                    $currentNode = $next;
                }
                $this->last = $this->head;
                $this->head = $reversedList;
            }
        }
    }

    /**
     * 返回特定位置的节点
     * @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;
            }
        }
    }

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

$DoubleLinkedObj = new DoubleLinkedList();

print("============插入===========\n\r");
printf("插入节点:2\n\r");
$DoubleLinkedObj->insert(2);

printf("在节点2后面插入:%d\n\r",1);
$DoubleLinkedObj->insertAtFirst(1);

printf("在最后节点插入:%d\n\r",10);
$DoubleLinkedObj->insertAtLast(10);

printf("在最前插入:%d\n\r",3);
$DoubleLinkedObj->insertBefore(3, 1);

printf("在3后插入:%d\n\r",11);
$DoubleLinkedObj->insertAfter(11, 3);

$DoubleLinkedObj->display();
printf("==========删除================\n");
printf("删除首节点%d:\n\r", 3);
$DoubleLinkedObj->deleteFirst();

printf("删除最后节点%d:\n\r", 11);
$DoubleLinkedObj->deleteLast();

printf("指定删除元素%d: \n\r", 10);
$DoubleLinkedObj->delete(10);
$DoubleLinkedObj->display();

print("============反转===========\n\r");
$DoubleLinkedObj->reverse();
printf("反转后的数据:\n\r");
$DoubleLinkedObj->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
============插入===========
插入节点:2
在节点2后面插入:1
在最后节点插入:10
在最前插入:3
在3后插入:11
LinkList length: 5
3
11
1
2
10
==========删除================
删除首节点3:
删除最后节点11:
指定删除元素10: 
LinkList length: 3
11
1
2
============反转===========
反转后的数据:
LinkList length: 3
2
1
11
参考资料：
数据结构与算法之美
-------------本文结束感谢您的阅读-------------
坚持原创技术分享，您的支持将鼓励我继续创作！