chapter_array_and_linkedlist/summary/

[giscus[bot]]

chapter_array_and_linkedlist/summary/

一本动画图解、能运行、可提问的数据结构与算法入门书

https://www.hello-algo.com/chapter_array_and_linkedlist/summary/

[Wonderdch]

对 Cache locality 的一个简单解释：Why does cache locality matter for array performance?

[jianglusheng]

大概看了一下，计算机在加载数据时，会把某个位置周围的数据也一起加载，因为数组是连续空间，在遍历时，加载第一个索引的数据时，会把后面的数据直接缓存，遍历后面的数据就更快了，而链表不是连续的，遍历第一个时也会加载他附近的数据，但是并不是我们遍历要用到的

[ruqingxu001]

"列表的出现大大提升了数组的实用性，但副作用是会造成部分内存空间浪费",这里的”部分内存空间浪费“是指额外增加的变量如容量、长度、扩容倍数所占的内存吗？

[krahets]

好问题，有这方面原因。更主要是因为：

1. 列表都会设定一个初始长度，我们不一定需要用这么多；
2. 为了防止频繁扩容，扩容一般都会乘以一个系数，比如 *1.5 。这样一来，也会出现很多空位，我们一般不会正正好好填满它们。

[zhuasdfg]

Q&A看得我云里雾里，不过小结的总结很简练。局部缓存的知识感觉很及时

[Azirliang]

Q&A的最后一条的解释可能不是很完美。在Python中分代码块，如果在同一个代码块里面，则采用统一代码块下的缓存机制。如果属于不同的代码块，则采用小数据池的缓存机制（可以理解成单例的或者全局的字典），而且对于int类型来说，小数据池的缓存范围在-5到256

[krahets]

谢谢补充！最后一条 Q&A 主要想说明 Python 不同于其他语言的存储整数的机制，你补充了 Python 在相同 / 不同代码块下采用的的缓存机制。

[lhr19971010]

JavaScript中数组没有要求一定要是一样的类型吧?目前在学java感觉两科语言差异还是有蛮多的

[LIJUNSONG98]

对的，JS的灵活性太强了，感觉如果只会JS，在学这些底层的东西的时候会吃力很多。

[malone6]

是的，python也是，这样比固定类型的性能就会低的

[krahets]

@malone6 是的，灵活性和性能是此消彼长的两个属性

[CodingGorit]

先学了一遍 c 的数据结构 与算法，再学其他的语言的看就容易一些

[wywsoor]

看到各位大佬的发言我觉得两个方面吧，性能优劣是一方面，灵活性是真的高。

[Turing-1024-Lee]

Hi, K神，
在Q&A的第二个问题回答的第二段文字“从垃圾回收的角度看，对于 Java、Python、Go 等拥有自动垃圾回收的语言来说，节点 P 是否被回收取决于是否有仍存在指向它的引用，而不是 P.next 的值。在 C 和 C++ 等语言中，我们需要手动释放节点内存。”中，
“节点 P 是否被回收取决于是否有仍存在指向它的引用”好像存在语病，应该是“节点 P 是否被回收取决于是否仍存在有指向它的引用”。

[krahets]

谢谢指正！

[leelearner]

关于Q&A第一条有些不懂的地方
在第3章中提到过，堆栈都是由数组或链表实现的复杂数据结构，那怎么理解数组存储在堆或栈上这个说法？打个比方的话，是否是操作系统代码中先用数组或链表的方式实现了栈，然后每个栈帧中又可以存放用户代码的数组？

[krahets]

内存管理中的堆和栈，与数据结构的堆和栈，不是一个概念奥

[cocowise]

关于Q&A中 在 Python 中初始化 n = [1, 2, 3] 与初始化 m = [2, 1, 3]
原因是Cython在启动时前创建−5 到 256 的整数对象，它们被称为预分配的整数。可搜索“为什么 256 是 256，而 257 不是 257”

[showlibia]

DAY3

[hubscut]

python中的列表是本文提到的动态数组吗。列表允许存储不同类型的元素，但数组要求相同类型的元素

[krahets]

Hi，Python 中的列表的底层是动态数组。

列表允许存储不同类型的元素

这个具体得看编程语言实现，像 Java 的 ArrayList 仍然限制存储相同类型的元素。

[Coolllh]

例如，双向队列适合使用链表实现，我们维护一个指针变量始终指向头结点、尾结点，每次插入与删除操作都是 O(1)。
对于这一点我有点问题就是维护一个指针变量始终指向头结点和尾节点，对于插入操作每次都是O（1）是没有错，但是对于删除操作呢？如果我想删出的在链表的中间呢？这样时间复杂度不还是O（n）吗

[krahets]

如果需要删除的节点在中间，需要遍历查找，时间复杂度确实是 $O(n)$ 。使用何种数据结构得具体看应用场景的实际情况。

[AceLi12138]

对于“初始化列表 res = [0] * self.size() 操作，会导致 res 的每个元素引用相同的地址吗？”这个问题。在python中，正如您之前讲到的列表中每个数字都是一个引用，那您回答中的“初始化二维列表 res = [[0] * self.size()] 多次引用了同一个列表 [0]”是如何发现的呢？

[AceLi12138]

假设 self.size() = 5, 那么mat的每一个元素都是同一个对象怎么理解呢，如果是同一个对象的话我对其中一个修改值之后，其他值为什么还是原来的0呢

[krahets]

arr 中的每个元素是独立的。mat 中有 self.size 个 arr ，这些 arr 都指向同一个对象。所以你修改 arr 中的一个元素，mat 中的“这一列”都会被改变。

[AceLi12138]

