数组与链表

#算法 #数据结构

目录

• 1. 总结
• 2. 注意点
• 3. 主要参考

1. 总结

• 数组和链表是两种基本的数据结构，分别代表数据在计算机内存中的两种存储方式：连续空间存储和分散空间存储。两者的特点呈现出互补的特性。
• 数组支持随机访问、占用内存较少；但插入和删除元素效率低，且初始化后长度不可变。
• 链表通过更改引用（指针）实现高效的节点插入与删除，且可以灵活调整长度；但节点访问效率低、占用内存较多。常见的链表类型包括单向链表、环形链表、双向链表。
• 列表是一种支持增删查改的元素有序集合，通常基于动态数组实现。它保留了数组的优势，同时可以灵活调整长度。
• 列表的出现大幅提高了数组的实用性，但可能导致部分内存空间浪费。
• 程序运行时，数据主要存储在内存中。数组可提供更高的内存空间效率，而链表则在内存使用上更加灵活。
• 缓存通过缓存行、预取机制以及空间局部性和时间局部性等数据加载机制，为 CPU 提供快速数据访问，显著提升程序的执行效率。
• 由于数组具有更高的缓存命中率，因此它通常比链表更高效。在选择数据结构时，应根据具体需求和场景做出恰当选择。

2. 注意点

• python 中的数字也被包装为对象，同 js，所以存储的是他的引用
• 列表末尾添加元素时，如果涉及到数据搬运，那么复杂度就是 O(n) 而不是 O(1)
• 数组存储在栈上和存储在堆上，对时间效率和空间效率是否有影响？
  • 存储在栈上和堆上的数组都被存储在连续内存空间内，数据操作效率基本一致。然而，栈和堆具有各自的特点，从而导致以下不同点。
    1. 分配和释放效率：
       1. 栈是一块较小的内存，分配由编译器自动完成；
       2. 而堆内存相对更大，可以在代码中动态分配，更容易碎片化。因此，堆上的分配和释放操作通常比栈上的慢。
    2. 大小限制：栈内存相对较小，堆的大小一般受限于可用内存。因此堆更加适合存储大型数组。
    3. 灵活性：栈上的数组的大小需要在编译时确定，而堆上的数组的大小可以在运行时动态确定。

3. 主要参考

• 《hello，算法》
• 《labuladong 算法笔记》