缓存淘汰的三种策略

  • 先进先出策略 FIFO（First In，First Out）
  • 最少使用策略 LFU（Least Frequently Used）
  • 最近最少使用策略 LRU（Least Recently Used）

可以考虑用链表进行实现。

链表

它并不需要一块连续的内存空间，它通过“指针”将一组零散的内存块串联起来使用。链表要想随机访问第 k 个元素，就没有数组那么高效了。因为链表中的数据并非连续存储的，所以无法像数组那样，根据首地址和下标，通过寻址公式就能直接计算出对应的内存地址，而是需要根据指针一个结点一个结点地依次遍历，直到找到相应的结点。

链表分类

  • 单链表
  • 双向链表
  • 循环链表：循环链表也很简单。它跟单链表唯一的区别就在尾结点

数组与链表的对比

时间复杂度 数组 链表
插入、删除 O(n) O(1)
随机访问 O(1) O(n)

数组简单易用，在实现上使用的是连续的内存空间，可以借助 CPU 的缓存机制，预读数组中的数据，所以访问效率更高。而链表在内存中并不是连续存储，所以对 CPU 缓存不友好，没办法有效预读。

数组的缺点是大小固定，一经声明就要占用整块连续内存空间。如果声明的数组过大，系统可能没有足够的连续内存空间分配给它，导致“内存不足（out of memory）”。如果声明的数组过小，则可能出现不够用的情况。这时只能再申请一个更大的内存空间，把原数组拷贝进去，非常费时。链表本身没有大小的限制，天然地支持动态扩容，我觉得这也是它与数组最大的区别。

实现

1. SingleLinkedListNode.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
class SingleLinkedListNode
{
    /**
     * 节点中的数据域
     *
     * @var null
     */
    public $data;

    /**
     * 节点中的指针域，指向下一个节点
     *
     * @var SingleLinkedListNode
     */
    public $next;

    /**
     * SingleLinkedListNode constructor.
     *
     * @param null $data
     */
    public function __construct($data = null)
    {
        $this->data = $data;
        $this->next = null;
    }
}

2. SingleLinkedList.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

class SingleLinkedList
{
    /**
     * 单链表头结点（哨兵节点）
     *
     * @var SingleLinkedListNode
     */
    public $head;

    /**
     * 单链表长度
     *
     * @var
     */
    private $length;

    /**
     * 初始化单链表
     *
     * SingleLinkedList constructor.
     *
     * @param null $head
     */
    public function __construct($head = null)
    {
        if (null == $head) {
            $this->head = new SingleLinkedListNode();
        } else {
            $this->head = $head;
        }

        $this->length = 0;
    }

    /**
     * 获取链表长度
     *
     * @return int
     */
    public function getLength()
    {
        return $this->length;
    }

    /**
     * 插入数据 采用头插法 插入新数据
     *
     * @param $data
     *
     * @return SingleLinkedListNode|bool
     */
    public function insert($data)
    {
        return $this->insertDataAfter($this->head, $data);
    }

    /**
     * 删除节点
     *
     * @param SingleLinkedListNode $node
     *
     * @return bool
     */
    public function delete(SingleLinkedListNode $node)
    {
        if (null == $node) {
            return false;
        }

        // 获取待删除节点的前置节点
        $preNode = $this->getPreNode($node);
        if (empty($preNode)) {
            return false;
        }

        // 修改指针指向
        $preNode->next = $node->next;
        unset($node);

        $this->length--;
        return true;
    }

    /**
     * 通过索引获取节点
     *
     * @param int $index
     *
     * @return SingleLinkedListNode|null
     */
    public function getNodeByIndex($index)
    {
        if ($index >= $this->length) {
            return null;
        }

        $cur = $this->head->next;
        for ($i = 0; $i < $index; ++$i) {
            $cur = $cur->next;
        }

        return $cur;
    }

    /**
     * 获取某个节点的前置节点
     *
     * @param SingleLinkedListNode $node
     *
     * @return SingleLinkedListNode|bool|null
     */
    public function getPreNode(SingleLinkedListNode $node)
    {
        if (null == $node) {
            return false;
        }

        $curNode = $this->head;
        $preNode = $this->head;
        // 遍历找到前置节点 要用全等判断是否是同一个对象
        // http://php.net/manual/zh/language.oop5.object-comparison.php
        while ($curNode !== $node) {
            if ($curNode == null) {
                return null;
            }
            $preNode = $curNode;
            $curNode = $curNode->next;
        }

        return $preNode;
    }

