算法-链表的实现

发表于   |   分类于   |  

什么是缓存

缓存是一种提高数据读取性能的技术，在硬件和软件中都有很多应用。比如常见的CPU缓存、数据库缓存、浏览器缓存

缓存淘汰机制：缓存的大小是有限制的，当缓存满了后哪些数据需要被清除 哪里需要被保留，这些都需要缓存淘汰策略来决定。一般分为 先进先出策略 FIFO、最少使用策略 LFU、最近最少使用 LRU

链表是什么

链表（Linked List）是一种稍微复杂一点的 数据结构。通过 指针 把零散的内存串联起来，其中内存块一般称为 结点。为了把内存串联起来，每个结点存储数据外还需要存储下一个结点的地址。

它和数组的区别是，数组需要一组 连续的内存空间 来存储，对内存要求比较高。比如我们需要一块100M的内存空间，假如内存还有足够剩余空间但是没有连续的100M内存空间了，这个时候就会申请失败。

而链表和数组相反，它不需要一块连续的内存空间，它通过指针将一组 零散的内存空间 串联起来，最后拼起来内存空间总和足够即可。

linked_list1

单链表

单链表是一种最简单的链表 结构如下图

linked_list2

其中有2个结点比较特殊，分别是第一个结点和最后一个结点。一般习惯把第一个结点叫做 头结点，最后一个结点叫做尾结点

头结点用来记录链表的基地址，尾结点比较特殊，他的指针不是指向下一个结点，而是指向一个 空地址NULL，表示这是链表的最后一个结点。

和数组一样，链表也支持数据的查找、插入和删除。对于链表的 插入和删除 操作速度是很快的。因为链表本身的存储空间就不是连续的，所以在插入和删除后并不需要搬移结点。只需要改变他前一个结点的指针指向后一个结点即可，所以链表在操作 插入和删除的时候时间复杂度为 O(1)。

linked_list3

对于链表的随机访问K元素就会比数组差很多，因为它在内存中不是连续的，无法通过固定的公式计算出内存地址，只能通过结点一个一个的遍历寻找，时间复杂度为O(1)。

循环链表

循环链表和单链表基本一样，唯一的不同在于循环链表的尾结点指向的是头结点。当处理的数据结构具有环形的特点时采用循环链表结构比较适合。

linked_list4

双向链表

linked_list5

双向链表如上图，它需要额外两个空间来存储 前一个结点 和 后一个结点，所以他会比一般的链表多占用空间。好处就是支持双向遍历

对于寻找前一个结点这种需求 复杂度为O(1)

用 删除操作 举例来说明双向链表的优势

删除链表中的一个数据有2中情况

  • 给定值，删除等于该值的结点
  • 删除给定指针的结点

这里要说明下其实删除本身操作很简单，只是删除一个结点，然后把前一个结点指向被删除结点的后一个结点即可，时间复杂度为O(1)。但是删除操作前需要找到该结点，也就是要遍历链表，对于遍历链表的时间复杂度都是一样的，都是O(n)。根据时间复杂度分析法，删除操作的时间复杂度变为了O(n)，这是对应上面第一种给定值 删除的情况

对于第二种情况给定指针删除结点的需求，双向链表的优势就体现出来了。首先我们给定一个指针，要求删除它，这个操作很简单直接删除，但是删除还有一步操作就是把被删除结点的前一个结点指向被删除结点的后一个结点，这里假设被删除结点为B，B结点前一个结点是A，B结点后一个结点是C，删除B结点的操作是

1.删除B结点
2.更改A结点指向C结点

对于一般的链表因为不知道A结点是谁，所以只能遍历链表寻找到某个结点的下一个结点是B结点才能确定A结点是哪个，然后做删除的第二步操作。所以单向链表的删除操作时间复杂度还是O(n)。双向链表因为本身就存储了前一个结点的指针，直接一步获取到A结点，然后做删除的第二步操作，所以双向两边的删除操作时间复杂度就为O(1)。

双向链表除了添加、删除块以外，对于给定值的查询也要比单向链表块。因为每次查询我们可以记录每次查找的位置P，每次查询根据要查找的值和P的大小比较，决定是哪一半继续查询，所以平均只需要查找一半的数据。

尽管双向链表比较耗内存，但是很多好多的实现还是使用双向链表，这是典型的 空间换时间。对于执行较慢的程序，可以通过空间换时间消耗更多的内存来优化，而消耗过多内存的程序，可以通过时间换空间的思想来降低内存消耗，具体还需要视情况而定。

链表 VS 数组

链表和数组是2种不同的内存组织方式。他们的 插入、删除、随机访问操作的时间复杂度是完全相反的

操作 数组 链表
插入、删除 O(n) O(1)
随机访问 O(1) O(n)

