数组与链表

[aermin]

计算器内存：

需要将数据存储到内存时，你请求计算机提供存储空间，计算机给你一个存储地址。

需要存 储多项数据时，有两种基本方式——数组和链表。

数组与链表

链表

链表中的元素可存储在内存的任何地方。链表的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一起，但也因此随机读取元素会较慢。

数组

数组所有元素是靠在一起的，如果没有一整个空间容下这个数组，就得移到内存的其他地方，因此添加新元素的速度会较慢。

读取元素：

需要随机地读取元素时，数组的效率很高，因为可迅速找到数组的任何元素, 因为数组知道其中每个元素的地址。

在链表中，元素并非靠在一起的，你无法迅速计算出第五个元素的内存 地址，而必须先访问第一个元素以获取第二个元素的地址，再访问第二个元素以获取第三个元素 的地址，以此类推，直到访问第五个元素。

增加元素：

在链表 中添加元素很容易：只需将其放入内存，并将其地址存储到前一个元素中。

需要在中间插入元素时，数组和链表哪个更好呢？使用链表时，插入元素很简单，只需修改 它前面的那个元素指向的地址。而使用数组时，则必须将后面的元素都向后移。

删除元素：

链表也是更好的选择，因为只需修改前一个元素指向的地址即可。而使用数组时，删除元素后，必须将后面的元素都向前移。