Array is a data structure consisting of a collection of elements (values or variables), each identified by at least one array index or key. An array is stored so that the position of each element can be computed from its index tuple by a mathematical formula. The simplest type of data structure is a linear array, also called one-dimensional array.
A linked list whose nodes contain two fields: an integer value and a link to the next node. The last node is linked to a terminator used to signify the end of the list.
数组与链表
在请求计算机提供存储空间的时候，计算机会提供一个存储地址，在存储多项数据的时候，有两种基本的方式数组和链表。
数组
数组意味着所有项在内存中是相连的，会预留空间。
链表
链表中的元素可以存储在内存中的任何地方。链表的每一个元素都存储了下一个元素的地址，从而使一串随机的内存地址串在一起。
比较
链表的优势在于插入和删除元素，数组的优势在于读取元素。
- 在中间插入元素时，链表的表现显然更好，它只需要修改前面一个元素指向的地址就好了。而使用数组时，必须将后面所有的元素都向后移，同时还要考虑空间的问题；
- 在删除元素时，同样是只需要求该前一个元素的指向地址即可，而数组需要集体前移；
- 数组和链表哪个用的多一些呢，显然是数组，因为它支持随机访问，链表只能顺序访问（需要读最后一个元素时，必须要先读取前面所有的元素），很多情况都要求能随机访问，因此数组用的更多。
参考书目：
[^1]: 《算法图解》【美】Aditya Bhargava. 编著