数组的优势体现在它的内存空间是连续的，可以借助CPU的缓存机制，预读数组中的数据 随机访问效率较高。它的缺点是大小固定，需要整块连续空间，如果没有足够连续内存空间可能会导致内存不足的情况。还有一种情况如果内存过小，不够用的时候需要在申请一个更大的内存把原数组的内容复制进去比较费时（举个例子 假如数组1个G不够用了，在申请一个1.5G内存，然后把1G数据复制进去…）

链表的优势体现在它没有大小限制，支持动态扩容，不足的地方就是对于随机访问效率很低，还有对于频繁的插入和删除可能会产生内存碎片。

判断链表是否有环 并找到入口点

这是一个很经典的面试问题，首先确定链表是否是闭环也就是是否是环形链表，然后找到链表的入口点

linked_list6

思路：
1.遍历链表，一个每次走一步，一个每次走二步，如果走的快的追上了走的慢了就说明链表存在闭环 也就是有环，追上的点是相交点
2.如果有环，从链表的起点到环入口点的距离 = 上一步的相交点到环入口点的距离
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
class LinkList
{
	/**
	 * 判断是否有闭环
	 */
	public function getIsLoop(LNode $l)
	{
		$slow = $l;
		$fast = $l;
		$isLoop = false;
		do {
			// 先获取后判断
			$slow = $slow->getNext();
			$fast = $fast->getNext()->getNext();
			if ($slow == $fast) {
				// 有闭环 当前是相交点
				$isLoop = true;
				break;
			}
		} while($fast != null && $fast->getNext() != null);
		if (! $isLoop) {
			// 没有环 直接返回
			return null;
		}
		// 如果找到了 开始找环入口点
		// 因为链表起点到环的入口点距离 = 相交点到环入口点的距离
		// 所以使用2个循环 分别从入口点 和 相交点走 是一定会相较于环入口点的
		// 经过上面 此时 slow = fast = 相交点
		$slow = $l; // 让slow重新回到入口 注意此时的fast就是相交点
		
		// 循环退出条件是2个相等也就是相交了 = 环入口点
		while ($slow != $fast) {
			$slow = $slow->getNext();
			$fast = $fast->getNext();
		}
		// 循环结束后 此时的slow和fast都是环入口点
		return $slow;
	}
}

PHP模拟链表使用LRU策略

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
<?php
// 使用链表实现浏览器的LRU策略
class LinkedList
{
    private $data;
    private $next;
    /**
     * 初始化
     */
    public function __construct($data, $next)
    {
        $this->data = $data;
        $this->next = $next;
    }
    public function setData($data)
    {
        $this->data = $data;
    }
    public function setNext($link)
    {
        $this->next = $link;
    }
    public function getData()
    {
        return $this->data;
    }
    public function getNext()
    {
        return $this->next;
    }
}
class LinkTest
{
    // 方便统计链表长度
    public $max = 10;
    
    /**
     * 初始化N个链表元素
     */
    public function initLink($n)
    {
        $end = new LinkedList(0, null);
        for ($i = 0; $i < $n - 1; $i++) {
            $new = new LinkedList($i + 1, $end);
            $end = $new;
        }
        return $end;
    }
	/**
     * 循环打印链表
     */
    public function loopLink(LinkedList $link)
    {
        if ($link == null) {
            return false;
        }
        
        while ($link->getNext()) {
            echo $link->getData()."<br />";
            $link = $link->getNext();
        }
        // 链表最后一个
        if ($link->getNext() == null) {
            echo $link->getData();
        }
    }
    /**
     * 查找链表中是否存在某个给定值
     */
    public function searchLink($link, $val)
    {
        $flag = false;
        $prev = null;
        $now = null;
        $next = null;
        $i = 1; // 计数
        while ($link && $link->getNext()) {
            if ($i == 1) {
                // 第一次循环特殊设置
                $prev = null;
                $now = $link;
                $next = $link->getNext();
                if ($now->getData() == $val) {
                    $flag = true;
                    break;
                }
                $link = $now;
                $i = $i + 1;
            } else {
                $prev = $link;
                $now = $link->getNext();
                $next = $now->getNext();
                if ($now->getData() == $val) {
                    $flag = true;
                    break;
                }
                
                $link = $now;
                $i = $i + 1;
            }
        }
        return [
            'flag' => $flag,
            'prev' => $prev,
            'now' => $now,
            'next' => $next,
        ];
    }
    /**
     * 添加结点
     */
    public function insertLink($link, $val)
    {
        // 1.遍历结点计算数量并把结点移动到尾结点
        $i = 1;
        $now = $link;
        while ($now->getNext()) {
            // 移动结点到最后一个结点
            $now = $now->getNext();
            ++$i;
        }
        if ($i >= $this->max) {
            // 已经满了 删除链表最后一个结点 然后新值插入链表头
            $lastVal = $now->getData();
            $searchResult = $this->searchLink($link, $lastVal);
            if ($searchResult['flag']) {
                $prev = $searchResult['prev'];
                $prev->setNext(null);
                // 新值直接插入链表头
                $newLink = new LinkedList($val, $link);
            }
        } else {
            // 未满 直接插入链表头
            $newLink = new LinkedList($val, $link);
        }
        return $newLink;
    }
}
$test = new LinkTest();
// 初始化N个结点单向链表
$link = $test->initLink(5);
// 模拟LRU策略
// 判断改值在不在链表中
$val = 99;
$searchResult = $test->searchLink($link, $val);
if ($searchResult['flag']) {
    // 该值存在结点中
    // 删除该节点然后在链表开头补进去该值
    $prev = $searchResult['prev'];
    $next = $searchResult['next'];
    $prev->setNext($next);
    $newLink = new LinkedList($val, $link);
} else {
    // 该值不在链表中
    // 1.换成未满 直接将值插入链表头
    // 2.换成已满 删除链表尾结点，将新的数据插入到链表头
    $newLink = $test->insertLink($link, $val);
}
$test->loopLink($newLink);
echo "<br />链表操作成功";
// var_dump($searchResult['flag']);
// echo "上一个结点";
// var_dump($searchResult['prev']);
// echo "当前结点";
// var_dump($searchResult['now']);
// echo "下一个结点";
// var_dump($searchResult['next']);
exit();

