##数据结构之数组和链表的区别

从以下几个方面来解释链表和数组的区别

一、存储数据

链表和数组都可用来存放指定的数据类型。

二、物理存储

• 数组：
  数组从栈中分配空间, 对于程序员方便快速,但是自由度小
• 链表：
  链表从堆中分配空间, 自由度大但是申请管理比较麻烦.

三、内存存储形势

• 数组：连续存储
  数组是连续存储的，在操作数组中的数据时就可以根据离首地址的偏移量直接存取相应位置上的数据，但是如果要在数据组中任意位置上插入一个元素，就需要先把后面的元素集体向后移一位为其空出存储空间
• 链表：离散存储
  链表是离散存储的，所以在插入一个数据时只要申请一片新空间，然后将其中的连接关系做一个修改就可以，但是显然在链表上查找一个数据时就要逐个遍历了。

四、查询数据

• 数组：查询快
  数组要求是一块连续的内存空间来存储，这就要求在物理上这一片空间是连续的，每个元素都有指定的索引index指向内存地址，因此查询的时候，可根据index快速找到对应地址存储的信息，此为查询快.
• 链表：查询慢
  链表由于没有像数组那样的索引，因此，查询的时候需要遍历整个链表所有元素的内存地址，然后才能确定目标元素，此为查询慢。

五、增删数据

• 数组：增删数据慢
  数组进行增删的时候，就必须将目标位置后的所有元素都整体移动，因此就比较耗时，此为增删慢.
• 链表：增删数据快
  链表在物理上是动态地分配储存空间，不要求连续性，但是要求逻辑上的连续。它需要存储每个元素在内存中的地址，以及指向下一个节点的指针，然后像链条一样把各元素链起来，保证了在逻辑上的连续性。
  例如：
  • 单链表：
    每个元素除了存储本身的值外，还存储了前驱的引用，也就是存储了前驱所在的内存地址信息。
  • 双链表:
    就是不仅存储了前驱的引用还存储了后继的引用.

总结

数组和链表各有优缺点。具体使用时要根据具体情况选择。当查找数据操作比较多时最好用数组；当对数据集中的数据进行添加或删除比较多时最好选择链表。｀