《图解算法》阅读04—数据结构：链表和数组
内存的工作原理
需要将数据存储到内存时，请求计算机提供存储空间，计算机返回一个存储地址。需要存储多项数据时，有两种基本方式——数组和链表。
数组和链表
使用数组进行存储数据时，所存储的数据在内存中都是相连的。 当向数组中添加新元素时，如果原来存储的内存没有了空间，就移到内存的其他地方，添加新元素的速度很慢。一种权变的解决措施是，为每一块数据提供多余的内存空间。但是这种预留的措施同样存在缺点：一是浪费内存，二是还是存在转移数据的可能性。
链表
链表中的元素可以存储在任何地方。链表中的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一起。
当向链表中添加元素时，不需要移动元素，只需要将元素放入的空闲的内存，并将存储的内存地址存储到前一个元素中。链表的优势在于插入元素。
数组
链表的主要缺点在于元素的访问。例如当需要访问最后一个元素时，需要先访问第一个元素，获得第二个元素的地址，一次类推，直至找到最后一个元素的位置进行访问。因此，当我们需要读取链表的所有元素时，效率很高；当需要跳跃式地访问元素时，链表的效率不高。 当随机读取元素时，数组的效率很高，可以迅速找到数组的任何元素。
术语
元素的位置称为索引。数组的元素带编号，编号从0开始。 在执行读取和插入时，数组和链表的时间复杂度不同，如下表所示。
在中间插入
在链表中插入元素时，只需要将前面的元素的指向地址进行修改即可。 在数组中插入元素时，需要将后面的元素往后移动，如果存储空间不够，还需要将整个数组复制到其他地方。
删除
在链表中，仅仅需要修改前一个元素的指向地址；在数组中需要将后面的元素往前移动。 在平时数组用的更多一点，因为它支持随机访问。有两种访问方式：随机访问和顺序访问。链表只支持顺序访问。 例子：Facebook存储用户信息时使用的既不是数组也不是链表，使用一种混合数据结构，链表数组。数组包含26个元素，每个元素都指向一个链表。
