# 数组和链表

数组和链表的区别：

数组的优点：

数组的缺点：

链表的优点：

链表的缺点：

综上，「对于想要快速访问数据，不经常有插入和删除元素的时候，选择数组；对于需要经常的插入和删除元素，而对访问元素时的效率没有很高要求的话，选择链表。」

# 数组

数组是由相同元素的集合所组成的数据结构，存储在一块连续的内存单元，根据元素的索引可以计算出该元素对应的存储地址。

数组的特点：

在内存中，数组是一块连续的区域
数组需要预留空间（在使用前需要提前申请所占内存的大小，这样不知道需要多大的空间，就预先申请可能会浪费内存空间，即数组空间利用率低）
在数组起始位置处，插入数据和删除数据效率低。插入数据时，待插入位置的的元素和它后面的所有元素都需要向后搬移；删除数据时，待删除位置后面的所有元素都需要向前搬移；这导致了插入数据和删除数据效率较低。
随机访问效率很高，时间复杂度可以达到 $O(1)$ 。因为数组的内存是连续的，想要访问那个元素，直接从数组的首地址处向后偏移就可以访问到了。这意味着数组的查找效率更高。
数组开辟的空间，在不够使用的时候需要扩容，扩容的话，就会涉及到需要把旧数组中的所有元素向新数组中搬移。
数组的空间是从栈分配的。

由一串节点组成，每个节点包含任意的实例数据和一个或两个用来指向下一节点或者上一节点位置的链接。

链表的特点：

在内存中，元素的空间可以在任意地方，空间是分散的，不需要连续
链表中的元素都会两个属性，一个是元素的值，另一个是指针，此指针标记了下一个元素的地址；每一个数据都会保存下一个数据的内存的地址，通过此地址可以找到下一个数据
查找数据时效率低,时间复杂度为 $O(N)$ ；因为链表的空间是分散的，所以不具有随机访问性，如要需要访问某个位置的数据，需要从第一个数据开始找起，依次往后遍历，直到找到待查询的位置，故可能在查找某个元素时，时间复杂度达到 $O(N)$
空间不需要提前指定大小，是动态申请的，根据需求动态的申请和删除内存空间，扩展方便，故空间的利用率较高
任意位置插入元素和删除元素效率较高，时间复杂度为 $O(1)$
链表的空间是从堆中分配的

← 堆树 →