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.

[silencekeep]

我对数组和链表增删和查找的时间复杂度O(1)和O(n)的理解是这样的：
查找：数组可以按索引直接跳到对应位置，而链表需要从头开始一步一步走。
增删：数组需要移动后继元素，链表不需要。不知道对不对？？、？？

[bodaq99]

对吧，我也是这么理解的

[krahets]

是的～

[qcc-gif]

pick

[wxamlzm]

这些知识点零散的在各个地方看到过，但能在算法上串联起来，之前是没想过的，我熟练度应该还是太低了

[resteven]

帅，这些问题的提出也太好了，少部分是自己也疑惑的，更多的是完全没有考虑的像是二维数组里面初始化，像是python里数组里存储的是引用。

[Vaeeeee-WJ]

你好，第四个问题：
Q：在链表中插入和删除操作的时间复杂度是 $\mathcal{O(1)}$。但是增删之前都需要 $\mathcal{O(n)}$的时间查找元素，那为什么时间复杂度不是 $\mathcal{O(n)}$呢？
这句话最后的 $\mathcal{O(n)}$ 是不是写错了

[krahets]

Hi，没太看懂，可以再表述一下吗

[Vaeeeee-WJ]

抱歉，当时是我理解错了，这句话没有问题🤦‍♂️

[fangichao]

真棒！！！

[HandyCC]

最后一个Question的 res = [[0] * self.size()] 是否写错了，应该是res = [[0]] * self.size()?

[krahets]

谢谢指正！

[DayDayYES]

打卡，数组和链表两种线性数据结构，都支持数据插入，删除，查询，修改.数组空间长度不可变，空间效率低.链表分散存储的特性使得它可以有效利用空间，但链表的查修操作的时间复杂度为O（n）.列表是一种抽象的数据结构概念，可以由数组或者链表形成，它也称为动态数组，可以动态地进行扩容，从而克服了数组长度不可变的缺点

[HP-Patience]

2024.5.29直接拿下打卡！

数组和链表这两种数据结构是互补的，
数组对于元素访问优于链表，
链表对于元素删除和增加优于数组。

今天才知道列表原来是一种抽象的数据结构概念，是可以动态修改并支持增删查改的数据结构，之前一直和链表混着用。

还有这两种数据结构对于缓存机制有着不同的效益，综合看用数组偏多，实际还是看具体需求，链表更多地应用在数据动态性更强的案例中。

发现不管是力扣题目还是hello算法介绍，在python语言上，都会去使用类别注释，个人觉得还是比较好的习惯，我之前觉得麻烦一直没有使用类别注释，觉得后面需要培养这个习惯。因为python天生支持多态的特性，而其他语言比如java和c++都需要明确指出数据类型，对于代码解释性更强。

[shaoxinH]

列表这里可以看一下Java的源码 虽然我算法学的是c++ 哈哈。。使用c++实时模拟一下列表实现，很有用，特别是感受数组扩容与设置报错的过程，对自己的编程逻辑很有好处

[tiam-bloom]

每一章或者每一小节后面是不是可以给一些相关的算法题(或者力扣题的地址)以供练习更好

[a2635814919]

这个作者的git库LeetCode-Book，里面有给出推荐的算法题

[AddictedK1]

How can u type this??

[HuaWang135608]

链表增删的时候没有元素移动

…

---- 回复的原邮件 ---- | 发件人 | ***@***.***> | | 日期 | 2024年09月09日 15:42 | | 收件人 | ***@***.***> | | 抄送至 | ***@***.***>***@***.***> | | 主题 | Re: [krahets/hello-algo] chapter_array_and_linkedlist/summary/ (Discussion #150) | 我有一个疑问，既然链表访问的时间复杂度为O(n)，那链表想要增删某一个元素时不是要先访问再增删吗，时间复杂度为O(n);数组增删的时间复杂度为O(n),为什么说链表在增删上效率更高 — Reply to this email directly, view it on GitHub, or unsubscribe. You are receiving this because you commented.Message ID: ***@***.***>

[Jeffstarm]

"栈上的数组的大小需要在编译时确定，而堆上的数组的大小可以在运行时动态确定"，哪位大哥可以解释下这句话的意思

[18365615055]

栈内存分配是静态的，也就是说，在编译阶段需要确定数组的大小。例如：
cpp int arr[10]; // 创建一个大小为 10 的数组
在这个例子中，数组的大小 10 是固定的，编译器会在编译时为该数组分配足够的栈内存。

堆内存分配是动态的，数组的大小可以在运行时根据程序的需要来决定。例如：
cpp int n; std::cin >> n; // 用户输入数组的大小 int* arr = new int[n]; // 在堆上创建一个大小为 n 的数组
在这个例子中，数组的大小 n 是在运行时通过用户输入决定的，编译器无法在编译阶段确定这个大小。

[shyGuide]

Q：在链表中插入和删除操作的时间复杂度是
。但是增删之前都需要
的时间查找元素，那为什么时间复杂度不是
呢？
如果是先查找元素、再删除元素，时间复杂度确实是
。然而，链表的
增删的优势可以在其他应用上得到体现。例如，双向队列适合使用链表实现，我们维护一个指针变量始终指向头节点、尾节点，每次插入与删除操作都是
。

这个还是没太理解，有没有大神讲解一下

[Pgq-Selia]

此处的插入和删除操作单单只这两个操作本身
默认已知需要插入/删除的位置，操作本身的时间复杂度是O（1）

如果不知道需要插入/删除的位置，则需要先查找，查找耗时最坏情况是O（n）
那么整个操作的时间复杂度就变成O（n）了

[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]]