    /**
     * 输出单链表 当data的数据为可输出类型
     *
     * @return bool
     */
    public function printList()
    {
        if (null == $this->head->next) {
            return false;
        }

        $curNode = $this->head;
        // 防止链表带环，控制遍历次数
        $listLength = $this->getLength();
        while ($curNode->next != null && $listLength--) {
            echo $curNode->next->data . ' -> ';

            $curNode = $curNode->next;
        }
        echo 'NULL' . PHP_EOL;

        return true;
    }

    /**
     * 输出单链表 当data的数据为可输出类型
     *
     * @return bool
     */
    public function printListSimple()
    {
        if (null == $this->head->next) {
            return false;
        }

        $curNode = $this->head;
        while ($curNode->next != null) {
            echo $curNode->next->data . ' -> ';

            $curNode = $curNode->next;
        }
        echo 'NULL' . PHP_EOL;

        return true;
    }

    /**
     * 在某个节点后插入新的节点 (直接插入数据)
     *
     * @param SingleLinkedListNode $originNode
     * @param                      $data
     *
     * @return SingleLinkedListNode|bool
     */
    public function insertDataAfter(SingleLinkedListNode $originNode, $data)
    {
        // 如果originNode为空，插入失败
        if (null == $originNode) {
            return false;
        }

        // 新建单链表节点
        $newNode = new SingleLinkedListNode();
        // 新节点的数据
        $newNode->data = $data;

        // 新节点的下一个节点为源节点的下一个节点
        $newNode->next = $originNode->next;
        // 在originNode后插入newNode
        $originNode->next = $newNode;

        // 链表长度++
        $this->length++;

        return $newNode;
    }

    /**
     * 在某个节点前插入新的节点（很少使用）
     *
     * @param SingleLinkedListNode $originNode
     * @param                      $data
     *
     * @return SingleLinkedListNode|bool
     */
    public function insertDataBefore(SingleLinkedListNode $originNode, $data)
    {
        // 如果originNode为空，插入失败
        if (null == $originNode) {
            return false;
        }

        // 先找到originNode的前置节点，然后通过insertDataAfter插入
        $preNode = $this->getPreNode($originNode);

        return $this->insertDataAfter($preNode, $data);
    }

    /**
     * 在某个节点后插入新的节点
     *
     * @param SingleLinkedListNode $originNode
     * @param SingleLinkedListNode $node
     *
     * @return SingleLinkedListNode|bool
     */
    public function insertNodeAfter(SingleLinkedListNode $originNode, SingleLinkedListNode $node)
    {
        // 如果originNode为空，插入失败
        if (null == $originNode) {
            return false;
        }

        $node->next = $originNode->next;
        $originNode->next = $node;

        $this->length++;

        return $node;
    }

    /**
     * 构造一个有环的链表
     */
    public function buildHasCircleList()
    {
        $data = [1, 2, 3, 4, 5, 6, 7, 8];

        $node0 = new SingleLinkedListNode($data[0]);
        $node1 = new SingleLinkedListNode($data[1]);
        $node2 = new SingleLinkedListNode($data[2]);
        $node3 = new SingleLinkedListNode($data[3]);
        $node4 = new SingleLinkedListNode($data[4]);
        $node5 = new SingleLinkedListNode($data[5]);
        $node6 = new SingleLinkedListNode($data[6]);
        $node7 = new SingleLinkedListNode($data[7]);

        $this->insertNodeAfter($this->head, $node0);
        $this->insertNodeAfter($node0, $node1);
        $this->insertNodeAfter($node1, $node2);
        $this->insertNodeAfter($node2, $node3);
        $this->insertNodeAfter($node3, $node4);
        $this->insertNodeAfter($node4, $node5);
        $this->insertNodeAfter($node5, $node6);
        $this->insertNodeAfter($node6, $node7);

        $node7->next = $node4;
    }
}

3. 定义工具类

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
class SingleLinkedListTool
{
    /**
     * 单链表
     *
     * @var
     */
    public $list;

    /**
     * 构造函数设置$list
     *
     * SingleLinkedListAlgo constructor.
     *
     * @param SingleLinkedList $list
     */
    public function __construct(SingleLinkedList $list = null)
    {
        $this->list = $list;
    }

    /**
     * 设置单链表
     *
     * @param SingleLinkedList $list
     */
    public function setList(SingleLinkedList $list)
    {
        $this->list = $list;
    }

