数组和链表

1. 内存的工作原理

​ 计算机将内存会分为很多格子(类似书柜)，每个格子都会对应自己地址，就是内存地址

​ 每当计算机接收到存储命令时，计算机会告诉你一个内存地址，表示你的东西存在这个地址。

​ 当需要存储多个数据时，有两种基本存储方式：数组和链表

2. 数组和链表的差异

​ 1. 存储方式

​ 1.1 数组存储方式

​ 利用数组进行存储多项数据时，会需要计算机提供一排连续的位置，即是数组在存储的时候，必须保证内存地址是依次相邻的，且在添加数据时也必须保证有相邻的位置提供，附近没有相邻的位置，则必须整体迁移(类似和朋友看电影，必须要是相邻的位置，如果中途有其他朋友来，那么又要重新寻找有足够多空余并且相邻的位置)。为了避免这种中途添加数据会导致全部数据整体迁移的问题，可以提前请求多个相邻的位置，但是如果中途没有数据再次添加，那么就会导致资源的浪费。或者请求多个位置用完了，那么又要整天重新迁移位置。

所以在使用数组进行存储数据时，速度相对缓慢，且容易浪费资源

​ 1.2 链表的存储方式

​ 链表进行存储时，只需要有足够的内存空间即可进行存储。链表中的每个元素都会携带下一个元素的内存地址，因此在存储数据时，只需要修改上一个元素指向的内存地址即可。

链表在存储数据时，速度相对较快，且只需要有足够的内存空间即可进行存储。

​ 2. 查询方式

​ 2.1 数组的查询方式

​ 由于数组在存储时内存地址都是相邻的，因此你知道所有元素的内存地址，所以可以通过索引的方式进行查询，而一般数组的第一个元素的索引为0，即是从0开始依次累加顺序。

​ 数组支持顺序查询和随机查询。

数组在进行查询时的速度较快(O(1))，因为可以通过简单的数学运算可以马上知道你要查询元素位置.

​ 2.2 链表的查询方式

​ 由于链表在存储时是任意位置存储的，所以你要知道某个元素的地址，就必须先知道上一个元素的位置，依次类推，则你必须先知道第一个元素的位置，所以链表在查询时只支持顺序查询。

链表在查询时速度较慢(O(n))，因为无法通过简单的数学运算计算出某个元素的位置，必须要先知道上一个元素的位置

​ 3. 删除方式

​ 3.1 数组的删除方式

​ 数组在删除某个元素时，后面的元素必须依次向前移动。因此数组在删除元素时的速度较慢(O(n))。

​ 3.2 链表的删除方式

​ 链表在删除某个元素时，只需要修改上一个元素指向的地址即可。因此链表在删除元素时速度较快(O(1))

​ 4. 插入方式

​ 4.1 数组的插入方式

​ 数组在插入时必须要保证有足够的空间，如果没有足够的空间，那么需要整个数组复制到其他地方。因此在插入元素时数组速度较慢(O(n)).

​ 4.2 链表的插入方式

​ 链表在插入时，只需要修改上一个元素指向的位置即可。因此链表在插入时速度较快(O(1))。

3. 总结

​ 下面是数组和链表常见的操作运行时间。（注意：有且仅当能够立即访问要删除的元素时，运行时间方为O(1)）

	数组	链表
查询	O(1)	O(n)
插入	O(n)	O(1)
删除	O(n)	O(1)

​ 从表格可以看出，数组和链表都有各自不同的优缺点。所以在使用时需要根据实际情况出发，来判断使用什么方式更加便捷。

​ 数组和链表是可以进行混合使用的。

​ 即在数组中存放一个链表的位置。这样混合后的储存方式，在查询时虽然不如数组，但是比链表块，且在插入和删除时不必链表慢。