对数组和链表的一点理解

1.数组与链表是两种基础且重要的数据结构，他们分别代表了“连续存储”和“分散存储”两种物理结构。列表可以通过数组或者链表结构实现。数组的访问效率很高,时间复杂度为O(1)，但是删除和添加元素时间复杂度为O(n).而链表则刚好相反。

2.所用的数据结构物理特性很大程度上决定着程序对内存和缓存的使用效率。

3.计算机的三种存储设备包括了：硬盘、内存和缓存。硬盘断电数据不丢失，内存则是程序运行过程中的中间数据的存储器。缓存也则是计算机CPU经常访问的数据所存储的地方，容量非常有限，旨在提高运行效率。尽管缓存空间容量上比内存小的多，但是执行比内存快的多。

4.数组元素的紧密排列，不需要额外的空间来存储链表节点间的引用指针，因此空间效率更高。但是数组需要一次性分配足够的内存空间，可能造成内存的浪费。而链表以“节点”为单位进行动态内存分配和利用，灵活性更高。

5.缓存命中率。缓存命中率越高，则CPU读写数据的效率就越高。缓存是以缓存行为单位存储和加载数据的，因此缓存加载数组数据和链表数据时的利用效率是不同的。

6.数组具有更高的缓存命中率，因此操作效率上通常优于链表。算法题我们倾向于选择基于数组实现的栈，但当数据量非常大时，可以选择基于链表实现的栈。其根本原因还是因为数组需要预先分配足够的内存空间，可能会造成内存浪费。

本文来自论坛，点击查看完整帖子内容。