小结

• 数组和链表是两种基本数据结构，代表了数据在计算机内存中的两种存储方式，即连续空间存储和离散空间存储。两者的优缺点呈现出此消彼长的关系。
• 数组支持随机访问、内存空间占用小；但插入与删除元素效率低，且初始化后长度不可变。
• 链表可通过更改指针实现高效的结点插入与删除，并且可以灵活地修改长度；但结点访问效率低、占用内存多。常见的链表类型有单向链表、循环链表、双向链表。
• 列表又称动态数组，是基于数组实现的一种数据结构，其保存了数组的优势，且可以灵活改变长度。列表的出现大大提升了数组的实用性，但副作用是会造成部分内存空间浪费。

数组 VS 链表

Table. 数组与链表特点对比

	数组	链表
存储方式	连续内存空间	离散内存空间
数据结构长度	长度不可变	长度可变
内存使用率	占用内存少、缓存局部性好	占用内存多
优势操作	随机访问	插入、删除

Tip

「缓存局部性（Cache locality）」涉及到了计算机操作系统，在本书不做展开介绍，建议有兴趣的同学 Google / Baidu 一下。

Table. 数组与链表操作时间复杂度

操作	数组	链表
访问元素	\(O(1)\)	\(O(N)\)
添加元素	\(O(N)\)	\(O(1)\)
删除元素	\(O(N)\)	\(O(1)\)