PHP模拟链表实现回文串校验

假设数据是存储在链表中的 实现回文串 形如 1 2 3 3 2 1 或者 1 2 1 这种回文串校验

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
// 用数组模拟造链表吧
$arr = [
    1, 2, 3, 3, 2, 1
    // 1, 2, 3, 2, 1
];
$link = null;
for ($i = 0; $i < count($arr); $i++) {
    if ($i == 0) {
        $link = new LinkedList($arr[$i], null);
    } else {
        $link = new LinkedList($arr[$i], $link);
    }
}
// 使用快慢指针找到中间点，快指针每次都2步 慢指针每次走一步，当快指针走到尾结点的时候慢指针刚好是中间节点
// 注意奇数偶数
// 1 2 3 2 1
$slow = $link;
$fast = $link;
$i = 0;
$j = 0;
$count = 0;
// 寻找中间结点
while ($fast && $fast->getNext()) {
    $slow = $slow->getNext();
    if ($fast->getNext()) {
        $fast = $fast->getNext()->getNext();
    }
    ++$i;
    ++$j;
}
// 循环结束的fast要么在最后一个 要么在null
if (! $fast) {
    // 说明为偶数 最后一个结点
    $count = $j * 2;
    $isDouble = true;
} else {
    // 说明为奇数
    $count = $j * 2 + 1;
    $isDouble = false;
}
// 声明一个新的链表存储半程数据
$new = new LinkedList(null, null);
    
// 此时的slow刚好走了一半
while ($slow && $slow->getNext()) {
    // 进入链表后半程
    $data = $slow->getData();
    $new = new LinkedList($data, $new);
    $slow = $slow->getNext();
}
if ($slow->getNext() == null) {
    // 最后一个
    $new = new LinkedList($slow->getData(), $new);
}
// end 填充新链表
$flag = true;
// 遍历新链表 和 原链表半程是否全部相等
while ($new && $new->getNext()) {
    if ($link->getData() != $new->getData()) {
        $flag = false;
    }
    
    $link = $link->getNext();
    $new = $new->getNext();
}
if ($flag) {
    echo $isDouble ? "偶数" : "奇数";
    echo "回文串";
} else {
    echo "不是回文串";
}
exit();

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
/**
 * 用递归翻转单向链表
 */
public function reverseLink($link)
{
    if ($link) {
        $this->reverseLink($link->getNext());
        echo $link->getData()."<br/>";
    }
}
/**
 * 用循环翻转单向链表
 * 在用循环输出
 */
public function reverseLink2($link)
{
    $head = $link; // 初始化链表头 其实head就相当于一个新的链表
    $next = $link->getNext(); // 初始化链表的第二个结点
    $tmp = null; // 临时保存结点
    $head->setNext(null); // 因为要翻转 设置原链表头为最后一个结点，因为尾结点的next是null
    while ($next != null) {
        $tmp = $next; // 临时存储翻转的完整链表
        $next = $next->getNext(); // 移动指针到下一个结点
        $tmp->setNext($head); // 把head当作一个整体 每次追加一个tmp进来
        $head = $tmp; // 上一步追加了一个tmp进来后 新的链表长度增加一个结点 重新赋值给head
    }
    // 循环打印 - 自己写的方法
    $this->loopLink($head);
}
-------------The End-------------