arr = [0]
mat = [arr * 5]
print(mat)
[[0, 0, 0, 0, 0]]
arr[0] = 1
print(mat)
[[0, 0, 0, 0, 0]]
这样的修改有什么问题吗，为什么并不能改变mat呢（在python

[krahets]

arr = [0] * 5
mat = [arr] * 5
print(mat)
# [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]

mat[0][0] = 1
print(mat)
# [[1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0]]

[AceLi12138]

神奇，谢谢k神解答

[Kore-yoshi]

想问一下：有没有推荐的相应的题目可以用来巩固和拓展的呀

[krahets]

Hi，可以看下这里：https://github.com/krahets/LeetCode-Book

[Kore-yoshi]

非常感谢！！！

[MaoPingZou]

对于 “ 初始化列表 res = [0] * self.size() 操作，会导致 res 的每个元素引用相同的地址吗？” 这个问题，运行下面的代码得到每个对象的 id 地址值是同样的，那为什么答案是 "不会引用相同的地址" 呢？

res = [0] * 5

for r in res:
    print(id(r))

[Ccclarachen]

同问

[Teio-1988]

同问，可能和Python的特性有关。例如图示代码，都是对数值“1‘的引用，听老师说这些都是在静态存储区的，所以有相同的地址。列表中
同理。（个人猜测，不一定对，还请指教）

[redandblueqwer]

感觉解释得确实有点模糊，不过结合后面应该想强调，res = [0] * 5，中res[0]、res[1]、res[2]、res[3]、res[4]，就是五个不一样的指针，虽然指针指向的对象是一样的(都是0)，改变其中一个都不会对其他指针的内容有影响。但是对于二维数组的话，就存在列上指针的重复。
引用下面K神回答的一个例子

arr = [0] * 5
mat = [arr] * 5
print(mat)
# [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]

mat[0][0] = 1
print(mat)
# [[1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0]]

[surpoloyang]

不管怎样说，如倒数第三个Q&A所述，[0]*self.size()中的每一个元素还是引用的同一个内存地址

[krahets]

感谢指出！这里写的确实有歧义，已修正。这个问题挺有趣：

1. 在列表 [0, 0, 0] 中，所有整数 0 都是同一个对象的引用。这是因为 Python 对小整数（通常是 -5 到 256）采用了缓存池机制，以便最大化对象复用，从而提升性能。
2. 虽然它们指向同一个对象，但这并不影响它们的独立性。我们仍然可以单独修改列表中的每个元素。这是因为 Python 的整数是“不可变对象”。当我们修改某个元素时，实际上是切换为另一个对象的引用，而不是改变原有对象本身。
3. 然而，当列表元素是“可变对象”时（例如列表、字典或类实例等），修改某个元素会影响其他引用相同对象的元素，所有引用该对象的元素都会产生相同变化。

[wupenhu]

two day.

[ElvisWai]

Q：操作 res = [[0]] * n 生成了一个二维列表，其中每一个 [0] 都是独立的吗？
其实有歧义，应该是 res[0][n] 的每个值 0 是否独立？

res = [[0]] * 3  # [[0], [0], [0]]
res[0][0] = 1 # [[1], [1], [1]]

res = [[0] * 3]  #  [[0], [0], [0]]
res[0]= [1] # [[1], [0], [0]]

[yhh2908307500]

其实也没有歧义。“其中每一个 [0] 都是独立的吗？” 这句话包含了 “其中每一个 [0] 中的0 都是独立的吗？”

[NotUr77]

“Python 中的数字也被包装为对象，列表中存储的不是数字本身，而是对数字的引用” 长见识了

[jiuerya7]

好家伙，python里面变量存储的都是对象的引用，涨知识了，那是不是所有弱类型语言的实现都是和python一样？

[xiaozhuge123]

day03

[RobinElysia]

在该列表中，所有整数 0 都是同一个对象的引用。这是因为 Python 对小整数（通常是 -5 到 256）采用了缓存池机制，以便最大化对象复用，从而提升性能。

虽然它们指向同一个对象，但我们仍然可以独立修改列表中的每个元素，这是因为 Python 的整数是“不可变对象”。当我们修改某个元素时，实际上是切换为另一个对象的引用，而不是改变原有对象本身。

然而，当列表元素是“可变对象”时（例如列表、字典或类实例等），修改某个元素会直接改变该对象本身，所有引用该对象的元素都会产生相同变化。

[RobinElysia]

这点涉及到python的深浅拷贝了，感兴趣的可以查一下

[solink7]

打卡2025/6/8

太精彩了！

[ruqingxu001]

你的邮件我已经收到！

[Ivy129]

2025年6月12日
打卡，这段总结仍然还有存在疑惑的地方

[main520]

打卡 2025/7/7

好困

[ruqingxu001]

你的邮件我已经收到！

[zhuchentong]

坚持学习，打卡20250805

[ruqingxu001]

你的邮件我已经收到！

[nanmingjushi]

在Java中，ArrayList 和 LinkedList 都是 Java 中 List 接口的实现类，ArrayList 基于动态数组，LinkedList 基于双向链表。

[ruqingxu001]

你的邮件我已经收到！

[Oceans820]

有点不是很理解列表和链表直接的区别，希望有友友可以帮忙解答，感谢

[KuitoInoguchi]

列表是一种更抽象的数据结构，而链表是比较具体的数据结构，因此列表可以由链表实现，也可以由数组实现。你可以把列表想象成“交通工具”，而链表是“飞机”，数组是“汽车”，“飞机”或者“汽车”都可以承担“交通工具”的职责，只是各有各的优势和短板。