    /**
     * 单链表反转
     *
     * 三个指针反转
     * preNode 指向前一个结点
     * curNode 指向当前结点
     * remainNode 指向当前结点的下一个节点（保存未逆序的链表，为了在断开curNode的next指针后能找到后续节点）
     *
     * @return bool
     */
    public function reverse()
    {
        if (null == $this->list || null == $this->list->head || null == $this->list->head->next) {
            return false;
        }

        $preNode = null;
        $curNode = $this->list->head->next;
        $remainNode = null;

        // 保存头结点，稍后指向反转后的链表
        $headNode = $this->list->head;
        // 断开头结点的next指针
        $this->list->head->next = null;

        while ($curNode != null) {
            $remainNode = $curNode->next;
            $curNode->next = $preNode;
            $preNode = $curNode;
            $curNode = $remainNode;
        }

        // 头结点指向反转后的链表
        $headNode->next = $preNode;

        return true;
    }

    /**
     * 判断链表是否有环
     *
     * 快慢指针判断是否有环
     *
     * @return bool
     */
    public function checkCircle()
    {
        if (null == $this->list || null == $this->list->head || null == $this->list->head->next) {
            return false;
        }

        $slow = $this->list->head->next;
        $fast = $this->list->head->next;

        while ($fast != null && $fast->next != null) {
            $fast = $fast->next->next;
            $slow = $slow->next;

            // 如果慢指针跟快指针相遇了说明有环
            if ($slow === $fast) {
                return true;
            }
        }

        return false;
    }

    /**
     * 合并两个有序链表
     *
     * @param SingleLinkedList $listA
     * @param SingleLinkedList $listB
     *
     * @return SingleLinkedList|SingleLinkedListNode
     */
    public function mergerSortedList(SingleLinkedList $listA, SingleLinkedList $listB)
    {
        if (null == $listA) {
            return $listB;
        }
        if (null == $listB) {
            return $listA;
        }

        $pListA = $listA->head->next;
        $pListB = $listB->head->next;
        $newList = new SingleLinkedList();
        $newHead = $newList->head;
        $newRootNode = $newHead;

        while ($pListA != null && $pListB != null) {
            if ($pListA->data <= $pListB->data) {
                $newRootNode->next = $pListA;
                $pListA = $pListA->next;
            } else {
                $newRootNode->next = $pListB;
                $pListB = $pListB->next;
            }
            $newRootNode = $newRootNode->next;
        }

        // 如果第一个链表未处理完，拼接到新链表后面
        if ($pListA != null) {
            $newRootNode->next = $pListA;
        }
        // 如果第二个链表未处理完，拼接到新链表后面
        if ($pListB != null) {
            $newRootNode->next = $pListB;
        }

        return $newList;
    }

    /**
     * 删除链表倒数第n个结点
     *
     * @param $index
     *
     * @return bool
     */
    public function deleteLastKth($index)
    {
        if (null == $this->list || null == $this->list->head || null == $this->list->head->next) {
            return false;
        }

        $i = 1;
        $slow = $this->list->head;
        $fast = $this->list->head;
        while ($fast != null && $i < $index) {
            $fast = $fast->next;
            ++$i;
        }

        if (null == $fast) {
            return true;
        }

        $pre = null;
        while ($fast->next != null) {
            $pre = $slow;
            $slow = $slow->next;
            $fast = $fast->next;
        }

        if (null == $pre) {
            $this->list->head->next = $slow->next;
        } else {
            $pre->next = $pre->next->next;
        }

        return true;
    }

    /**
     * 寻找中间节点
     *
     * 快慢指针遍历
     *
     * @return SingleLinkedListNode|bool|null
     */
    public function findMiddleNode()
    {
        if (null == $this->list || null == $this->list->head || null == $this->list->head->next) {
            return false;
        }

        $slow = $this->list->head->next;
        $fast = $this->list->head->next;

        while ($fast != null && $fast->next != null) {
            $fast = $fast->next->next;
            $slow = $slow->next;
        }

        return $slow;
    }

    /**
     * 检查是否回文
     * @return bool
     */
    public function isPalindrome()
    {
        if ($this->list->getLength() <= 1) {
            return true;
        }

        $pre = null;
        $slow = $this->list->head->next;
        $fast = $this->list->head->next;
        $remainNode = null;

        // 找单链表中点 以及 反转前半部分链表
        while ($fast != null && $fast->next != null) {
            $fast = $fast->next->next;

            // 单链表反转关键代码 三个指针
            $remainNode = $slow->next;
            $slow->next = $pre;
            $pre = $slow;
            $slow = $remainNode;
        }
        // 链表长度为偶数的情况
        if ($fast != null) {
            $slow = $slow->next;
        }

        // 开始逐个比较
        while ($slow != null) {
            if ($slow->data != $pre->data) {
                return false;
            }
            $slow = $slow->next;
            $pre = $pre->next;
        }
        return true;
    }
}